$\mathbf{unstuck}^{T}(C,t_{0})\subseteq\mathbf{unstuck}^{R}(t_{0})$. This
follows from the consistency of $F_{t_{0}}^{T}$ and $F_{t_{0}}^{R}$, as
already mentioned.

To finish the proof we consider $\tau^{\prime}\geq 1$ such that both
invariants hold for $\tau^{\prime}$, which implies (using the definition of
$\mathcal{E}_{\mathrm{jam}}^{T}(C^{\prime},t_{0},\tau^{\prime})$ in Definition
40) that

$f(\mathbf{stuckvect}^{T}(C^{\prime},t_{0}+\tau^{\prime}-1)\geq\zeta|\mathrm{bins}(\tau^{\prime}-1)|$

and

$\mathbf{unstuck}^{T}(C,t_{0}+\tau^{\prime}-1)\subseteq\mathbf{unstuck}^{R}(t_{0}+\tau^{\prime}-1).$

Using $\mathcal{F}^{T}_{t_{0}+\tau^{\prime}-1}$ and
$\mathcal{F}^{R}_{t_{0}+\tau^{\prime}-1}$ we now wish to consider step
$t_{0}+\tau^{\prime}$, and to extend the coupling to this step in such a way
that
$\mathbf{unstuck}^{T}(C,t_{0}+\tau^{\prime})\subseteq\mathbf{unstuck}^{R}(t_{0}+\tau^{\prime})$.
Once we do this, we’ll have completd the high-level strategy, hence we’ll have
completed the proof.

It is helpful to note by the definition of the processes that for all $t$ and
$j$ we have

$\mathbf{balls}^{T}(C,t)\cap b_{j}^{T}(t)=b_{j}^{Y^{C}}(t)=b_{j}^{R}(t).$

We will use this observation for $t=t_{0}+\tau^{\prime}-1$. From this we
deduce that

$\mathbf{stucksend}^{T}(C,t)\subseteq\mathbf{stucksend}^{R}(t)\cup\mathbf{unstuck}^{R}(t).$

We are finally ready to do the coupling. We first determine
${b^{\prime}_{0}}^{Y^{C}}(t+1)={b^{\prime}_{0}}^{R}(t+1)$ and
$\mathbf{send}^{Y^{C}}(t+1)=\mathbf{send}^{R}(t+1)$. This allows us to deduce
$\mathbf{stucksend}^{T}(C,t+1)$ and $\mathbf{stucksend}^{R}(t+1)$.

We will use this to finish the coupling of step $t+1$ in such a way that any
ball

$\beta\in\mathbf{stucksend}^{T}(C,t+1)\cap\mathbf{unstuck}^{T}(C,t+1)$

is also in $\mathbf{unstuck}^{R}(t+1)$. Here is how we do it: If
$\mathbf{stucksend}^{T}(C,t+1)$ is empty, there is nothing to prove.
Otherwise, choose $\beta$ u.a.r. from $\mathbf{stucksend}^{T}(C,t+1)$ (this is
the random ball that may become unstuck at time $t+1$ in $T$). The probability
that $\beta$ is in $\mathbf{unstuck}^{T}(C,t+1)$ is the probability that
$\mathbf{stucksend}^{T}(C^{\prime},t+1)=\emptyset$. We will use Lemma 44 to
bound this probability. First note that the lemma applies since the definition
of $I_{0}$ ensures that $\zeta|B_{I_{0}}|\geq 4$ so
$\zeta|\mathrm{bins}(\tau^{\prime})|\geq 4$. By Lemma 44, the probability that
$\mathbf{stucksend}^{T}(C^{\prime},t+1)=\emptyset$ is at most

$\exp(-\zeta|\mathrm{bins}(\tau^{\prime}-1)|/16).$

If $\beta$ is in $\mathbf{unstuck}^{R}(t)$ then there is nothing to prove.
Alternatively, if it is in $\mathbf{stucksend}^{R}(t)$, then the probability
that it is in $\mathbf{unstuck}^{R}(t+1)$ is
$p_{\mathrm{unstick}}(t)=\exp(-\zeta|\mathrm{bins}(\tau^{\prime}-1)|/16)$.
Thus we can extend the coupling as required, completing the proof.

∎

It is not hard to see that the final bullet point of Lemma 51 implies
$\mathrm{Fill}_{j}^{R}(\tau)\subseteq\mathrm{Fill}_{j}^{T}(C,\tau)$; this is
the only difference between the statements of Lemma 51 and Corollary 52.

######  Corollary 52.

Fix $\lambda$, $\eta$ and $\nu$ in $(0,1)$ and a $(\lambda,\eta,\nu)$-suitable
send sequence $\mathbf{p}$ with $p_{0}=1$. Let $Y^{A}$ and $Y^{B}$ be
independent externally-jammed processes with arrival rate $\lambda/2$ and send
sequence $\mathbf{p}$ and consider the two-stream externally-jammed process
$T=T(Y^{A},Y^{B})$. Consider any integer $t_{0}\geq j_{\mathrm{min}}$. Let
$F^{T}_{t_{0}}$ be a value of $\mathcal{F}^{T}_{t_{0}}$ such that
$\mathcal{E}_{\mathrm{init}}^{T}(t_{0})$ occurs. Let $C$ and $C^{\prime}$ be
distinct elements of $\\{A,B\\}$. Let $R=R(Y^{C},t_{0})$ be a random-
unsticking process. Let $F^{R}_{t_{0}}$ be a value of
$\mathcal{F}^{R}_{t_{0}}$ that is consistent with $F^{T}(t_{0})$. Consider any
integer $\tau\geq 1$. There is a coupling of

  * •

$T$ conditioned on $\mathcal{F}^{T}_{t_{0}}=F^{T}_{t_{0}}$ and

  * •

$R$ conditioned on $\mathcal{F}^{R}_{t_{0}}=F^{R}_{t_{0}}$

such that at least one of the following occurs:

  * •

$\mathcal{E}_{\mathrm{jam}}^{T}(C^{\prime},t_{0},\tau)$ does not occur, or

  * •

For all positive integers $j$,
$\mathrm{Fill}_{j}^{R}(\tau)\subseteq\mathrm{Fill}_{j}^{T}(C,\tau)$.

###### Proof.

We use the coupling of Lemma 51. If
$\mathcal{E}_{\mathrm{jam}}(C^{\prime},t_{0},\tau)$ does not occur, then the
result is immediate. Otherwise, we have
$\mathbf{unstuck}^{T}(C,t_{0}+\tau)\subseteq\mathbf{unstuck}^{R}(t_{0}+\tau)$.
Since every ball is either stuck or unstuck, it follows that
$\mathbf{stuck}^{R}(t_{0}+\tau)\subseteq\mathbf{stuck}^{T}(C,t_{0}+\tau)$. By
the definitions of $\mathrm{Fill}_{j}^{R}(\tau)$ and
$\mathrm{Fill}_{j}^{T}(C,\tau)$, it follows that
$\mathrm{Fill}_{j}^{R}(\tau)\subseteq\mathrm{Fill}_{j}^{T}(C,\tau)$ as
required. ∎

Then combining the couplings of Corollary 52 (from one stream of $T$ to $R$)
and Lemma 50 (from $R$ to i.i.d. Poisson variables), we get the following
lemma.

######  Lemma 53.

Fix $\lambda$, $\eta$ and $\nu$ in $(0,1)$ and a $(\lambda,\eta,\nu)$-suitable
send sequence $\mathbf{p}$ with $p_{0}=1$. Let $Y^{A}$ and $Y^{B}$ be
independent externally-jammed processes with arrival rate $\lambda/2$ and send
sequence $\mathbf{p}$ and consider the two-stream externally-jammed process
$T=T(Y^{A},Y^{B})$. Consider any integer $t_{0}\geq j_{\mathrm{min}}$. Let
$F^{T}_{t_{0}}$ be a value of $\mathcal{F}^{T}_{t_{0}}$ such that
$\mathcal{E}_{\mathrm{init}}^{T}(t_{0})$ happens. Let $C$ and $C^{\prime}$ be
distinct elements of $\\{A,B\\}$. Consider any integer
$\tau\geq\tau_{\mathrm{init}}$. There is a coupling of

  * •

$T$ conditioned on $\mathcal{F}^{T}_{t_{0}}=F^{T}_{t_{0}}$ and

  * •

A sample $\\{Z_{j}^{-}\mid j\in\mathrm{bins}(\tau)\\}$ where each $Z_{j}^{-}$
is chosen independently from a Poisson distribution with mean
$\lambda/(4p_{j})$

such that at least one of the following occurs:

  * •

$\mathcal{E}_{\mathrm{jam}}^{T}(C^{\prime},t_{0},\tau)$ does not occur, or

  * •

For all integers $j\in\mathrm{bins}(\tau)$,
$|\mathrm{Fill}_{j}^{T}(C,\tau)|\geq Z_{j}^{-}$.

Finally, applying Lemma 53 twice, once with $C=A$ and once with $C=B$ and
using the definitions of $\mathrm{Fill}_{j}^{T}(C,\tau)$ and
$\mathcal{E}_{\mathrm{jam}}^{T}(t_{0},\tau)$, we get Lemma 45 as desired.

See 45

##  5 The main lemma for proving Theorem 25

Our goal in this section is to prove Lemma 56, which says that if $T$ is a
two-stream externally-jammed process with suitable send sequence, and if
$\mathcal{E}_{\mathrm{init}}^{T}(t_{0})$ occurs, then $T$ is likely to stay
$t_{0}$-jammed forever. We start with a simple observation.

######  Observation 54.

Suppose that $\mathbf{p}$ is $(\lambda,\eta,\nu)$-suitable. If $i\geq I_{0}$
then $|\\{j\in B_{i}\mid p_{j}\leq p_{*}\\}|>2\eta|B_{i}|/3$.

###### Proof.

Since $\mathbf{p}$ is $(\lambda,\eta,\nu)$-suitable, $|\\{j\in[u(i)]\mid
p_{j}\leq p_{*}\\}|>\eta u(i)$. At most $u(i-1)$ of these bins are in blocks
$B_{1},\ldots,B_{i-1}$, and by definition we have $u(i-1)=u(i)/\kappa\leq\eta
u(i)/3$, so at least $2\eta u(i)/3$ of these bins are in block $B_{i}$. ∎

We will prove Lemma 56 using a union bound over all time steps. For
readability, we extract the most difficult case of this bound as Lemma 55.

######  Lemma 55.

Let $\mathbf{p}$ be $(\lambda,\eta,\nu)$-suitable. Let $T$ be a two-stream
externally-jammed process with arrival rate $\lambda\in(0,1)$ and send
sequence $\mathbf{p}$. Consider any integer $t_{0}\geq j_{\mathrm{min}}$. Let
$F^{T}_{t_{0}}$ be a value of $\mathcal{F}^{T}_{t_{0}}$ such that
$\mathcal{E}_{\mathrm{init}}^{T}(t_{0})$ happens. Let
$\tau\geq\tau_{\mathrm{init}}$. Conditioned on
$\mathcal{F}^{T}_{t_{0}}=F^{T}_{t_{0}}$, with probability at least
$1-1/(10\tau^{2})$, at least one of the following happens:

  * •

The event $\mathcal{E}_{\mathrm{jam}}^{T}(t_{0},\tau)$ doesn’t occur.

  * •

The process $T$ is $t_{0}$-jammed for time $\tau+1$.

###### Proof.

Let $Y^{A}$ and $Y^{B}$ be independent externally-jammed processes with
arrival rate $\lambda/2$ and send sequence $\mathbf{p}$ such that
$T=T(Y^{A},Y^{B})$. Consider $C\in\\{A,B\\}$. Let $\\{Z_{j}\mid
j\in\mathrm{bins}(\tau)\\}$ be independent Poisson variables with
$\mathbb{E}(Z_{j})=\lambda/(4p_{j})$. Since $\zeta=\eta\lambda/24$, by Lemma
45 and the definition of $f$ (Definition 24),

$\displaystyle\mathbb{P}\bigg{(}\overline{\mathcal{E}_{\mathrm{jam}}^{T}(t_{0},\tau)}\mbox{
or
}f(\mathbf{stuckvect}^{T}(C,t_{0}+\tau))\geq\zeta|\mathrm{bins}(\tau)|\,\Big{|}\,\mathcal{F}_{t_{0}}^{T}=F_{t_{0}}^{T}\bigg{)}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\geq\mathbb{P}\bigg{(}\sum_{j\in\mathrm{bins}(\tau)}p_{j}Z_{j}\geq\frac{{\eta}\lambda|\mathrm{bins}(\tau)|}{{24}}\bigg{)}.$
(13)

Since $\tau\geq\tau_{\mathrm{init}}\geq 0$, we have
$\mathrm{bins}(\tau)=B_{I(\tau)-1}$ where $I(\tau)\geq I_{0}+1$. Observation
54 ensures that there is a set
$\mathrm{bins}^{\prime}(\tau)\subseteq\mathrm{bins}(\tau)$ such that
$|\mathrm{bins}^{\prime}(\tau)|\geq 2\eta|\mathrm{bins}(\tau)|/3$ and for all
$j\in\mathrm{bins}^{\prime}(\tau)$, we have $p_{j}\leq p_{*}$. From Equation
(13) and the lower bound on $|\mathrm{bins}^{\prime}(\tau)|$ we get

$\displaystyle\mathbb{P}\bigg{(}\overline{\mathcal{E}_{\mathrm{jam}}^{T}(t_{0},\tau)}\mbox{
or
}f(\mathbf{stuckvect}^{T}(C,t_{0}+\tau))\geq\zeta|\mathrm{bins}(\tau)|\,\Big{|}\,\mathcal{F}_{t_{0}}^{T}=F_{t_{0}}^{T}\bigg{)}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\geq\mathbb{P}\bigg{(}\sum_{j\in\mathrm{bins}^{\prime}(\tau)}p_{j}Z_{j}\geq\frac{\lambda|\mathrm{bins}^{\prime}(\tau)|}{{16}}\bigg{)}.$
(14)

For each $j\in\mathrm{bins}^{\prime}(\tau)$, let $1_{Z_{j}}$ be the indicator
variable of the event $Z_{j}\leq\lambda/(8p_{j})$, so that

$\sum_{j\in\mathrm{bins}^{\prime}(\tau)}p_{j}Z_{j}\geq\frac{\lambda}{8}\Big{(}|\mathrm{bins}^{\prime}(\tau)|-\sum_{j\in\mathrm{bins}^{\prime}(\tau)}1_{Z_{j}}\Big{)}.$
(15)

We dominate the sum in the right-hand side of (15) above by a binomial random
variable, which we will bound above using the Chernoff bound of Lemma 20. We
first bound the mean $\mu$ of this variable; by the Chernoff bound of Lemma 19
applied with $\delta=1/2$, for all $j\in{\mathrm{bins}^{\prime}(\tau)}$ we
have

$\mathbb{P}(1_{Z_{j}}=1)=\mathbb{P}\big{(}Z_{j}\leq\mathbb{E}(Z_{j})/2\big{)}\leq
e^{-\mathbb{E}(Z_{j})/8}\leq
e^{-\mathbb{E}(Z_{j})/12}=e^{-\lambda/(48p_{j})}\leq e^{-\lambda/(48p_{*})}.$

Let $x=e^{\lambda/(48p_{*})}/2$ and
$\mu=e^{-\lambda/(48p_{*})}|{\mathrm{bins}^{\prime}}(\tau)|$. Since
$p_{*}\leq\lambda/48$, we have $x>1$, which ensures the applicability of Lemma
20. From this lemma, we obtain

$\mathbb{P}\bigg{(}\sum_{j\in\mathrm{bins}^{\prime}(\tau)}1_{Z_{j}}\geq\frac{|\mathrm{bins}^{\prime}(\tau)|}{2}\bigg{)}\leq
e^{-\mu x(\log
x-1)}\leq\exp\bigg{(}{-}\frac{|\mathrm{bins}^{\prime}(\tau)|}{2}\Big{(}\frac{\lambda}{48p_{*}}-2\Big{)}\bigg{)}.$

Recall that $|\mathrm{bins}^{\prime}(\tau)|\geq 2\eta|\mathrm{bins}(\tau)|/3$;
hence by Lemma 43, it follows that

$\mathbb{P}\bigg{(}\sum_{j\in\mathrm{bins}^{\prime}(\tau)}1_{Z_{j}}\geq\frac{|\mathrm{bins}^{\prime}(\tau)|}{2}\bigg{)}\leq\exp\bigg{(}{-}\frac{{2\eta}\log(\tau)}{3\cdot
4\kappa^{2}\log(1/\nu)}\Big{(}\frac{\lambda}{48p_{*}}-2\Big{)}\bigg{)}.$

The rest of the proof is simple manipulation. Since $p_{*}\leq\lambda/200$ we
have $\lambda/(48p_{*})-2\geq\lambda/(100p_{*})$. Since
$p_{*}\leq(\lambda\eta)/(1800\kappa^{2}\log(1/\nu))$ we have
$\lambda/(100p_{*})\geq(18/\eta)\kappa^{2}\log(1/\nu)$ so we get

$\mathbb{P}\bigg{(}\sum_{j\in\mathrm{bins}^{\prime}(\tau)}1_{Z_{j}}\geq\frac{|\mathrm{bins}^{\prime}(\tau)|}{2}\bigg{)}\leq\exp({-}3\log(\tau))=\frac{1}{\tau^{3}}.$

Finally, since $\tau\geq\tau_{\mathrm{init}}\geq 20$, this probability is at
most $1/(20\tau^{2})$. It follows from (15) that

$\mathbb{P}\bigg{(}\sum_{j\in\mathrm{bins}^{\prime}(\tau)}p_{j}Z_{j}\geq\frac{\lambda|\mathrm{bins}^{\prime}(\tau)|}{16}\bigg{)}\geq
1-\frac{1}{20\tau^{2}}.$

It follows from (14) that

$\mathbb{P}\bigg{(}\overline{\mathcal{E}_{\mathrm{jam}}^{T}(t_{0},\tau)}\mbox{
or
}f(\mathbf{stuckvect}^{T}(C,t_{0}+\tau))\geq\zeta|\mathrm{bins}(\tau)|\,\Big{|}\,\mathcal{F}_{t_{0}}^{T}=F_{t_{0}}^{T}\bigg{)}\geq
1-\frac{1}{20\tau^{2}}.$

The result therefore follows by a union bound over $C\in\\{A,B\\}$. ∎

######  Lemma 56.

Let ${\mathbf{p}}$ be $(\lambda,\eta,\nu)$-suitable. Let $T$ be a two-stream
externally-jammed process with arrival rate $\lambda\in(0,1)$ and send
sequence $\mathbf{p}$. Consider any integer $t_{0}\geq j_{\mathrm{min}}$. Let
$F^{T}_{t_{0}}$ be a value of $\mathcal{F}^{T}_{t_{0}}$ such that
$\mathcal{E}_{\mathrm{init}}^{T}(t_{0})$ happens. Then

$\mathbb{P}\Big{(}T\mbox{ is $t_{0}$-jammed for all }\tau\geq
1\mid\mathcal{F}^{T}_{t_{0}}=F^{T}_{t_{0}}\Big{)}\geq 4/5.$

###### Proof.

For all $\tau\geq\tau_{\mathrm{init}}$, let $\mathcal{E}_{\tau}$ be the event
that either $\mathcal{E}_{\mathrm{jam}}^{T}(t_{0},\tau)$ doesn’t occur or that
$T$ is $t_{0}$-jammed for $\tau+1$. We then have

$\displaystyle\mathbb{P}\Big{(}\bigwedge_{\tau\geq
1}\mathcal{E}_{\mathrm{jam}}^{T}(t_{0},\tau)\mid\mathcal{F}_{t_{0}}^{T}=F_{t_{0}}^{T}\Big{)}$
$\displaystyle=\mathbb{P}\Big{(}\mathcal{E}_{\mathrm{jam}}^{T}(t_{0},\tau_{\mathrm{init}})\wedge\bigwedge_{\tau\geq\tau_{\mathrm{init}}}\mathcal{E}_{\tau}\mid\mathcal{F}_{t_{0}}^{T}=F_{t_{0}}^{T}\Big{)}.$

By Lemmas 41 and 55 and a union bound, we therefore have

$\mathbb{P}\Big{(}\bigwedge_{\tau\geq
1}\mathcal{E}_{\mathrm{jam}}^{T}(t_{0},\tau)\mid\mathcal{F}_{t_{0}}^{T}=F_{t_{0}}^{T}\Big{)}\geq\frac{49}{50}-\sum_{\tau\geq\tau_{\mathrm{init}}}\frac{1}{10\tau^{2}}\geq\frac{49}{50}-\frac{\pi^{2}}{60}\geq\frac{4}{5},$

as required. ∎

##  6 Proof of Main Theorems

See 25

###### Proof.

For every positive integer $i$, let $R_{i}$ be the $i$’th smallest time step
in $\mathcal{R}^{T}$. If $|\mathcal{R}^{T}|<i$, then we define $R_{i}=\infty$.
Since $R_{1}=0$, for all $i\geq 2$ we have

$\mathbb{P}(R_{i}<\infty)=\prod_{k=2}^{i}\mathbb{P}(R_{i}<\infty\mid
R_{i-1}<\infty).$ (16)

Let $\mathcal{E}_{i}$ be the event that $R_{i-1}<\infty$ and that
$\mathcal{E}_{\mathrm{init}}^{T}(R_{i-1}+t)$ occurs for some positive integer
$t$ such that $R_{i-1}+t<R_{i}$. Observe that conditioned on $R_{i-1}<\infty$,
the probability of $\mathcal{E}_{i}$ occurring does not depend on $i$ since
$\mathbf{stuck}^{T}$ evolves independently of unstuck balls; let
$p_{\mathrm{init}}=\mathbb{P}(\mathcal{E}_{i}\mid R_{i-1}<\infty)$. Then by
(16), we have

$\mathbb{P}(R_{i}<\infty)\leq\prod_{k=2}^{i}\Big{(}1-p_{\mathrm{init}}+p_{\mathrm{init}}\mathbb{P}(R_{i}<\infty\mid\mathcal{E}_{i},R_{i-1}<\infty)\Big{)}.$
(17)

Observe that if $\mathcal{E}_{\mathrm{init}}(R_{i-1}+t)$ occurs for some
$t<R_{i}-R_{i-1}$, and $T$ is $(R_{i-1}+t)$-jammed for all $\tau\geq 1$, then
we have we must have $\mathbf{stuck}^{T}(R_{i-1}+u)\neq\emptyset$ for all
$u\geq 1$; hence $R_{i}=\infty$.

It follows by applying Lemma 56 to (17) that

$\mathbb{P}(R_{i}<\infty)\leq\prod_{k=2}^{i}\Big{(}1-p_{\mathrm{init}}+p_{\mathrm{init}}/5\Big{)}\leq
e^{-4(i-1)p_{\mathrm{init}}/5}.$ (18)

By (18), we have $\sum_{i}\mathbb{P}(R_{i}<\infty)<\infty$. It follows by the
Borel-Cantelli lemma that with probability 1 we have $R_{i}=\infty$ for all
but finitely many values of $i$, which proves the theorem. ∎

See 26

###### Proof.

Let $T$ be a two-stream externally-jammed process with arrival rate $\lambda$
and send sequence $\mathbf{p}$. Let
$\mathcal{R}^{T}=\\{t\mid\mathbf{stuck}^{T}(t)=\emptyset\\}$. Theorem 25 shows
that, with probability $1$, $\mathcal{R}^{T}$ is finite. Let $Y$ be an
externally-jammed process with arrival rate $\lambda$ and send sequence
$\mathbf{p}$, and let
$\mathcal{R}^{Y}=\\{t\mid\mathbf{stuck}^{Y}(t)=\emptyset\\}$. By the coupling
of $Y$ and $T$ from Lemma 23, with probability $1$, $\mathcal{R}^{Y}$ is
finite. Finally, by the coupling of $X$ and $Y$ from Observation 22, it
follows that with probability $1$, $\mathcal{R}^{X}$ is finite. ∎

In order to make the proof of Theorem 5 more convenient, we first re-state the
definition of LCED.

See 4

See 5

###### Proof.

Suppose that $\mathbf{p}$ is not LCED. Fix $\lambda\in(0,1)$. Let $X$ be a
backoff process with arrival rate $\lambda$ and send sequence $\mathbf{p}$. We
split the analysis into cases depending on which case of Definition 4 fails.

Case 1 (iii) fails: By definition, since (iii) fails, there is no real number
$C>0$ such that, for all but finitely many $j$, $\log(1/p_{j})\leq Cj$. So for
all $C>0$, there are infinitely many $j$ such that $\log(1/p_{j})>Cj$, which
implies $p_{j}<\exp(-Cj)$. Taking $C=\log(2/(\lambda p_{0}))$, we conclude
that there are infinitely many $j$ such that $p_{j}<(\lambda p_{0}/2)^{j}$.
Lemma 7 implies that $X$ is unstable.

Case 2 (iii) holds but (i) fails: By definition, since (i) fails, there is an
$\eta>0$ such that for all $c>0$, for all but finitely many $n$, $|\\{j\leq
n\colon p_{j}\leq c\\}|>\eta n$. Taking $c=p_{*}(\lambda p_{0},\eta,\nu)$ for
positive $\nu$, we conclude that there is an $\eta>0$ such that for all
$\nu>0$ and for all but finitely many $n$, $|\\{j\leq n\colon p_{j}\leq
p_{*}(\lambda p_{0},\eta,\nu)\\}|>\eta n$.

Let $\mathbf{p}^{\prime}$ be the send sequence derived from $\mathbf{p}$ by
setting $p^{\prime}_{0}=1$ and, for every positive integer $j$,
$p^{\prime}_{j}=p_{j}$.

Given the $\eta>0$ that we have just identified, our goal will be find $\nu>0$
such that $\mathbf{p}^{\prime}$ is $(\lambda p_{0},\eta,\nu)$-suitable
(Definition 14). To achieve this, we need to show that we can choose $\nu>0$
such that, for all but finitely many $n$, $\nu^{n}<p_{n}=p^{\prime}_{n}$.

Here we will use the fact that (iii) holds. Since $\log(1/p_{j})=O(j)$, there
exists $C>0$ such that for all but finitely many $j$, $1/p_{j}<e^{Cj}$. So
taking $\nu=e^{-C}<1$ we have that for all but finitely many $j$,
$p_{j}>\nu^{j}$. So we have now shown that $\mathbf{p}^{\prime}$ is $(\lambda
p_{0},\eta,\nu)$-suitable.

Let $X^{\prime}$ be a backoff process with arrival rate $\lambda p_{0}$ and
send sequence $\mathbf{p}^{\prime}$. Let
$\mathcal{R}^{X^{\prime}}=\\{t\mid\mathbf{balls}^{X^{\prime}}(t)=\emptyset\\}$.
By Corollary 26, with probability $1$, $\mathcal{R}^{X^{\prime}}$ is finite.

Finally, let $X$ be a backoff process with arrival rate $\lambda$ and send
sequence $\mathbf{p}$. Let
$\mathcal{R}^{X}=\\{t\mid\mathbf{balls}^{X}(t)=\emptyset\\}$. By the coupling
of $X$ and $X^{\prime}$ from Observation 21, with probability $1$,
$\mathcal{R}^{X}$ is finite. Hence, the process $X$ is transient, so it is
unstable.

Case 3 (iii) holds but (ii) fails: In this case $\log(1/p_{j})=o(j)$ so the
result follows from Corollary 9. Here is an argument that
$\log(1/p_{j})=o(j)$. Since (iii) holds but (ii) fails, there is no infinite
subsequence $(p_{\ell_{1}},p_{\ell_{2}},\dots)$ that satisfies
$\log(1/p_{\ell_{x}})=\Omega(\ell_{x})$. Thus for every infinite subsequence
$(p_{\ell_{1}},p_{\ell_{2}},\dots)$ and for every $C>0$, infinitely many $n$
satisfy $\log(1/p_{\ell_{n}})<C\ell_{n}$. This implies that for all $C>0$ and
all infinite subsequences $(p_{\ell_{1}},p_{\ell_{2}},\dots)$, some $n$ has
$\log(1/p_{\ell_{n}})<C\ell_{n}$. Hence, for all $C>0$ there is no infinite
subsequence $(p_{\ell_{1}},p_{\ell_{2}},\dots)$ that satisfies
$\log(1/p_{\ell_{x}})\geq C\ell_{x}$. Finally, for all $C>0$, there is a
$j_{C}$ such that for all $j\geq j_{C}$, $\log(1/p_{j})<Cj$ so
$\log(1/p_{j})=o(j)$, as required. ∎

We can now use Theorem 5 to derive the other theorems stated in the
introduction.

See 2

###### Proof.

We prove that $\mathbf{p}$ is not LCED and use Theorem 5. Suppose for
contradiction that $\mathbf{p}$ is LCED. Let $c>0$ be such that $p_{j}\geq c$
for infinitely many values of $j$; by (i) of Definition 4 applied with any
$\eta>0$, such a $c$ must exist. Let $(p_{\ell_{1}},p_{\ell_{2}},\dots)$ be
the infinite exponentially-decaying subsequence of $\mathbf{p}$ guaranteed by
(ii), and observe that there exists $i_{c}$ such that $p_{\ell_{i}}<c$ for all
$i\geq i_{c}$. Since $\mathbf{p}$ is monotonically non-increasing, it follows
that for all $j\geq i_{c}$ we have $p_{j}\leq p_{i_{c}}\leq c$, giving a
contradiction. ∎

See 3

###### Proof.

We observe that $\mathbf{p}$ is not LCED and use Theorem 5. In particular, we
will observe that item (i) in the definition of LCED cannot be satisfied for
$\eta=1/2$. Item (i) implies that there is a $c>0$ such that for infinitely
many $n$, $m_{\mathbf{p}}(n)>c$. But this is inconsistent with
$m_{\mathbf{p}}(n)=o(1)$.

∎

## References

  * [1] IEEE standard for information technology-telecommunications and information exchange between systems local and metropolitan area networks — specific requirements — part 11: Wireless LAN medium access control (MAC) and physical layer (PHY) specifications.  IEEE Standard 802.11-2016 (Revision of IEEE Std 802.11-2012, pages 1–3534, 2016.
  * [2] Norman Abramson.  THE ALOHA SYSTEM.  In Norman Abramson and Franklin Kuo, editors, Computer-Communication Networks, pages 281–285. Prentice-Hall, 1973.
  * [3] Hesham Al-Ammal, Leslie Ann Goldberg, and Philip D. MacKenzie.  An improved stability bound for binary exponential backoff.  Theory of Computing Systems, 34(3):229–244, 2001.
  * [4] David Aldous.  Ultimate instability of exponential back-off protocol for acknowledgment-based transmission control of random access communication channels.  IEEE Transactions on Information Theory, 33(2):219–223, 1987.
  * [5] Mark Allman, Vern Paxson, and Ethan Blanton.  TCP congestion control.  RFC, 5681:1–18, 2009.
  * [6] Michael A. Bender, Tsvi Kopelowitz, William Kuszmaul, and Seth Pettie.  Contention resolution without collision detection.  In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 105–118. ACM, 2020\.
  * [7] Haimin Chen, Yonggang Jiang, and Chaodong Zheng.  Tight trade-off in contention resolution without collision detection.  In Avery Miller, Keren Censor-Hillel, and Janne H. Korhonen, editors, PODC ’21: ACM Symposium on Principles of Distributed Computing, pages 139–149. ACM, 2021.
  * [8] Bogdan S. Chlebus.  Randomized communication in radio networks.  CoRR, abs/1801.00074, 2018.  URL: http://arxiv.org/abs/1801.00074.
  * [9] AWS documentation.  Error retries and exponential backoff in AWS.  URL: https://docs.aws.amazon.com/general/latest/gr/api-retries.html.
  * [10] Google Drive documentation.  Handle errors and improve performance.  URL: https://developers.google.com/drive/api/guides/handle-errors?hl=en#exponential-backoff.
  * [11] Anthony Ephremides and Bruce Hajek.  Information theory and communication networks: an unconsummated union.  IEEE Transactions on Information Theory, 44(6):2416–2434, 1998\.
  * [12] Leslie Ann Goldberg, Mark Jerrum, Sampath Kannan, and Mike Paterson.  A bound on the capacity of backoff and acknowledgment-based protocols.  SIAM Journal on Computing, 33(2):313–331, 2004.
  * [13] Leslie Ann Goldberg, Philip D. MacKenzie, Mike Paterson, and Aravind Srinivasan.  Contention resolution with constant expected delay.  Journal of the ACM, 47(6):1048–1096, 2000.
  * [14] Jonathan Goodman, Albert G. Greenberg, Neal Madras, and Peter March.  Stability of binary exponential backoff.  Journal of the ACM, 35(3):579–602, 1988.
  * [15] Albert G. Greenberg, Philippe Flajolet, and Richard E. Ladner.  Estimating the multiplicities of conflicts to speed their resolution in multiple access channels.  Journal of the ACM, 34(2):289–325, 1987.
  * [16] Johan Håstad, Frank T. Leighton, and Brian Rogoff.  Analysis of backoff protocols for multiple access channels.  SIAM Journal on Computing, 25(4):740–774, 1996.
  * [17] Maurice Herlihy and J. Eliot B. Moss.  Transactional memory: Architectural support for lock-free data structures.  In Proceedings of the 20th Annual International Symposium on Computer Architecture, San Diego, CA, USA, May 1993, pages 289–300. ACM, 1993\.
  * [18] Frank P. Kelly and Iain M. MacPhee.  The number of packets transmitted by collision detect random access schemes.  Annals of Probability, 15:1557–1568, 1987.
  * [19] Robert Metcalfe and David R. Boggs.  Ethernet: Distributed packet switching for local computer networks.  Communications of the ACM, 19(7):395–404, 1976.
  * [20] Michael Mitzenmacher and Eli Upfal.  Probability and Computing: Randomized Algorithms and Probabilistic Analysis.  Cambridge University Press, 2005.
  * [21] Jeannine Mosely and Pierre Humblet.  A class of efficient contention resolution algorithms for multiple access channels.  IEEE Transactions on Communications, 33(2):145–151, 1985.
  * [22] Prabhakar Raghavan and Eli Upfal.  Stochastic contention resolution with short delays.  SIAM Journal on Computing, 28(2):709–719, 1998.
  * [23] Ravi Rajwar and James R. Goodman.  Speculative lock elision: enabling highly concurrent multithreaded execution.  In Yale N. Patt, Josh Fisher, Paolo Faraboschi, and Kevin Skadron, editors, Proceedings of the 34th Annual International Symposium on Microarchitecture, Austin, Texas, USA, December 1-5, 2001, pages 294–305. ACM, 2001.
  * [24] Lawrence G. Roberts.  ALOHA packet system with and without slots and capture.  ACM SIGCOMM Computer Communication Review, 5(2):28–42, 1975\.
  * [25] Devavrat Shah and Jinwoo Shin.  Randomized scheduling algorithm for queueing networks.  Annals of Applied Probability, 22:128–171, 2012.
  * [26] Devavrat Shah, Jinwoo Shin, and Prasad Tetali.  Medium access using queues.  In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, pages 698–707. IEEE Computer Society, 2011.