# Time and Energy Efficient Contention Resolution in Asynchronous Shared
Channels

Gianluca De Marco444 Dipartimento di Informatica, University of Salerno,
Italy. Email<EMAIL_ADDRESS> Dariusz R. Kowalski333School of Computer
and Cyber Sciences, Augusta University, GA, USA. Email<EMAIL_ADDRESS>Grzegorz Stachowiak222 Institute of Computer Science, University of Wrocław,
Poland. Email<EMAIL_ADDRESS>
###### Abstract

A shared channel (also called a multiple access channel), introduced nearly 50
years ago, is among the most popular and widely studied models of
communication and distributed computing. In a nutshell, a number of stations,
independently activated over time, is able to communicate by transmitting and
listening to a shared channel in discrete time slots, and a message is
successfully delivered to all stations if and only if its source station is
the only transmitter at a time. Despite a vast amount of work in the last
decades, many fundamental questions remain open in the realistic situation
where stations do not start synchronously but are awaken in arbitrary times
(called dynamic or asynchronous scenario). What is the impact of an
asynchronous start on channel utilization? How important is the
knowledge/estimate of the number of contenders? Could non-adaptive protocols
be asymptotically as efficient as adaptive ones? In this work we present a
broad picture of results answering the abovementioned questions for the
fundamental problem of Contention resolution, in which each of the contending
stations needs to broadcast successfully its message.

We show that adaptive algorithms or algorithms with the knowledge of the
contention size $k$ achieve a linear $O(k)$ message latency even if the
channel feedback is restricted to simple acknowledgements in case of
successful transmissions and in the absence of synchronization. This
asymptotically optimal performance cannot be extended to other settings: we
prove that there is no non-adaptive algorithm without the knowledge of
contention size $k$ admitting latency $o(k\log k/(\log\log k)^{2})$. This
means, in particular, that coding (even random) with acknowledgements is not
very efficient on a shared channel without synchronization or an estimate of
the contention size. We also present a non-adaptive algorithm with no
knowledge of contention size that almost matches the lower bound on latency.

Finally, despite the absence of a collision detection mechanism, we show that
our algorithms are also efficient in terms of energy, understood as the total
number of transmissions performed by the stations during the execution.

Key words— shared channel, multiple-access channel, contention resolution,
distributed algorithms, randomized algorithms, lower bound, dynamic
communication, adaptive and oblivious adversaries

##  1 Introduction

A shared channel, also called a multiple access channel, is one of the
fundamental communication models considered in the literature. It allows many
autonomous computing entities to communicate over a shared medium, and the
main challenge is how to efficiently resolve collisions occurring when more
than one entity attempts to access the channel at the same time. Despite a
vast amount of work, some fundamental questions about channel utilization have
remained open for decades. What is the impact of asynchrony among the starting
times of the stations? How important is the knowledge/estimate of the number
of contenders? Could non-adaptive protocols or random codes be asymptotically
as efficient as adaptive protocols? This paper attempts to answer these
questions by separating the impact of the abovementioned characteristics into
two classes: those allowing asymptotically optimal channel utilization and
those which incur a substantial overhead.

The formal model considered in this paper is the one commonly taken as the
basis for theoretical studies on multiple access channels (cf. the surveys by
Gallager [18] and Chlebus [14]). In what follows we overview it, paying
special attention to the particular settings of this paper.

#### Stations.

A set of $k$ stations are connected to the same multi-point transmission
medium. The stations are anonymous, that is, they have no identification label
(ID) to uniquely distinguish them. There is no central control: every station
acts autonomously by means of a distributed algorithm. At the beginning, all
the stations are sleeping. A sleeping station does not send nor receive any
message on the channel. Each station can be activated (and thus become active)
at any time with the task of sending a data packet. The activation times do
not depend on algorithm’s execution and are totally determined by an adversary
that will be defined next. A station is active from the activation time until
its termination, which means going back into a permanent sleeping mode. Unlike
the activation time, termination is decided by the algorithm.

#### Communication.

Time is divided into discrete synchronous rounds (also called time steps or
time slots). In each round, an active station can either send a message or
listen to the channel. A message is just the packet itself, although in our
adaptive algorithm we allow also some stations to send a one-bit message as
coordinating information (also called control message or control bit, both in
theoretical models and technological applications).

An active station that is not transmitting in a round, is implicitly assumed
to be listening in that round. A station transmits successfully its message at
a given round if and only if it is the only transmitter in that round: all the
other active stations are listening (and therefore receive the message).
Namely, if $m\leq k$ stations transmit at the same round, then the result of
the transmission in this round depends on the parameter $m$ as follows:

  * •

If $m=0$, the channel is silent and no packet is successfully transmitted;

  * •

If $m=1$, the packet owned by the singly transmitting station is successfully
transmitted on the channel and therefore received by all the other active
stations;

  * •

If $m>1$, simultaneous transmissions interfere with one another (we say that a
collision occurs) and as a result no message is received by the other
stations.

#### Feedback.

In the setting without collision detection adopted in this paper, no special
signal is perceived in the case of collision, making therefore impossible, for
a station listening to the channel, to distinguish between an occurred
collision and the case where no station transmits. (By contrast, in a
collision detection setting, not considered in this paper, the channel elicits
a feedback in case of collision, allowing to deduce that two or more stations
tried to transmit at the same time.) The only feedback a station can sense is
when it actually transmits successfully, in which case it gets an
acknowledgement.

#### Contention resolution problem.

Each active station possesses a packet, which can be transmitted in a single
time slot. Packets are not assumed to be distinguishable, so they cannot be
used to identify the stations. The aim is to let each of the $k$ stations to
transmit successfully its packet. The task is considered to be accomplished
when all packets are successfully transmitted and all stations are switched
off with all their functions permanently disabled.

#### Algorithms.

We seek randomized algorithms that allow every station to transmit
successfully its packet, regardless of the activation times. Note that the
choice of randomized solutions is forced since in the absence of unique ID’s
there is no deterministic way of breaking the symmetry among the identical
stations on the shared channel.

For each station, a randomized algorithm specifies two things: ($a$) the
probability of transmission for each round of its local clock and ($b$) the
message to be transmitted in that round. In non-adaptive algorithms the
probability of transmission depends only on the local round number (we do not
assume independence of these probabilities across rounds), and the message is
simply the data packet initially assigned to the station. In adaptive
algorithms, both the probability of transmission and the message to be sent in
round $i$ depend on the history of successful transmissions received until
round $i$ (messages collected so far as well as the rounds at which they were
received).

In the non-adaptive setting, a station automatically leaves the system
(switches off) once it gets the acknowledgement that its packet has been
successfully transmitted. Notice that this is a straight consequence of the
definition above. Indeed, in a non-adaptive algorithm there is no point in
keeping alive a station after its successful transmission, as it cannot
influence in any way the behaviour of the other stations. On the contrary, in
our adaptive algorithm some stations, in order to coordinate the protocol,
reserve the right to remain active some time after their successful
transmission.

In particular, the adaptive algorithm considered in this paper allows stations
to send either the packet itself, or (alternatively) a one-bit message as a
coordination/control information. Similar adaptive settings allow to append a
constant number of bits to each packet (e.g. [28]) or to send any packet-sized
message, besides the original packet itself (e.g. [4, 10]).

A contention resolution algorithm is a distributed algorithm that schedules
the transmissions in station’s local time for each of the $k$ participating
stations guaranteeing that every station eventually transmits successfully
(i.e., without interfering with other stations) on the channel, and switches
off.

#### Static vs dynamic scenarios.

Most of the literature on the contention resolution problem produced so far
either assumed the (simplified) static situation in which the $k$ stations are
all activated at the very beginning (and therefore start simultaneously their
transmitting schedules) [4, 12, 16, 25, 23, 24, 31] or that the activation
times are restricted to statistical (e.g., when packet arrivals are determined
by a Poisson distribution) or adversarial-queueing models [7, 15, 22, 32, 35,
37].

Inspired by the inherently decentralized nature of the multiple access model,
in this paper we focus on the more general and realistic  dynamic scenario, in
which stations awaken (i.e., start their local executions of a distributed
algorithm) in arbitrary times, i.e., the sequence of activation times, also
called a wake-up schedule, is totally determined by an adversary (see the next
paragraph for a formal definition). This scenario, sometimes also called
asynchronous, reflects the more realistic situation in which the stations are
geographically far apart or totally independent, and consequently each
activation time is locally determined and cannot be known or even
approximately predicted by other stations. Throughout the paper, “switched
on”, “activated”, “woken up” and their derived terms are used interchangeably
to mean the action, controlled by an adversary, by which a station wakes up
and starts executing the algorithm.

#### Adversaries.

A dynamic scenario could be caused by an adaptive or an oblivious adversary.
The former can decide, online during the execution, what station to wake-up
and when, knowing the algorithm code and the computation history but not the
future randomness. The latter knows only the algorithm’s code and has to fix
its decision on what station to wake up and when before the execution starts
(without knowing the random choices made by the stations). Clearly, the
adaptive adversary is stronger than the oblivious one, in the sense that it
could mimic any strategy of the oblivious adversary and additionally use
online strategies, based on the knowledge of the computation history, that may
deteriorate the algorithm’s performance even further.

#### Timing.

Although the communication is in synchronous rounds (i.e., the clocks of all
the stations tick at the same rate) there is no global clock and no system-
based synchronization: each station starts its local clock in the round in
which it wakes up, without knowing anything about the round numbers ticked by
the other clocks. We conventionally assume that a station is activated in
round 0 of its local clock and can start transmitting since round 1.

It is interesting to note that in the static model there is no distinction
between the model with a global clock and that without it. Indeed, one can
assume that a global clock is always available in that model: all the stations
are activated simultaneously and therefore their clocks, starting at the same
time, will always tick the same round numbers. In this sense, the dynamic
model considered in this work is more general and challenging than the static
one.

#### Metrics.

In this paper we measure the efficiency of the algorithms both in terms of
time complexity and energy consumption. In a dynamic scenario when each
station can be woken up at any time, the activation times can be arbitrarily
distant from each other, therefore there is no straight way to correctly judge
the time efficiency of an algorithm such as simply counting rounds from start
to end (as it would be in the static model, where all stations are activated
at once). A natural criterion is to consider the latency of the algorithm.
First we define the latency of a station as the number of rounds necessary for
the station to transmit successfully, measured since its activation time.
Then, the maximum of these values, calculated among all $k$ stations, provides
the latency of the algorithm.  Concerning the energy consumption, the
algorithm’s efficiency will be evaluated in terms of total number of
transmissions (broadcast attempts) performed by all stations executing the
protocol. Both latency and energy cost will be analyzed against a worst-case
adaptive adversary: the upper bounds will hold against any strategy of the
(online) adaptive adversary. Our lower bound will hold even for a weaker
oblivious adversary: the formula holds even if the adversary fixes its worst-
case wake-up pattern prior to the execution.

All our asymptotic upper bounds are to be understood as high probability
bounds, that is, they hold with high probability (in short: whp). We say that
an event for an algorithm holds whp, when for a predefined parameter $\eta>0$,
the parameters of the algorithm can be chosen, so that for any contention size
$k$ the event holds with probability at least $1-1/k^{\eta}$. In the
intermediate steps of analysis, we will sometimes need to use the notion of
whp not only with respect to the pre-assumed parameter $\eta$; in such a case
we will say more specifically that an event occurs “whp $1-1/k^{\lambda}$”,
for some $\lambda>0$. Parameter $\lambda$ will typically be slightly higher
than $\eta$, so that at the end we could get the final result with the sought
probability at least $1-1/k^{\eta}$.

###  1.1 Previous work and our contribution

Contention resolution on a shared channel has a very long and rich history,
including communication tasks, scheduling, fault-tolerance, security, energy,
game-theoretical and many other aspects,

The first theoretical papers on channel contention resolution date back to the
70’s and considered mainly solutions either for the static scenario or the
dynamic scenario restricted to when the activation times follow some known
probability distribution. The common assumption is that the number of stations
connected to the shared medium is very large with respect to the actual number
of stations that can be involved in the contention. In this case the simple
time-division multiple access (TDMA), which assigns a different round to each
of the potential transmitters, would become very inefficient.

Abramson [1] introduced the first random-access technique, called the Aloha
system, that, contrary to TDMA, instead of avoiding collisions, allows
retransmission of the data packets when collisions occur. Soon after, Roberts
[42] designed a method to divide the continuous time into discrete time slots
by allowing the stations to agree on slot boundaries (slotted Aloha system).
These earliest works focused on queueing models in which each station
maintains a queue of data packets to be sent that arrive according to
independent Poisson processes. The basic idea was ingeniously simple: when a
new packet arrives at a station, it is immediately transmitted and, if a
collision is detected, it is retransmitted at a randomly selected future time.
The main issue with any Aloha-type approach was the instability: eventually
the system reaches a situation where the number of stations involved in
retransmissions tends to infinity, while the throughput tends to zero [11].

A novel category of protocol schemes, called splitting algorithms, introduced
in the late 70’s independently by Capetanakis [12], Hayes [27], and Tsybakov
and Mikhailov [43], allowed to control the random retransmissions in such a
way to avoid many chaotic situations encountered in the previous solutions.
These algorithms were the first to be based on a collision-resolution approach
aiming at recursively “resolving” collisions whenever they occur. The idea was
to split the set of colliding stations into subsets, only one of which
transmits in the subsequent time slot, while the other stations defer. If
another collision occurs, a further splitting into subsets is performed. If in
a time slot no station transmits or if exactly one station transmits in it,
the splitting stops.

Alongside the queueing models discussed above, a common setting, which is also
the one adopted in the present paper, assumed that each new packet arrives at
a new station, rather than at a backlogged one. In this context, the problem
is to let each station to transmit a single message rather than a queue of
messages. This is very realistic whenever the number of stations is much
larger than the arrival rate (which is the scenario under which TDMA is very
inefficient), so that new arrivals at backlogged stations are negligible.
Moreover, from a theoretical point of view, this assumption captures the real
essence of multiaccess communication in that it assures a good approximation
of a large number of systems with arbitrary assumptions about buffering of
newly arriving packets (see e.g. Section 4.2 in [11].) All of the following
results assume, as the present paper, this setting with a single packet per
station.

Under this setting, analysis and refinements of the splitting algorithms
produced efficient solutions for the static scenario, i.e. when $k$ stations
are activated simultaneously. The first rigorous analysis was made by Massey
[34] who showed that the original splitting algorithm can solve a contention
among $k$ stations in $2.8867k$ time slots in expectation, provided that $k$
is known. Greenberg, Flajolet and Ladner [23] and Greenberg and Ladner [24]
presented an algorithm working in $2.134k+O(\log k)$ expected rounds without
any a priori knowledge of the number $n$ of contenders. This was called a
hybrid algorithm in that it first produces an estimate of $k$ (which gives
rise to the $O(\log k)$ additive term) and then uses a refinement of the
original splitting algorithm to finally resolve the contention. All of the
above solutions, being based on splitting algorithms, are adaptive and require
a collision detection mechanism. The same asymptotic (optimal) bound for the
static scenario has been obtained even without collision detection and with a
non-adaptive algorithm that also ignores any initial knowledge about the
contention size $k$ [26, 19, 4].  This shows that in the static model, i.e.,
when all the packets arrive at the same time, there is no asymptotic
difference in the time complexity between adaptiveness and non-adaptiveness,
even in the absence of any a priori knowledge about channel contention. In the
dynamic scenario, considered in this paper, Bender et al. [8] designed an
adaptive algorithm with collision detection that, without any given bound on
parameter $k$, exhibits constant throughput, linear latency and
$O(\log\log^{*}k)$ expected transmissions per station. More recently Bender et
al. [10] proved that constant throughput and polylogarithmic transmissions can
be achieved, with high probability, by adaptive algorithms even without
collision detection.

synchrony | C.D. | setting | latency | energy
---|---|---|---|---
u. b. | l. b. | u. b. | l. b.
static | no |  non-adaptive and $k$ unknown |  $O(k)$ [26, 19, 4] | $\Omega(k)$ |  $\Omega(k\log^{2}k)$ [26, 19, 4] | $\Omega(k)$
dynamic | yes |  adaptive and $k$ unknown |  $O(k)$ [8] | $\Omega(k)$ |  $O(\log(\log^{*}k))$ [8] | $\Omega(k)$
no |  non-adaptive and $k$ known | $\boldsymbol{O(k)}$ | $\Omega(k)$ | $\boldsymbol{O(k\log k)}$ | $\Omega(k)$
no |  non-adaptive and $k$ unknown | $\boldsymbol{O\left(k\frac{\ln^{2}k}{\ln\ln k}\right)}$ | $\boldsymbol{\Omega\left(k\frac{\log k}{(\log\log k)^{2}}\right)}$ | $\boldsymbol{O(k\log^{2}k)}$ | $\Omega(k)$
no |  adaptive and $k$ unknown | $\boldsymbol{O(k)}$ | $\Omega(k)$ | $\boldsymbol{O(k\log^{2}k)}$ | $\Omega(k)$
Table 1: Currently best results on latency and energy in randomized contention
resolution. Collision detection is abbreviated “C.D.”, while “u. b.” and “l.
b” respectively stand for upper bound and lower bound. Results from this paper
are shown in bold. A lower bound $\Omega(k)$ is inevitable, both for latency
and energy, to have $k$ successful transmissions.

#### Our contribution.

We pursue the study on contention resolution further by considering both
adaptive and non-adaptive protocols in the general setting when stations
awaken at arbitrary times and in the severe model without collision detection.
The wake-up times are determined by a worst-case adversary. Upon waking up,
each station starts its protocol from the beginning and a global clock is not
available (an upper bound for the case with global clock has been given for
the deterministic setting [17]). With respect to the preliminary version [33],
the present work provides the following significant additions. The analysis of
the algorithms have been improved to work against a stronger adaptive
adversary, while the lower bound has been strengthen to deal even if the
activation times of the stations are scheduled by a much weaker oblivious
adversary. We consider also transmission energy efficiency, in particular
improving the expected total number of transmissions of our adaptive algorithm
from $\Omega(k^{2})$ to $O(k\log^{2}k)$. Finally, we formulate several
challenging open directions in the field of shared channel communication.

Our results can be summarized as follows (see Table 1 for a comparison with
the static model in the most severe settings, i.e. non-adaptivity without
collision detection and with $k$ unknown).

  * •

If a linear upper bound on $k$ is given a priori to the stations or the
protocol is adaptive, then the contention resolution can be done optimally (in
asymptotic sense); we provide two corresponding algorithms working whp with
latency $O(k)$, c.f., Theorem 3.1 in Section 3 and Theorem 6.3 in Section 6,
respectively.

  * •

If the protocol is non-adaptive and no linear upper bound is known on
parameter $k$, then we show a time complexity separation with the previous
cases by proving that there is no non-adaptive randomized algorithm, without
the knowledge of any linear upper bound on $k$, achieving $o\left(k\frac{\log
k}{(\log\log k)^{2}}\right)$ latency whp, c.f., Theorem 4.1 in Section 4.

  * •

We also give a non-adaptive algorithm, ignoring any linear upper bound on $k$,
i.e., an universal random code, with latency $O(k\log^{2}k)$ whp, which almost
match our lower bounds for the same setting (see Theorem 5.1 in Section 5).
Additionally we show that if we allow the stations to switch-off upon an
acknowledgment then this algorithm/code guarantees even a better latency:
$O\left(k\frac{\log^{2}k}{\log\log k}\right)$ whp, c.f., Theorem 5.2 in
Section 5.

All our upper bounds (achieved by algorithms) hold for an adaptive adversary,
while the lower bound holds even for a weaker oblivious adversary. In view of
our (almost) tight formulas, it implies that the power of the adversary does
not (substantially) influence the complexity of the contention resolution
problem.

Our contribution implies that, in contrast with what happens in the static
model, in the dynamic counterpart there is a separation, in terms of time
complexity (latency), between non-adaptive algorithms ignoring $k$ and
algorithms that either are adaptive or know parameter $k$. It also implies a
separation between the static and dynamic models, in case of non-adaptive
algorithms without a good estimate of the number $k$ of contenders.  It is
interesting to note that, compared with the Bender et al. [8] protocol, our
adaptive algorithm exhibits the same optimal performance on latency even in
the more severe setting without collision detection.

Finally, all of our algorithms, despite the absence of a collision detection
mechanism, are also efficient in terms of the total number of transmissions
performed by the stations during the execution. Namely, the adaptive algorithm
spends $O(k\log^{2}k)$ broadcast attempts, c.f., Theorem 6.4, while our non-
adaptive solutions, with and without knowledge of $k$, have an energy cost
respectively $O(k\log k)$ and $O(k\log^{2}k)$ whp, see Theorems 3.2 and 5.3.

Given the generality of the shared channel as a symmetry breaking model, we
believe that our contribution and newly developed techniques could shed light
on the complexity of other problems in distributed computing.

#### Our approach and technical contribution.

We build our approach on the following four findings.

The first and key finding is that in order to utilize the channel efficiently
against some non-synchronized sequence of activation times, any “universally
efficient” (i.e., efficient for any contention size) non-adaptive contention
resolution algorithm has to schedule probabilities of transmissions in the
first $\Theta(k\log k/(\log\log k)^{2})$ rounds in such a way that they sum up
to $\Omega(\log k/\log\log k)$ (see Lemma 4.2 in Section 4). (Recall that we
do not require from the algorithms that these probabilities are independent
over the rounds, which make our lower bound on latency more general.) This was
not the case for previous analysis of simplified static scenarios (i.e., when
stations start the protocol at the same time) or simpler problems such as
wake-up (i.e., waiting for the first successful transmission). We later show
that some slightly more subtle selection of activation times pumps-up the sum
requirement to $\Omega(\log^{2}k/(\log\log k)^{2})$ over the first
$\Theta(k\log k/(\log\log k)^{2})$ rounds (see Lemma 4.5). This is sufficient
to prove the corresponding superlinear lower bound on latency (see Theorem
4.1).

Second, we found out that such an effect does not hold if we know some linear
upper bound on the number of contenders, since slowly increasing
probabilities, starting from the level of $1/k$ and ending at $(\log k)/k$,
guarantees the existence of many rounds at which the sum of probabilities of
the alive stations is smaller than $1$, regardless of how the activation times
are located (cf., Lemmas 3.2 to 3.5 in Section 3). This, together with the
property that the transmission probability of a single station is at least
$(\log k)/k$, implies that each station succeeds in linear time with high
probability (cf., Lemma 3.1 and the final proof of Theorem 3.1). Note that in
this case the sum of transmission probabilities of a station during the first
$\Theta(k)$ rounds is also $\Omega(\log k)$, however the knowledge of $k$ (or
its linear upper bound) allows the algorithm to schedule them in such a way
that the pumping-up technique from the lower bound mentioned above (for non-
adaptive solutions without knowledge of $k$) does not work.

Third, in Section 6 we will show how the adaptiveness can also moderate the
effect of the pumped-up sums, as it allows to elect a leader quickly using
known solutions to the wake-up problem. The leader could then be used to
coordinate the transmissions of the synchronized stations. The main
challenging part is to manage such a coordination among different algorithmic
components (wake-up and uniform selection of a subset of already synchronized
stations) on an asynchronous channel without accessing to a global clock and
with no a priori information about the number of participating stations. We
overcome these obstacles by using a few types of modes and a small number of
transmissions.

Finally, in the most severe setting of non-adaptive algorithms with no a
priori knowledge, sub-linearly decreasing probabilities allow to find a linear
fraction of rounds with $O(1)$ sum of transmission probabilities, cf., Lemmas
5.2 to 5.4 in Section 5. This, together with the fact that a station itself
transmits with sub-linearly decreasing probability $(\log j)/j$ in round $j$,
guarantees successful transmissions with high probability in a slightly
overlinear time period of $O(k\log^{2}k/(\log\log k))$ rounds.

###  1.2 Related works

An interesting related line of research studies the contention resolution
problem in presence of adversarial jamming. Awerbuch et al. [6] as well as
Richa et al. [38, 39, 40] studied jamming in multiple access channels in an
adversarial setting when jamming is bounded within any sufficiently large
fraction of the time. Anantharamu et al. [3] considered the setting with a
dynamic arrivals of packets subject to particular injection rates and jamming
rates. For an account of the literature on adversarial models the interested
reader can consult Richa et al. [41]. For arbitrary jamming models we refer
the reader also to the works by Alistarh et al. [2] and Gilbert et al. [20].
Energy efficiency approaches can be found in [21]. More recently, the setting
where $d$ slots can be jammed by an adaptive adversary has received attention.
In such a situation, when collision detection is available, very efficient
algorithms, both in terms of throughput and energy, have been presented in [9,
13]. Interestingly, Bender et al. [10] showed a separation between the models
with and without collision detection, proving that no constant throughput
algorithm can be achieved in presence of jamming when collision detection is
not available.

As for the energy consumption, some papers also measured the efficiency of
contention resolution analyzing the number of channel accesses, including not
only the broadcast attempts, but also the time spent by the stations listening
to the channel. In this context, for the model with collision detection,
Bender et al. [8] presented a randomized algorithm with expected constant
throughput and only $O(\log(\log^{*}N))$ channel accesses in expectation.

###  1.3 Structure of the paper.

We start with Section 2 presenting some conventions and notations that will be
used throughout the paper. The next three sections will be devoted to non-
adaptive algorithms. Namely, in Section 3 we give our optimal non-adaptive
solution with known contention size; in Section 4 we show our lower bound for
non-adaptive algorithms unaware of the contention size; and in Section 5 we
give an almost optimal non-adaptive algorithm for unknown contention size.
Finally, in Section 6 we present our optimal adaptive solution for unknown
contention size.

##  2 Technical preliminaries

###  2.1 Conventions and notation

The activity of every station is articulated into synchronous rounds counted
by a local clock. Each station can measure the time only on the base of this
local numbering, without having any information on the clocks of other
stations. By convention, we assume that a station is activated at round 0 of
its local clock and can start its transmitting schedule from the next round:
i.e., at each round $1,2,3,\ldots$ a station can decide the probability of
transmission.111The probabilities of transmission are not necessarily
independent — we follow the general definition of randomized algorithms being
a random distribution over deterministic algorithms. Therefore, in case of
adaptive algorithms, the probabilities may depend also on the history of the
channel feedback.

The example given in Figure 1 shows the lack of synchrony among the clocks of
stations with different wake-up times: the first round of $u_{4}$ corresponds
to the third round of $u_{2}$ and $u_{3}$ (that were activated simultaneously)
and to the seventh round of $u_{1}$.

Although there is no global time accessible to the stations, in the analysis
we will need a reference clock (not visible to the stations) that allows us to
consider the behaviour of all the stations involved in the computation at a
given moment. For example, in Figure 1 we could start a reference clock
synchronously with $u_{1}$’s clock and say that at time $5$ (of the reference
clock) there are three active stations: $u_{1}$, $u_{2}$ and $u_{3}$.

$u_{1}$’s local rounds: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 …
---|---|---|---|---|---|---|---|---|---|---
$u_{2}$’s local rounds: |  |  |  |  | 0 | 1 | 2 | 3 | 4 | 5 …
$u_{3}$’s local rounds: |  |  |  |  | 0 | 1 | 2 | 3 | 4 | 5 …
$u_{4}$’s local rounds: |  |  |  |  |  |  | 0 | 1 | 2 | 3 …
|  |  | $\vdots$ |  |  |  |  |  |  |
Figure 1: Lack of synchrony among the clocks.

For any time $t$ of a given reference clock, we denote by $\hat{A}[t]$ the set
of stations activated until time $t$. The transmission probability assigned by
the protocol to a station $v\in\hat{A}[t]$ at time $t$ will be denoted by
$q_{v}[t]$. Some stations may however cease to be active during the protocol,
therefore we use $A[t]\subseteq\hat{A}[t]$ to designate the set of stations
that are still active at time $t$.

Moreover, we define the sum of transmission probabilities at time $t$ as
follows:

$\sigma[t]=\sum_{u\in A[t]}q_{u}[t]\ .$

The notation introduced so far will be used both for adaptive and non-adaptive
algorithms.

Let us now introduce some definitions that will be specific for non-adaptive
algorithms. When dealing with non-adaptive algorithms, we will also need to
express the transmission probability of a station at any round of its local
clock: $p(i)$ denotes the probability that an arbitrary station transmits at
the $i$th round of its local clock. More precisely, without loss of
generality, we can assume that each station $v$ chooses randomly, in advance,
the sequence of rounds in which it schedules the transmissions. Recall that
the assignment of transmissions to rounds does not need to be independent over
the rounds.

Notice that in $p(i)$ we do not need to specify the station which this
probability refers to. Indeed, for non-adaptive algorithms, the probability
that a station transmits at the $i$th round of its local clock may depend only
on the local round index $i$ (recall that the stations are anonymous). We also
define the sum of transmission probabilities of an arbitrary station up to
local time $i$:

$s(i)=\sum_{j=1}^{i}p(j)\ .$

Let $v$ be an arbitrary station and $t_{v}$ be the round, with respect to a
given reference clock, corresponding to the wake-up time of $v$. The $t$th
round of the reference clock corresponds to the $(t-t_{v})$th round of $v$’s
local clock. Therefore, if $v$ is active in round $t$, its transmission
probability in this round is $q_{v}[t]=p(t-t_{v})$.

We define

$\hat{\sigma}[t]=\sum_{v\in\hat{A}[t]}{p(t-t_{v})}\ .$

It is easy to see that $\hat{\sigma}[t]\geq\sigma[t]$, due to the ranges of
sums defining these two values.

As might have been noticed, when the time appears as argument of a function
(like $p(i)$, $s(i)$, $A[t]$, $q_{u}[t]$), to avoid confusion, we have used
parenthesis for local rounds and square brackets for rounds of a given
reference clock. We will continue using such a convention throughout the
paper.

###  2.2 Chernoff bounds.

Throughout the paper, we will use the following form of the Chernoff bound
(see Eq. (4.2) and (4.5) in [36]). Let $X_{1},\ldots,X_{n}$ be independent
Poisson trials such that $\Pr(X_{i}=1)=p_{i}$ . Let $X=\sum_{i=1}^{n}X_{i}$
and $\mu=\mathbf{E}[X]$. Then, for $0<\delta<1$, the following bounds hold:

$\displaystyle\Pr(X\geq(1+\delta)\mu)$ $\displaystyle\leq$ $\displaystyle
e^{-\frac{\delta^{2}\mu}{3}};$ $\displaystyle\Pr(X\leq(1-\delta)\mu)$
$\displaystyle\leq$ $\displaystyle e^{-\frac{\delta^{2}\mu}{2}}.$

##  3 A non-adaptive algorithm for known contention

In this section we give a non-adaptive algorithm achieving latency $O(k)$ in
the case when the number of contenders $k$, or a linear upper bound on $k$, is
given to the stations as a part of the input. Recall that the stations do not
have any ID and are allowed to wake up arbitrarily. Apart from being non-
adaptive, an additional advantage of our algorithm is that it is uniform,
i.e., the transmissions are independent over rounds. Moreover, it can deal
successfully against an adaptive adversary.

The algorithm is formally described as follows. Any station, starting from the
time at which it is activated, executes the following protocol
NonAdaptiveWithK($k,c$) (see Algorithm 1). It takes two parameters in input:
the number $k$ of stations and a constant $c$. Such a constant determines the
probability of success of the algorithm: for any fixed parameter $\eta>0$, we
can choose an input value $c$ such that the algorithm succeeds with
probability at least $1-1/k^{\eta}$ for any contention size $k$ (recall the
definition of high probability given in the Introduction). For every integer
$0\leq l\leq\log\log k$, let

$\varphi(l)=\left\\{\begin{tabular}[]{cc}$\frac{k}{2^{l}}$,&if $l<\log\log
k$;\\\ $k$,&if $l=\log\log k$.\\\ \end{tabular}\right.$

Algorithm 1 NonAdaptiveWithK($k,c$)

1:for $l=0,1,2,\ldots,\log\log k$ do

2: for $c\varphi(l)$ rounds do transmit with probability $\frac{2^{l}}{2k}$

3: end for

4:end for

Figure 2 shows the sequence of transmission probabilities for two stations,
activated in different rounds, as it results from the execution of the first
three iterations of the inner for-loop. Notice how the lack of synchronization
between the two stations causes that in many rounds they transmit with
different probabilities.

|  | $\overbrace{\hskip 85.35826pt}^{\mbox{$ck$ rounds}}$ | $\overbrace{\hskip 85.35826pt}^{\mbox{$ck/2$ rounds}}$ | $\overbrace{\hskip 85.35826pt}^{\mbox{$ck/4$ rounds}}$ |  |
---|---|---|---|---|---|---
$u_{1}$: |  | $1/2k$ | $\ldots$ | $1/2k$ | $1/k$ | $\ldots$ | $1/k$ | $2/k$ | $\ldots$ | $2/k$ | … |
|  |  | $\overbrace{\hskip 85.35826pt}^{\mbox{$ck$ rounds}}$ | $\overbrace{\hskip 85.35826pt}^{\mbox{$ck/2$ rounds}}$ | $\overbrace{\hskip 85.35826pt}^{\mbox{$ck/4$ rounds}}$ |
$u_{2}$: |  |  | $1/2k$ | $\ldots$ | $1/2k$ | $1/k$ | $\ldots$ | $1/k$ | $2/k$ | $\ldots$ | $2/k$ | …
|  |  |  |  |  | ⋮ |  |  |  |  |  |
Figure 2: Two stations executing the first 3 iterations of the inner for-loop
of Protocol NonAdaptiveWithK($k,c$).

In this section we want to prove the following theorem.

######  Theorem 3.1.

All stations executing protocol NonAdaptiveWithK($k,c$), for a sufficiently
large constant $c$, will transmit successfully within $O(k)$ time rounds whp.
The result holds even against an adaptive adversary.

The linear upper bound on the latency of the protocol follows from an easy
inspection of the pseudo-code: the total number of rounds is less than
$c(k+k/2+k/4+\cdots+k/{\log k}+k)<3c\cdot k$. Therefore, we can state the
following fact.

######  Fact 3.1.

For any given integer constant $c>0$, the number of rounds needed for any
station to execute protocol NonAdaptiveWithK($k,c$) is less than $3c\cdot
k=O(k)$.

Hence, from now on we may focus only on proving the correctness of the
protocol. As stated by Fact 3.1, each station is able to transmit only for at
most (actually less than) $3c\cdot k$ rounds following its activation.
Therefore, there are altogether at most $3c\cdot k^{2}$ rounds in which the
transmissions from the $k$ stations can occur. Of course, these rounds are not
necessarily consecutive, as they depend on the wake-up times of the stations
which can be arbitrarily distant in time. This set of rounds can be
partitioned into disjoint intervals consisting of subsequent rounds at which
there are some active stations that are executing the protocol and, therefore,
can choose to transmit. These intervals are called time frames (there can be
many of them).

Let’s start with the following observation which is a consequence of the fact
that there are altogether at most $3c\cdot k^{2}$ rounds in which a
transmission can occur.

######  Fact 3.2.

For any choice of the activation times, any time frame lasts at most $3c\cdot
k^{2}$ rounds.

In the following analysis we will concentrate on an arbitrary time frame $F$
and use a reference clock starting with it: the $t$th round of the reference
clock is the $t$th round of $F$. In other words, the reference clock is an
imaginary global clock (unknown to the stations) starting with the activation
time of the first station(s). We will show that any station $v$ executing the
protocol during such a time frame, will transmit successfully before the end
of the execution.

The crux of the analysis will be to show that the rounds of a time frame can
be partitioned into $\log\log k$ disjoint intervals such that, as a result of
successful transmissions, the number of active stations is halved in each of
these intervals, independently of how their wake up times are chosen by the
adversary (Lemma 3.2). Such a progressive reduction of the active stations,
besides being beneficial in itself, in that it brings us closer to the final
goal, it also remarkably contributes to lighten the contention among the
remaining active stations, so that it is possible to show that in each round
$t$ of a time frame, the sum of transmission probabilities $\sigma[t]$ is less
than 1 whp (Lemma 3.5). This is a very favorable situation that will be
finally exploited by any station that hasn’t been able to transmit
successfully until the last iteration, i.e., when it transmits for $ck$ rounds
with probability $\log k/(2k)$. Namely, in the final proof of Theorem 3.1 on
page 3 we will show that having a small sum of transmission probabilities in
every round of the time frame, implies that any station – if still alive –
transmits successfully with probability $\Omega(\log k/k)$ in each of the
rounds of the last iteration. This probability combined with the size $ck$ of
the iteration assures that the station transmits successfully, whp, in one of
these final rounds, provided it didn’t do so previously.

We start with the next lemma stating that in each round $t\in F$ such that
$\sigma[t]<1$, we have a favorable probability that a given station $v$
transmits successfully. For any round $t\in F$, let us define
${\mathcal{E}}[t]$ as the event that $\sigma[t]<1$.

######  Lemma 3.1.

If the event ${\mathcal{E}}[t]$ holds, then the probability that a given
station $v$ transmits successfully in round $t$ is larger than $q_{v}[t]/4$.

###### Proof.

For every round $t$ of our protocol, $q_{v}[t]\leq 1/2$, from which we get
$(1-q_{w}[t])^{\frac{1}{q_{w}[t]}}\geq 1/4$. Hence, the probability stated in
the lemma becomes

$\displaystyle q_{v}[t]\cdot\prod_{w\neq v}(1-q_{w}[t])$ $\displaystyle=$
$\displaystyle q_{v}[t]\cdot\prod_{w\neq
v}(1-q_{w}[t])^{\frac{1}{q_{w}[t]}q_{w}[t]}$ $\displaystyle\geq$
$\displaystyle q_{v}[t]\cdot\prod_{w\neq v}(1/4)^{q_{w}[t]}$ $\displaystyle>$
$\displaystyle q_{v}[t]\cdot(1/4)^{\sigma[t]}$ $\displaystyle>$ $\displaystyle
q_{v}[t]/4\ ,$

where the last inequality follows from the hypothesis that ${\mathcal{E}}[t]$
holds. ∎

Our next goal will be to show that this favorable situation recurs whp for the
whole execution of the algorithm. Indeed, in Lemma 3.5 we will show that the
events ${\mathcal{E}}[t]$ simultaneously occur whp for all rounds $t$ of a
given time frame. Before being able to prove such a claim, we need three
preparatory lemmas.

In the first of these lemmas we consider a scenario in which the sum of
transmission probabilities $\sigma[\iota]$ is less than $1$ for all rounds
$\iota<t$, i.e., ${\mathcal{E}}[\iota]$ occurs in all rounds $\iota$ preceding
round $t$.

We show that for any $j\in(0,\log\log k]$, during the $c\varphi(j)$ rounds
preceding round $t$, at least half of the stations that at time $t$ are
assigned to some iteration $\lambda\geq j$ of the outer for-loop of the
protocol, will transmit successfully whp. Therefore they switch-off before
round $t$.

Let $U$, $|U|\leq k$, be the set of all the stations executing the algorithm
in a given frame. For any integer $l\in[0,\log\log k]$ and time round $t\geq
0$, we define $T^{l}[t]\subseteq U$ to be the subset of stations $v$ (not
necessarily still active) that at round $t$ have assigned a transmission
probability $q_{v}[t]=2^{l}/(2k)$. In other words, it includes all the
stations that have been activated in some round before $t$ and would transmit
with probability $2^{l}/(2k)$ if still active (i.e., if not switched-off due
to a successful transmission) at round $t$.

For any predefined parameter $\eta>0$, let $c$ be chosen sufficiently large so
that $\eta\leq(c-8)^{2}/(32c)+4$.

######  Lemma 3.2.

Let $0<j\leq\log\log k$ be an integer. Let $F$ be any time frame and
$\tau,\tau^{\prime}\in F$ be two time rounds such that
$\tau^{\prime}=\tau-c\varphi(j)$. Assume that the events
${\mathcal{E}}[1],{\mathcal{E}}[2],\ldots,{\mathcal{E}}[\tau-1]$ hold. Then,
if $T^{\prime}\subseteq\bigcup_{\lambda\geq j}T^{\lambda}[\tau]$ and
$|A[\tau^{\prime}]\cap T^{\prime}|\leq x$ for some $x>0$, then $|A[\tau]\cap
T^{\prime}|\leq\max\\{x/2,\sqrt{k}\\}$ with probability at least
$1-k^{-\eta-4}$.

###### Proof.

Let us consider rounds $\iota\in[\tau^{\prime},\tau-1]$. Notice that since
$j>0$, all the stations in $T^{\prime}$ must have joined the protocol before
round $\tau^{\prime}$. Thus during the interval $[\tau^{\prime},\tau-1]$ the
number of stations in $A[\iota]\cap T^{\prime}$ cannot increase (it can only
decrease as the stations switch-off after successful transmissions).

If $x\leq\sqrt{k}$, then $|A[\tau]\cap T^{\prime}|\leq|A[\tau^{\prime}]\cap
T^{\prime}|\leq x\leq\sqrt{k}$ and there is nothing to prove. So hereafter we
assume that $x>\sqrt{k}$ and our aim will be to prove that $|A[\tau]\cap
T^{\prime}|\leq x/2$ with probability at least $1-k^{-\eta-4}$.

For any round $\iota$, $\tau^{\prime}\leq\iota\leq\tau-1$, let $p_{\iota}$ be
the probability of having a successful transmission at round $\iota$. To any
execution of the algorithm, we can attribute the following 0-1 sequence
$\rho$, of length $c\varphi(j)$, where the $(\iota-\tau^{\prime}+1)$th bit of
$\rho$ corresponds to round $\iota$, for
$\iota=\tau^{\prime},\tau^{\prime}+1,\ldots,\tau-1$. The
$(\iota-\tau^{\prime}+1)$th bit of $\rho$ is defined as follows.

  * •

If $|A[\iota]\cap T^{\prime}|>x/2$ and there is no successful transmission
from $A[\iota]\cap T^{\prime}$ at time $\iota$, then we have a 0 on the
position corresponding to $\iota$.

  * •

If $|A[\iota]\cap T^{\prime}|>x/2$ and there is a successful transmission from
$A[\iota]\cap T^{\prime}$ at time $\iota$, then we assign 1 at the
corresponding position with probability $(1/p_{\iota})x2^{j}/16k$ and 0
otherwise. Observe that this probability is well defined as
$p_{\iota}>x2^{j}/16k$. Indeed, there are more than $x/2$ stations in
$A[\iota]\cap T^{\prime}$ and each of them transmits successfully with
probability larger than $q_{v}(\iota)/4=2^{j}/8k$ by Lemma 3.1.

  * •

Finally, if $|A[\iota]\cap T^{\prime}|\leq x/2$ then the position is set by
tossing an asymmetric coin where 1 is output with probability $x2^{j}/16k$ and
0 otherwise.

We can now observe that for every $\tau^{\prime}\leq\iota\leq\tau-1$, the
probability of having a 1 in the corresponding $(\iota-\tau^{\prime}+1)$th bit
of $\rho$ is ${x2^{j}}/{16k}$ independently of the values of the other bits,
even against an adaptive adversary. This is evident in case $|A[\iota]\cap
T^{\prime}|\leq x/2$. In case $|A[\iota]\cap T^{\prime}|>x/2$ the probability
of having a 1 is $p_{\iota}(1/p_{\iota}){x2^{j}}/{16k}={x2^{j}}/{16k}$, which
turns out to be independent of the probability $p_{\iota}$ of having a
successful transmission at round $\iota$. This in particular implies that
although the probability of having a successful transmission can be affected
by the activation of new stations, the behaviour of these newcomers cannot
influence the probability of having a 1 or a 0 in $\rho$.

Let $X$ be the random variable defined as the number of ones in $\rho$. We can
now see that if $X\geq x/2$, then $|A[\tau]\cap T^{\prime}|\leq x/2$. Assuming
that $|A[\tau^{\prime}]\cap T^{\prime}|\leq x$, the ones in $\rho$ produced
when $|A[\iota]\cap T^{\prime}|>x/2$ correspond to successful transmissions.
Consequently, there are at most $x/2$ stations that remain active in the
interval $[\tau^{\prime},\tau-1]$. Recalling that by hypothesis
$|A[\tau^{\prime}]\cap T^{\prime}|\leq x$, it follows that $|A[\tau]\cap
T^{\prime}|\leq x-x/2=x/2$.

Hence, the probability that $|A[t]\cap T^{\prime}|\leq x/2$ is at least the
probability that $X\geq x/2$. An estimate of the latter probability will
complete the proof. The random variable $X$ expresses the number of successes
in $c\varphi(j)\geq ck/2^{j}$ mutually independent experiments, in each of
which the probability of success is $x2^{j}/16k$. Therefore $\mathbf{E}(X)\geq
cx/16$. Notice that for this inequality to hold, it is sufficient that
$c\varphi(j)=ck/2^{j}$ for every $j=0,1,\ldots,\log\log k$, but recall that
the algorithm uses $c\varphi(j)=ck$ rounds in its last iteration,
corresponding to $j=\log\log k$.  Hence, for $c$ sufficiently large,

$\displaystyle\Pr(X<x/2)$ $\displaystyle\leq$
$\displaystyle\Pr(X\leq\mathbf{E}(X)\cdot 8/c)$ $\displaystyle\leq$
$\displaystyle\exp[-\mathbf{E}(X)(1-8/c)^{2}/2]\mbox{ (by the Chernoff
bound)}$ $\displaystyle\leq$
$\displaystyle\exp[-\sqrt{k}(c-8)^{2}/(32c)]\mbox{ (recalling that
$x>\sqrt{k}$)}$ $\displaystyle<$ $\displaystyle
k^{-(c-8)^{2}/(32c)}=k^{-\eta-4}\ .$

∎

Our next milestone will be to use Lemma 3.2 to show that when the events
${\mathcal{E}}[1],{\mathcal{E}}[2],\ldots,{\mathcal{E}}[t-1]$ hold, then
${\mathcal{E}}[t]$ also holds whp. This will be done in the two following
lemmas. First, in Lemma 3.3, we define the more complex events
${\mathcal{A}}^{l}[t]$ and prove that their intersection implies event
${\mathcal{E}}[t]$. Second, in Lemma 3.4, we apply this fact to upper bound
the sought conditional probability.

Let $t\geq 0$ be a round index and $0\leq l\leq\log\log k$. Event
${\mathcal{A}}^{l}[t]$ is the event that holds if and only if $|A[t]\cap
T^{l}[t]|\leq\max\\{|T^{l}[t]|/2^{l},\sqrt{k}\\}$. Let ${\mathcal{A}}[t]$ be
the event that holds if and only if all events ${\mathcal{A}}^{l}[t]$, for
$l=0,1\ldots,\log\log k$, hold.

######  Lemma 3.3.

Let $F$ be any time frame and $t\in F$. If event ${\mathcal{A}}[t]$ holds then
${\mathcal{E}}[t]$ holds.

###### Proof.

Fix a round index $t$ and assume that for $l=0,1,\ldots,\log\log k$, events
${\mathcal{A}}^{l}[t]$ hold. We have to show that $\sigma[t]<1$. Indeed,

$\displaystyle\sigma[t]$ $\displaystyle=$ $\displaystyle\sum_{l=0}^{\log\log
k}|A[t]\cap T^{l}[t]|\cdot 2^{l}/2k$ $\displaystyle\leq$
$\displaystyle\sum_{l=0}^{\log\log k}|T^{l}[t]|/2k+\sum_{l=0}^{\log\log
k}\sqrt{k}\cdot 2^{l}/2k\mbox{ (by the hypothesis that ${\mathcal{A}}[t]$
holds)}$ $\displaystyle<$ $\displaystyle|U|/2k+1/2\leq 1.$

∎

For any event ${\mathcal{A}}$ we denote by $\overline{{\mathcal{A}}}$ the
negation of ${\mathcal{A}}$.

######  Lemma 3.4.

Let $F$ be any time frame and $t\in F$. We have

$\Pr\left(\overline{{\mathcal{E}}[t]}\>\Big{|}\>{\mathcal{E}}[1]\wedge{\mathcal{E}}[2]\wedge\cdots{\mathcal{E}}[t-1]\right)<k^{-\eta-3}(\log\log
k+1).$

###### Proof.

Let us fix any round $t$. By Lemma 3.3, we have:

$\displaystyle\Pr\left(\overline{{\mathcal{E}}[t]}\>\Big{|}\>{\mathcal{E}}[1]\wedge{\mathcal{E}}[2]\wedge\cdots{\mathcal{E}}[t-1]\right)\leq\sum_{l=0}^{\log\log
k}\Pr\left(\overline{{\mathcal{A}}^{l}[t]}\>\Big{|}\>{\mathcal{E}}[1]\wedge\cdots\wedge{\mathcal{E}}[t-1]\right).$
(1)

In order to complete the proof it will suffice to show that
$\Pr\left(\overline{{\mathcal{A}}^{l}[t]}\>\Big{|}\>{\mathcal{E}}[1]\wedge\cdots\wedge{\mathcal{E}}[t-1]\right)$
is smaller than $k^{-\eta-3}$ for every $l=0,1,\ldots,\log\log k$.

For $l=0$, ${\mathcal{A}}^{l}[t]$ reduces to $|A[t]\cap
T^{l}[t]|\leq\max\\{|T^{l}[t]|,\sqrt{k}\\}$ which trivially holds. Therefore,
the probability of
$\left(\overline{{\mathcal{A}}^{0}[t]}\>\Big{|}\>{\mathcal{E}}[1]\wedge\cdots\wedge{\mathcal{E}}[t-1]\right)$
is zero.

Let us now fix $l\in[1,\log\log k]$. We define the sequence of rounds
$t_{0},t_{1},\ldots,t_{l}$ so that $t_{j}-t_{j-1}=c\varphi(j)$ and $t_{l}=t$
for $j=1,\ldots,l$. Note that $T^{l}[t]\subseteq\bigcup_{\lambda\geq
j}T^{\lambda}[t_{j}]$ for any $j\leq l$. Therefore, repeatedly applying Lemma
3.2 to intervals $[\tau^{\prime},\tau]=[t_{j-1},t_{j}]$ for
$j=l,l-1,\ldots,1$, we can write:

$\displaystyle|A[t_{l}]\cap T^{l}[t]|$ $\displaystyle\leq$
$\displaystyle\max\\{|A[t_{l-1}]\cap T^{l}[t]|/2,\sqrt{k}\\}\mbox{ (with
probability at least }1-k^{-\eta-4})$ $\displaystyle\leq$
$\displaystyle\max\\{|A[t_{l-2}]\cap T^{l}[t]|/4,\sqrt{k}\\}\mbox{ (with
probability at least }1-k^{-\eta-4})$ $\displaystyle\vdots$
$\displaystyle\leq$ $\displaystyle\max\\{|A[t_{0}]\cap
T^{l}[t]|/2^{l},\sqrt{k}\\}\mbox{ (with probability at least }1-k^{-\eta-4})$
$\displaystyle\leq$ $\displaystyle\max\\{|T^{l}[t]|/2^{l},\sqrt{k}\\}\ .$

Thus, after applying a union bound to the above derivation, we get that

$|A[t]\cap T^{l}[t]|\leq\max\\{|T^{l}(t)|/2^{l},\sqrt{k}\\}$

holds with probability at least $1-k^{-\eta-4}\log\log k>1-k^{-\eta-3}$. ∎

######  Lemma 3.5.

Given any time frame $F$, all events ${\mathcal{E}}[t]$, for every $t\in F$,
simultaneously occur with probability larger than $1-k^{-\eta}/2$.

###### Proof.

Let $F$ be any time frame. We want to prove that
$1-\Pr({\mathcal{E}}[1]\wedge{\mathcal{E}}[2]\wedge\cdots\wedge{\mathcal{E}}[|F|])$
is less than $k^{-\eta}/2$.

Hence,

$\displaystyle
1-\Pr({\mathcal{E}}[1]\wedge{\mathcal{E}}[2]\wedge\cdots\wedge{\mathcal{E}}[|F|])$
$\displaystyle=$
$\displaystyle\sum_{t=1}^{|F|}\Pr\left(\overline{{\mathcal{E}}[t]}\>\Big{|}\>{\mathcal{E}}[1]\wedge{\mathcal{E}}[2]\wedge\cdots{\mathcal{E}}[t-1]\right)\Pr({\mathcal{E}}[1]\wedge{\mathcal{E}}[2]\wedge\cdots{\mathcal{E}}[t-1])$
$\displaystyle\leq$
$\displaystyle\sum_{t=1}^{|F|}\Pr\left(\overline{{\mathcal{E}}[t]}\>\Big{|}\>{\mathcal{E}}[1]\wedge{\mathcal{E}}[2]\wedge\cdots{\mathcal{E}}[t-1]\right)$
$\displaystyle\leq$ $\displaystyle 3c\cdot
k^{2}\cdot\Pr\left(\overline{{\mathcal{E}}[t]}\>\Big{|}\>{\mathcal{E}}[1]\wedge{\mathcal{E}}[2]\wedge\cdots{\mathcal{E}}[t-1]\right)\mbox{
(by Fact~{}\ref{Fact1a})}$ $\displaystyle<$ $\displaystyle 3c\cdot k^{2}\cdot
k^{-\eta-3}(\log\log k+1)\mbox{ (by Lemma~{}\ref{conditional})}$
$\displaystyle<$ $\displaystyle k^{-\eta}/2\ ,$

for sufficiently large $k$. ∎

The last lemma tells us that, whp, $\sigma[t]<1$ holds for all rounds $t$
within a time frame. Due to this inequality, we are now able to show that in
each of the last $ck$ rounds, station $v$ — if still awake — transmits
successfully with probability $\Omega(\log k/k)$. This, in turn, assures that
$v$ transmits successfully, whp, in one of these final rounds (provided it
didn’t do so previously). What follows is the proof of Theorem 3.1, which is
the main result of this section.

Proof of Theorem 3.1

Let us focus on some station $v$ active in some time frame $F$. We first prove
that this station transmits whp within $O(k)$ rounds and then we take the
union bound over all contending stations. We will prove that $v$ manages to
transmit successfully, whp, by the end of the execution of its protocol. Let
$R\subseteq F$ be the set of the last $ck$ rounds executed by $v$
corresponding to the final iteration of the inner for-loop. While it is
active, station $v$ transmits in any round $t\in R$ with probability
$q_{v}[t]=p(t-t_{v})=\log k/(2k)$. In order to prove the theorem, we need to
show that $v$ transmits successfully in one of these rounds whp.

The probability that station $v$ does not transmit successfully during the
rounds in $R$ is upper bounded by the probability that the station does not
transmit successfully in a round $t\in R$ when all events ${\mathcal{E}}[t]$
for $t\in R$ hold or that there exists a round $t\in R$ such that
${\mathcal{E}}[t]$ does not hold.

By Lemma 3.1, in any round $t\in R$ such that event ${\mathcal{E}}[t]$ holds,
the active station $v$ transmits successfully with probability larger than
$q_{v}[t]/4=\log k/(8k)$. So, assuming that for every round $t\in R$ event
${\mathcal{E}}[t]$ holds, station $v$ does not manage to transmit successfully
with probability less than $(1-\log k/(8k))^{ck}<e^{-c\log k/8}$, which is
smaller than $k^{-\eta}/2$, if we take the constant $c$ sufficiently large.

By Lemma 3.5 the probability that there exists a round $t\in R$ such that
event ${\mathcal{E}}[t]$ does not hold is also smaller than $k^{-\eta}/2$.
Hence, the probability that station $v$ does not transmit successfully is less
than $k^{-\eta}/2+k^{-\eta}/2=k^{-\eta}$. Now, taking the union bound over all
contending stations, we get that the probability that one station fails to
transmit successfully is at most $k^{-\eta+1}$, for any prefixed parameter
$\eta>0$. This also means that for any fixed $\eta-1>0$, all stations transmit
successfully with probability at least $1-k^{-(\eta-1)}$, that is whp. This
concludes the proof of Theorem 3.1. ∎

Now we can conclude this section by showing that our algorithm is also energy
efficient. In the following theorem we consider the number of broadcast
attempts performed by all contending stations.

######  Theorem 3.2.

The total number of broadcast attempts for an execution of Protocol
NonAdaptiveWithK($k,c$) is $O(k\log k)$ whp. The result holds even against an
adaptive adversary.

###### Proof.

For $l<\log\log k$, during the $l$-th execution of the main loop, the expected
number of transmissions per station is $c\varphi(l)\cdot 2^{l}/(2k)=c/2$.
While for $l=\log\log k$ this expected number is $c\varphi(\log\log k)\cdot
2^{\log\log k}/(2k)=(c/2)\log k$. Overall, we have $O(\log k)$ expected
transmissions per station for the whole execution of the protocol.

Since the transmissions are independent over rounds, by using the Chernoff
bound to estimate from above the number of transmissions of a single station,
and then the union bound over all stations, we get $O(\log k)$ transmissions
for every station, whp. This means that in total our algorithm requires
$O(k\log k)$ broadcast attempts whp. ∎

##  4 A lower bound for non-adaptive algorithms

The aim of this section is to prove the following theorem stating a lower
bound on non-adaptive algorithms without the knowledge of $k$.

######  Theorem 4.1.

There is no non-adaptive contention resolution algorithm, with no knowledge of
contention size $k$, with a latency of $o(k\log k/(\log\log k)^{2})$ rounds
whp. The result holds even for a weaker oblivious adversary.

For the sake of contradiction, in the following we will assume that there is a
non-adaptive algorithm ${\mathcal{A}}$ which, without having any information
on contention size $k$, solves the contention for any number $k$ of stations,
with a latency of $o\left(k\frac{\log k}{(\log\log k)^{2}}\right)$ rounds whp.

In the following, we will use the term instance to denote a schedule assigning
to each station the time at which it becomes activated. Our aim will be to
show existence of an instance of the problem such that whp algorithm
${\mathcal{A}}$ does not make any successful transmission on this instance
within the first $\Omega\left(k\frac{\log k}{(\log\log k)^{2}}\right)$ rounds.
This of course contradicts the assumption on the latency of algorithm
${\mathcal{A}}$. We stress out the following interesting polarization that we
have discovered and make use of here, and which does not take place in the
simpler setting with synchronization — if one tries to solve contention
resolution (i.e., to have all stations successful) with an algorithm too
greedy in terms of channel utilization, it may not achieve even a single
successful transmission. We would like to emphasize that the instance is
determined in advance so that this lower bound is valid for oblivious
adversary.

Recall that for algorithm ${\mathcal{A}}$ we can define a sequence of
probabilities $p(1),p(2),p(3),\ldots$ of transmissions of station’s message in
its local rounds $1,2,3,\ldots$ counting from its activation. This sequence is
the same for all executions and across all stations, due to ${\mathcal{A}}$
being non-adaptive. Namely, any station transmits its message with probability
$p(1)$ in the first round after it has been activated. If it has not
transmitted successfully before, the transmission occurs with probability
$p(i)$ for $i>1$ in the $i$th round after its activation. Note that the
transmission in a round $i$ does not have to be necessarily an event
independent on the transmissions in previous rounds; in this sense our proof
is more general than many other lower bounds in the literature of shared
channel which hold under the assumption of such an independence over rounds.

Without loss of generality we can assume $p(1)>0$. Moreover, since the
stations do not know parameter $k$, the contention size, the probability
$p(1)$ does not depend on $k$.

We emphasize that, in view of our contradictory hypothesis, all the following
definitions and results hold for a non-adaptive algorithm ${\mathcal{A}}$
which, without knowing $k$, solves the Contention Resolution problem for any
number $k$ of contending stations, with a time complexity of
$o\left(k\frac{\log k}{(\log\log k)^{2}}\right)$ whp.

The following new definitions will be used. Let $I(k)$ be an arbitrary
instance in which exactly $k$ stations are activated. Let $\tau(I(k))$ be the
minimum time needed for algorithm ${\mathcal{A}}$ to assure that any activated
station transmits successfully in instance $I(k)$ whp, i.e. at least
$1-k^{-\eta}$ for any predetermined constant $\eta>0$. Let
$\tau(k)=\max_{I(k)}\\{\tau(I(k))\\}$, where the maximum is taken over all
instances activating $k$ stations. A straightforward consequence of our
contradictory assumption is that $\tau(k)=o\left(k\frac{\log k}{(\log\log
k)^{2}}\right)$. We also define

$\varsigma(k)=s(\tau(k))=\sum_{i\in[1,\tau(k)]}p(i)\ .$

Fixed any instance $I(k)$, we will use a reference clock starting at the first
activation time of the instance. All the following rounds $t$ refer to this
clock.

The proof of the lower bound consists of two parts. In the first part we show
a dependance between the number of successful transmissions and the sum of
transmission probabilities. This is the task of the following lemma which
shows that if in an interval of $O(k^{2})$ rounds the sum ${\hat{\sigma}}[t]$
of transmission probabilities of all activated stations is $\Omega(\log k)$,
then whp no transmission will be successful in that interval. Note that, since
$\tau(k)\leq k^{2}$, this contradicts the assumption that algorithm
${\mathcal{A}}$ has latency $\tau(k)$ whp. The second part of the proof is
devoted to constructing an instance of activation times such that the
hypothesis of Lemma 4.1 holds, so to block whp successful transmissions for
$\tau(k)$ rounds.

######  Lemma 4.1.

Fix an arbitrary instance. Assume that for any round $t\in[1,T]$, with $T\leq
k^{2}$, it holds that ${\hat{\sigma}}[t]\geq\gamma\log k$ for some
sufficiently large constant $\gamma>0$. Then, no station transmits
successfully by round $T$ with probability $1-1/k$.

###### Proof.

We want to show that the probability of having at least one successful
transmission in the time interval $[1,T]$ is smaller than $1/k$. Since we are
interested in the probability of having at least one successful transmission,
we can consider the simplified model in which the stations do not switch off
when they transmit successfully. Indeed, on any sequence of activation times
for the $k$ stations, the probability of having the first (i.e., at least one)
successful transmission on the original model is equivalent to the probability
of having the first transmission in the simplified model. In the simplified
model, the probability of successful transmission in any round $t$, if no
successful transmission happened before time $t$, is at most

$\sum_{v\in{\hat{A}}[t]}p(t-t_{v})\prod_{{w\in{\hat{A}}[t],}{w\not=v}}\left(1-p(t-t_{w})\right)\leq{\hat{\sigma}}[t]e^{-{\hat{\sigma}}[t]+1}\
,$

which can be made smaller than $1/k^{3}$, for a sufficiently large $\gamma$.

By taking the union bound over all the $T\leq k^{2}$ rounds, we get that the
probability of no successful transmission in the simplified model (and thus in
the original model) is at most $1/k$. ∎

The construction of the problem instance assuring the lower bound on the
algorithm will be based on the inequality
$\varsigma(k)=\Omega(\log^{2}k/(\log\log k)^{2})$ proved in the key Lemma 4.5,
transformed later into the lower bound on ${\hat{\sigma}}[t]$ in Lemma 4.6. In
order to prove that key lemma, we first show a weaker inequality that
$\varsigma(k)$ has to fulfill.

######  Lemma 4.2.

$\varsigma(k)=\Omega(\log k/\log\log k)$.

###### Proof.

To prove the lemma, we construct a random instance for algorithm
${\mathcal{A}}$ such that if $\varsigma(k)\not=\Omega(\log k/\log\log k)$,
then the first station $v$ activated in this instance transmits successfully,
within $\tau(k)$ rounds, with probability smaller than $1-1/k^{\zeta}$, for
some constant $\zeta>0$. Because of this, the contention resolution problem
would not be solved whp by algorithm ${\mathcal{A}}$.

Let station $v$ be activated among the earliest possible group of stations,
i.e., at round 1 of the instance. Station $v$ chooses at random the rounds in
which it is going to transmit (it can be assumed that this choice be done at
the moment $v$ is activated, as the algorithm is non-adaptive). The number of
such rounds in the time period $[1,\tau(k)]$ is a random variable $X$ such
that $E(X)=\varsigma(k)$. By Markov’s inequality we have

$\Pr\left(X<2\varsigma(k)\right)>1/2\ .$ (2)

We now let the activation times of the other $k-1$ stations be distributed
uniformly at random among the $\tau(k)=O(k\log k)$ rounds. Each station
transmits with probability $p(1)$ at the first round it switches on.
Therefore, at any round in which $v$ transmits, the probability that this
transmission is not successful is at least $(k-1)\cdot p(1)\cdot(1/O(k\log
k))=\Omega(1/\log k)$. (Recall that, as explained in the introductory part of
this section, $p(1)$ does not depend on $k$.)

Thus, the probability of no successful transmission for station $v$ during the
interval $[1,\tau(k)]$ is at least

$\displaystyle\Omega\left(\frac{1}{(\log k)^{X}}\right)\ .$

Hence, this probability (that $v$ does not transmit successfully) is
negligible, i.e., at most $1/k^{\eta}$ for any predetermined constant
$\eta>0$, only when $X=\Omega(\log k/\log\log k)$. By Equation (2), it follows
that $\varsigma(k)=\Omega(\log k/\log\log k)$, or otherwise station $v$ does
not transmit successfully whp within the interval $[1,\tau(k)]$.

∎

In the following lemma we show that the sum of probabilities in a round could
be indeed made $\Omega(\log n)$ over a period slightly shorter than the
ultimate length $\tau(k)$; we will extend it even further later on.

| $\overbrace{\hskip 298.75394pt}^{\mbox{\small$(c^{\prime}\log\log k)/2$
activations per round}}$
---|---
| $\overbrace{\hskip 159.3356pt}^{\mbox{\small$\gamma\log k/p(1)$ activations per round}}$ |  |  |  |
Rounds of the instance: | $1,2,$ |  | $\ldots$ |  | $,\tau(k/\log^{2}k),$ |  | $\ldots$ |  | $,k/(c^{\prime}\log\log k)$
Figure 3:  Construction of the activation instance used in Lemma 4.3.

From now on, we consider the constant $\gamma$ determined in Lemma 4.1

######  Lemma 4.3.

There is a constant $c_{1}>0$ and an integer $k_{0}$ such that for $k>k_{0}$
there is an instance $I(k)$ such that ${\hat{\sigma}}[t]\geq\gamma\log k$ in
rounds $t\in[1,\tau(k/(c_{1}\log k\log\log k))]$.

###### Proof.

By the contradictory hypothesis on the latency of algorithm ${\mathcal{A}}$,
it follows that $\tau(k)=o(k\log k/(\log\log k)^{2})$. This implies that for
any constant $c^{\prime}>0$ there exists a constant $c_{1}>0$ such that
$\tau(k/(c_{1}\log k\log\log k))\leq k/(c^{\prime}\log\log k)$ for $k$
sufficiently large. In other words, for any $c^{\prime}$ there is $c_{1}$ such
that

$[1,\tau(k/(c_{1}\log k\log\log k))]\subseteq[1,k/(c^{\prime}\log\log k)]\ .$
(3)

Also, we have

$\tau(k/\log^{2}k)=o(k/\log k)\ .$ (4)

Let $\gamma$ be the constant determined in Lemma 4.1. Since, by Lemma 4.2,
$\varsigma(k)=\Omega(\log k/\log\log k)$, there is a constant $c^{\prime}$
such that for $k$ sufficiently large the following inequality holds:

$\varsigma(k/\log^{2}k)\geq 2\gamma\log k/(c^{\prime}\log\log k)\ .$ (5)

We can construct instance $I(k)$ for $k$ contending stations as follows (see
Figure 3 for a reference). In each round $t\in[1,\tau(k/\log^{2}k)]$ we switch
on $\gamma\log k/p(1)$ stations. Recalling that each station transmits with
probability $p(1)$ in the first round after it has been activated, we have
${\hat{\sigma}}[t]\geq\gamma\log k$ in all rounds $t\in[1,\tau(k/\log^{2}k)]$.
By Equation (4) it follows that, for sufficiently large $k$, it is sufficient
to activate at most $k/2$ stations in these rounds.

We continue the definition of the instance by switching on the remaining
stations as follows. The goal is now to guarantee
${\hat{\sigma}}[t]\geq\gamma\log k$ in all rounds
$t\in[\tau(k/\log^{2}k),k/(c^{\prime}\log\log k)]$. We switch on
$(c^{\prime}\log\log k)/2$ stations in each round
$t\in[1,k/(c^{\prime}\log\log k)]$ (note that this is possible since there are
at least $k/2$ remaining stations). Observe that in any round
$t\in[\tau(k/\log^{2}k),k/(c^{\prime}\log\log k)]$, the following inequalities
hold:

${\hat{\sigma}}[t]\geq\varsigma(k/\log^{2}k)\cdot c^{\prime}\log\log
k/2\geq\gamma\log k\ .$

Indeed, the first inequality holds because for each considered round $t$ and
for every integer $i\in[1,\tau(k/\log^{2}k)]$ there are exactly
$(c^{\prime}\log\log k)/2$ stations each contributing $p(i)$ to the sum
${\hat{\sigma}}[t]$, totaling in $(c^{\prime}\log\log k)/2$ times
$\varsigma(k/\log^{2}k)$; the second inequality follows from Equation (5).

This way we have showed that there exists an instance such that, for some
constant $c^{\prime}$, the lower bound ${\hat{\sigma}}[t]\geq\gamma\log k$
holds in rounds $t\in[1,k/(c^{\prime}\log\log k)]$. Now, recalling Equation
(3), the lemma follows. ∎

Using the activation times from Lemma 4.3, we can extend the statement of
Lemma 4.2 by proving that the transmission probabilities concentrate in some
suffix of the considered period $[1,\tau(k)]$.

######  Lemma 4.4.

For some constant $c_{2}>0$, we have

$\varsigma(k)-\varsigma(k/(c_{2}\log k\log\log k))=\Omega(\log k/\log\log k)\
.$

###### Proof.

Let $I(k/2)$ be the instance from Lemma 4.3 for $k/2$ stations. By Lemma 4.1,
for this instance, there are no successful transmissions in rounds
$1,2,\ldots,\tau((k/2)/(c_{1}\log(k/2)\log\log(k/2)))$, whp. Note that for
some constant $c_{2}$, we have
$\tau((k/2)/(c_{1}\log(k/2)\log\log(k/2)))\geq\tau(k/(c_{2}\log k\log\log
k))$. Therefore, there are no successful transmissions in rounds
$1,2,\ldots,\tau(k/(c_{2}\log k\log\log k))$, whp. Consider a station $v$ that
starts in round $1$ in instance $I(k/2)$. It follows that in round
$\tau(k/(c_{2}\log k\log\log k))$ the station is still running the protocol,
whp.

We then proceed analogously as in the proof of Lemma 4.2. We distribute
randomly the remaining $k/2$ stations in the interval $[\tau(k/(c_{2}\log
k\log\log k)),\tau(k)]$. Station $v$ has some sequence of transmissions in
this interval. Each transmission is not successful with probability larger
than $(k/2)\cdot p(1)\cdot(1/\tau(k))=\Omega(1/\log k)$. Thus, in order to
have a successful transmission with high probability, station $v$ needs to
transmit $\Omega(\log k/\log\log k)$ times in the interval $[\tau(k/(c_{2}\log
k\log\log k)),\tau(k)]$.

Therefore, the expected number of transmissions in the interval
$[\tau(k/(c_{2}\log k\log\log k)),\tau(k)]$, which is
$\varsigma(k)-\varsigma(k/(c_{2}\log k\log\log k))$, is $\Omega(\log
k/\log\log k)$. ∎

Using Lemma 4.4 in a telescopic way, we can increase the requirement on the
sum of transmission probabilities of a single station over the considered
period $\tau(k)$.

######  Lemma 4.5.

$\varsigma(k)=\Omega(\log^{2}k/(\log\log k)^{2})$.

###### Proof.

We can write down a telescoping sum, where $c_{2}$ is the constant determined
in Lemma 4.4:

$\displaystyle\varsigma(k)$ $\displaystyle=$
$\displaystyle\left(\varsigma(k)-\varsigma(k/(c_{2}\log k\log\log k))\right)+$
$\displaystyle\left(\varsigma(k/(c_{2}\log k\log\log
k))-\varsigma(k/(c_{2}\log k\log\log k)^{2})\right)+$
$\displaystyle\left(\varsigma(k/(c_{2}\log k\log\log
k)^{2})-\varsigma(k/(c_{2}\log k\log\log k)^{3})\right)+\ldots$

The thesis follows by observing that this sum has $\Omega(\log k/\log\log k)$
terms, and the first half of these terms are $\Omega(\log k/\log\log k)$ by
Lemma 4.4. ∎

We now transform the lower bound on transmission probabilities of a station
over the considered period $[1,\tau(k)]$, proved in Lemma 4.5, into the lower
bound on the sums of transmission probabilities in rounds. Using Lemma 4.5,
one can construct an instance $J(k)$ for which no successful transmission is
likely.

######  Lemma 4.6.

For any sufficiently large integer $k$ and some constant $c^{*}>0$, there is
an instance $J(k)$, which can be used by an oblivious adversary, such that the
lower bound ${\hat{\sigma}}[t]\geq\gamma\log k$ holds in all the rounds
$t\in[1,c^{*}k\log k/(\log\log k)^{2}]$.

###### Proof.

We know, by the contradictory hypothesis, that $\tau(k/\log^{2}k)=o(k/\log
k)$. By Lemma 4.5, there is a constant $d$ such that, for sufficiently large
$k$,

$\varsigma(k/\log^{2}k)\geq 2d\log^{2}k/(\log\log k)^{2}\ .$ (6)

The instance can be constructed as follows.

In each round $t\in[1,\tau(k/\log^{2}k)]$ the oblivious adversary switches on
$\gamma\log k/p(1)$ stations. This assures ${\hat{\sigma}}[t]\geq\gamma\log k$
in these rounds. One can use (no more than) $k/2$ stations in these rounds,
for sufficiently large $k$. Next, one distributes the activation times of the
other $k/2$ stations. For any constant $c>0$, which we will fix later on, the
activation times of the other $k/2$ stations can be distributed uniformly and
independently at random in rounds $t\in[1,ck\log k/(\log\log k)^{2}]$.
Recalling Equation (6), the average sum of probabilities
$E({\hat{\sigma}}[t])$ for these $k/2$ stations in rounds
$t\in[\tau(k/\log^{2}k),ck\log k/(\log\log k)^{2}]$ is at least

$\frac{k}{2}\cdot\frac{(\log\log k)^{2}}{ck\log
k}\cdot\frac{2d\log^{2}k}{(\log\log k)^{2}}=\frac{d}{c}\cdot\log k\ .$

Letting $\delta=1-(\gamma c)/d$, we have
$(1-\delta)E({\hat{\sigma}}[t])=\gamma\log k$. Hence, by the Chernoff bound,
the probability that ${\hat{\sigma}}[t]<\gamma\log k$ in any round
$t\in[\tau(k/\log^{2}k),ck\log k/(\log\log k)^{2}]$ is at most

$e^{-\delta^{2}E({\hat{\sigma}}[t])/2}=e^{-\delta^{2}\frac{d}{2c}\cdot\log
k}=k^{-(1-\frac{\gamma c}{d})^{2}\frac{d}{2c\ln 2}}.$

For a sufficiently small $c>0$, which we denote $c^{*}$, the latter quantity
can be made less than $k^{-3}$. Applying the union bound over all the rounds
of the interval $[\tau(k/\log^{2}k),ck\log k/(\log\log k)^{2}]$, we get that
the probability that there exists a round $t$ in that interval such that
${\hat{\sigma}}[t]<\gamma\log k$ is less than $k^{-1}$, for sufficiently large
$k$.

Hence, drawing a random instance using this procedure we get the desired
instance $J(k)$ with probability $1-1/k>0$, which proves that it exists. ∎

The proof of the main result is now straightforward.

Proof of Theorem 4.1. The contradiction is obtained by applying Lemma 4.1 to
the rounds specified in Lemma 4.6. Since no station transmits in instance
$J(k)$ whp $1-1/k$, station $v$ cannot achieve latency $o(k\log k/(\log\log
k)^{2})$ whp.

##  5 A non-adaptive algorithm for unknown contention

In this section we describe a non-adaptive protocol that resolves the
conflicts without having any a priori knowledge on the number $k$ of
contenders. The algorithm can be formally described as follows. Starting from
the time at which it is activated, any station executes the following protocol
SublinearDecrease$(b)$ (see Algorithm 2). It takes a constant parameter $b>0$
in input that determines the probability of success of the algorithm (the
larger $b$, the larger the probability that the algorithm succeeds).

Algorithm 2 SublinearDecrease$(b)$

1:for $j=3,4,5,\ldots,\infty$ do

2: for $b$ rounds do

3: transmit with probability $\frac{\ln j}{j}$

4: end for

5:end for

|  | $\overbrace{\hskip 85.35826pt}^{\mbox{$b$ rounds}}$ | $\overbrace{\hskip 85.35826pt}^{\mbox{$b$ rounds}}$ | $\overbrace{\hskip 85.35826pt}^{\mbox{$b$ rounds}}$ |  |
---|---|---|---|---|---|---
$u_{1}$: |  | $\ln 3/3$ | $\ldots$ | $\ln 3/3$ | $\ln 4/4$ | $\ldots$ | $\ln 4/4$ | $\ln 5/5$ | $\ldots$ | $\ln 5/5$ | … |
|  |  | $\overbrace{\hskip 85.35826pt}^{\mbox{$b$ rounds}}$ | $\overbrace{\hskip 85.35826pt}^{\mbox{$b$ rounds}}$ | $\overbrace{\hskip 85.35826pt}^{\mbox{$b$ rounds}}$ |
$u_{2}$: |  |  | $\ln 3/3$ | $\ldots$ | $\ln 3/3$ | $\ln 4/4$ | $\ldots$ | $\ln 4/4$ | $\ln 5/5$ | $\ldots$ | $\ln 5/5$ | …
|  |  |  |  |  | ⋮ |  |  |  |  |  |
Figure 4: Two stations executing the first 3 iterations of the inner for-loop
of Protocol SublinearDecrease$(b)$.

Figure 4 shows the sequence of transmission probabilities used by two stations
during the execution of the first three iterations of the inner for-loop. As
can be seen, as a consequence of not being synchronized, in many rounds they
transmit with different probabilities.

We start with proving a weaker bound on the complexity of protocol
SublinearDecrease$(b)$ that holds when acknowledgments are not allowed and
consequently a station does not switch-off after a successful transmission.
This will give a first glimpse of our proof’s technique. Later, in order to
get our final result, we will refine the analysis by considering the
acknowledgments and therefore exploiting the benefit of switching-off a
station as soon as it successfully transmits. Both variants are successful
against an adaptive adversary.

###  5.1 Analysis of the protocol without acknowledgments.

In this subsection we will prove the following theorem.

######  Theorem 5.1.

All stations executing protocol SublinearDecrease$(b)$ for a sufficiently
large constant $b$, will transmit successfully within $O(k\ln^{2}k)$ time
rounds whp, even in the case where acknowledgments are not allowed. The result
holds even against an adaptive adversary.

All the following results refer to an execution of protocol
SublinearDecrease$(b)$ for an arbitrary value of its input parameter $b$. We
start with the following two technical facts.

######  Fact 5.1.

For a sufficiently large $i$, we have $s(i)<b\ln^{2}(i/b)$.

###### Proof.

We have,

$\displaystyle s(i)$ $\displaystyle\leq$ $\displaystyle b\sum_{j=3}^{\lceil
i/b\rceil}\frac{\ln j}{j}$ $\displaystyle\leq$ $\displaystyle
b\int_{j=2}^{\lceil i/b\rceil}\frac{\ln x}{x}\,dx\;\;\;\text{ (for $i>2b)$}$
$\displaystyle=$ $\displaystyle b\cdot\frac{\ln^{2}(\lceil
i/b\rceil)-\ln^{2}(2)}{2}$ $\displaystyle\leq$ $\displaystyle b\ln^{2}(i/b).$

∎

######  Fact 5.2.

If $r=4\cdot k\ln^{2}k$, then $k\ln^{2}r<r/2$ for a sufficiently large $k$.

###### Proof.

We have, $k\ln^{2}r=k\ln^{2}(4\cdot
k\ln^{2}k)=k\ln^{2}4+k\ln^{2}k+2k\ln^{2}\ln k<2k\ln^{2}k=r/2$; where the last
inequality holds for a sufficiently large $k$. ∎

From now on we fix an arbitrary station $v$ with the aim of proving that such
a station will transmit successfully within $O(k\ln^{2}k)$ time rounds whp.
All the following rounds $t$ are referred to a reference clock corresponding
to $v$’s local clock, i.e. starting at the wake-up time of $v$. Due to the
adaptive adversary, the rounds $t:{\hat{\sigma}}[t]<1$, which are most
favourable for successful transmissions of $v$ are not known in advance.
Nevertheless the next lemma guarantees they are half of the rounds in the
aforementioned period.

######  Lemma 5.1.

Let $r=4\cdot k\ln^{2}k$. In at least $br/2$ rounds $t\in[1,br]$ we have
${\hat{\sigma}}[t]<1$.

###### Proof.

Let $r=4\cdot k\ln^{2}k$. We have,

$\displaystyle\sum_{t\in[1,br]}{\hat{\sigma}}[t]$ $\displaystyle=$
$\displaystyle\sum_{t\in[1,br]}\sum_{w\in\hat{A}[t]}q_{w}[t]$ $\displaystyle=$
$\displaystyle\sum_{w\in\hat{A}[t]}\sum_{t\in[1,br]}p(t-t_{w})$
$\displaystyle\leq$ $\displaystyle k\cdot s(br)$ $\displaystyle<$
$\displaystyle bk\ln^{2}r\mbox{ (by Fact~{}\ref{f:full-1})}$ $\displaystyle<$
$\displaystyle br/2\mbox{ (by Fact~{}\ref{f:full-2})},$

where the last two inequalities hold for a sufficiently large $k$. Thus, in at
least $br/2$ rounds $t\in[1,br]$, the sum ${\hat{\sigma}}[t]$ must be smaller
than 1. ∎

Lemma 5.1 holds for an arbitrary value of the input parameter $b$. Now, in
order to conclude the proof of Theorem 5.1, we will show that, for a suitable
choice of the constant parameter $b$, protocol SublinearDecrease$(b)$ allows
any station to transmit successfully whp within $br$ rounds, with
$r=4k\ln^{2}k$.

Proof of Theorem 5.1: Consider any station $v$ and let $r=4\cdot k\ln^{2}k$.
By Lemma 5.1, there are at least $br/2$ rounds $t\in[1,br]$ in which
${\hat{\sigma}}[t]<1$. In view of the inequality
$\sigma[t]\leq{\hat{\sigma}}[t]$, it follows that there are at least $br/2$
rounds $t\in[1,br]$ in which $\sigma[t]<1$.

By Lemma 3.1, the probability that $v$ has a successful transmission at any of
these rounds $t$ is at least $q_{v}[t]/4=p(t-t_{v})/4\geq p(br)/4$. Hence, the
probability that $v$ will not manage to transmit successfully in rounds
$1,2,\ldots,br$, is at most

$\left(1-\frac{p(br)}{4}\right)^{br/2}=\left(1-\frac{\ln
r}{4r}\right)^{br/2}<e^{-(b/8)\ln r}<k^{-b/8}\ .$

This last value can be made smaller than $k^{-\eta-1}$, for any predefined
parameter $\eta>0$, by choosing $b$ sufficiently large. Applying the union
bound over all contending stations we can derive that the probability that any
of them will not transmit successfully within the first $br$ rounds of its
activity is less than $k^{-\eta}$. This finally proves that our protocol
SublinearDecrease$(b)$ guarantees latency $br=O(k\ln^{2}k)$ whp. ∎

###  5.2 Analysis of the protocol with acknowledgments.

In this subsection we prove that if we allow each station to switch-off after
getting an acknowledgment of its own successful transmission, we can improve
the performance guarantees of protocol SublinearDecrease$(b)$ by a factor of
$\Omega(\log\log k)$.

######  Theorem 5.2.

All stations executing protocol SublinearDecrease$(b)$ for a sufficiently
large constant $b$, will transmit successfully within
$O\left(k\frac{\ln^{2}k}{\ln\ln k}\right)$ time rounds whp. The result holds
even against an adaptive adversary.

We start with the following technical fact.

######  Fact 5.3.

Let $b_{1}>0$ be a constant.

If $r=\frac{2k\ln^{2}k}{b_{1}\ln\ln k}$, then $k\ln^{2}r<\frac{b_{1}r\ln\ln
r}{2}$ for a sufficiently large $k$.

###### Proof.

For sufficiently large $k$, $\ln r<\ln k$, which implies that
$\frac{k\ln^{2}r}{\ln\ln r}<\frac{k\ln^{2}k}{\ln\ln
k}=\frac{b_{1}}{2}\frac{2k\ln^{2}k}{b_{1}\ln\ln k}=\frac{b_{1}r}{2}$. Hence,
$k\ln^{2}r<\frac{b_{1}r\ln\ln r}{2}$ for a sufficiently large $k$. ∎

Likewise we did in Subsection 5.1, we now fix a station $v$ with the intention
of showing that such an arbitrary station will transmit successfully within
$O\left(k\frac{\ln^{2}k}{\ln\ln k}\right)$ rounds whp. All the following time
rounds $t$ are refereed to a reference clock coinciding with $v$’s local
clock.

######  Lemma 5.2.

Let $b$ be an arbitrary positive integer constant. There exists a constant
$b_{1}>0$ such that for any round $t$ for which $1<\sigma[t]\leq b_{1}\ln\ln
k$, the probability that some station successfully transmits at round $t$ is
at least $16k/(br)$, where $r=\frac{2k\ln^{2}k}{b_{1}\ln\ln k}$.

###### Proof.

Fix any round $t$. The probability that some station transmits successfully at
round $t$ is

$\sum_{s\in A[t]}q_{s}[t]\prod_{s^{\prime}\neq s\in
A[t]}\left(1-q_{s^{\prime}}[t]\right)>\sigma[t]\left(\frac{1}{4}\right)^{\sigma[t]}\geq
b_{1}\ln\ln k\left(\frac{1}{4}\right)^{b_{1}\ln\ln k},$

where the first inequality follows from the observation that the transmission
probabilities are less than $1/2$ and the latter is implied by $f(x)=x\cdot
4^{-x}$ being a decreasing function for $x\geq 1$.

Continuing, we have that

$b_{1}\ln\ln k\left(\frac{1}{4}\right)^{b_{1}\ln\ln k}=\frac{b_{1}\ln\ln
k}{2^{2b_{1}\frac{\log(\ln k)}{\log e}}}=\frac{b_{1}\ln\ln k}{(\ln
k)^{2b_{1}/\log e}}.$

Finally, by choosing $b_{1}$ sufficiently small and $k$ sufficiently large,
the latter value can be made larger than

$\frac{4b_{1}\ln\ln k}{b\ln^{2}k}=\frac{16k}{br}.$

∎

In the next lemma we prove the existence of sufficiently many rounds $t$ at
which $\sigma[t]\leq b_{1}\ln\ln k$, for some constant $b_{1}>0$. Notice that,
due to the adaptive adversary, these rounds are not known in advance, but the
lemma guarantees that they will appear somewhere in the specified interval.

######  Lemma 5.3.

Let $b$ be an arbitrary positive integer constant. Suppose
$r=\frac{2k\ln^{2}k}{b_{1}\ln\ln k}$, where $b_{1}$ is the constant determined
in Lemma 5.2. In at least $br/2$ rounds $t\in[1,br]$ the sum of probabilities
$\sigma[t]$ is smaller than $b_{1}\ln\ln k$.

###### Proof.

By Fact 5.1 and Fact 5.3 we have that $k\cdot
s({br})<bk\ln^{2}r<b\cdot\frac{b_{1}r\ln\ln r}{2}$. Therefore,

$\displaystyle\sum_{t\in[1,br]}{\hat{\sigma}}[t]$ $\displaystyle=$
$\displaystyle\sum_{t\in[1,br]}\sum_{w\in\hat{A}[t]}q_{w}[t]$ $\displaystyle=$
$\displaystyle\sum_{w\in\hat{A}[t]}\sum_{t\in[1,br]}p(t-t_{w})$
$\displaystyle\leq$ $\displaystyle k\cdot s(br)$ $\displaystyle<$
$\displaystyle\frac{br}{2}\cdot b_{1}\ln\ln r.$

Thus, in at least $br/2$ rounds $t\in[1,br]$ the value ${\hat{\sigma}}[t]$ is
smaller than $b_{1}\ln\ln k$. Finally, the Lemma follows from the inequality
$\sigma[t]\leq{\hat{\sigma}}[t]$. ∎

The next lemma shows that for a sufficiently large input parameter $b$, there
are many rounds in which the sum of transmission probabilities is at most 1
whp.

######  Lemma 5.4.

Let $b,b_{1},r$ be as in Lemma 5.3. There exists $k_{0}$ not depending on
$b,b_{1},r$ such that for $k\geq k_{0}$, in any execution of the protocol, the
probability that $\sigma[t]\leq 1$ in at least $br/4$ rounds $t\in[1,br]$, is
at least

$1-\frac{1}{2k^{\eta+1}}.$

###### Proof.

By Lemma 5.3 there are at least $br/2$ rounds $t\in[1,br]$ in which
$\sigma[t]\leq b_{1}\ln\ln k$. Let $R$ be the set of these rounds and $X$ be
the event that there are at least $br/4$ rounds $t\in R$ such that
$1<\sigma[t]\leq b_{1}\ln\ln k$. By Lemma 5.2 in each of such rounds the
probability of a successful transmission is at least $16k/(br)$. To prove the
lemma it will suffice to show that whp event $X$ will not occur.

Let $T=t_{1},t_{2},\ldots,t_{m}$, with $t_{1}<t_{2}<\cdots<t_{m}$, be the
sequence of rounds in $R$ such that $1<\sigma[t_{i}]\leq b_{1}\ln\ln k$, for
$i=1,2,\ldots,m$. For any execution of protocol SublinearDecrease$(b)$, we can
define the following binary sequence
$\rho=\rho_{1},\rho_{2},\ldots,\rho_{\ell}$, of length $\ell=br/4$ (all random
choices are made independently).

  1. 1.

If in round $t_{i}\in T$ there is no successful transmission, we set
$\rho_{i}=0$.

  2. 2.

If in round $t_{i}\in T$ there is a successful transmission, then we set
$\rho_{i}$ randomly so that $\Pr(\rho_{i}=1)=16k/(br)$. This is done as
follows. Let $p_{i}=\sum_{v\in{A}[t_{i}]}q_{v}[t_{i}]\prod_{w\neq
v}(1-q_{w}[t_{i}])$ be the probability of having a successful transmission at
round $t_{i}$, we set

$\rho_{i}=\begin{cases}1,&\text{with probability}\ (1/p_{i})[16k/(br)];\\\
0,&\text{with probability}\ 1-(1/p_{i})[16k/(br)].\end{cases}$

  3. 3.

If there are less than $br/4$ rounds in $T$, the lacking $\ell-m$ entries of
$\rho$ are added by tossing a biased coin which assigns 1 with probability
$16k/(br)$ and 0 with probability $1-16k/(br)$.

In this way, $\rho$ has length $\ell=br/4$ and each entry is independently set
to 1 with probability exactly $16k/(br)$. Notice that at most $k$ 1’s can be
attributed by step (2), as there are at most $k$ stations and each of them can
successfully transmit only once, as it switches-off immediately after. So, if
there are more than $k$ 1’s in the sequence $\rho$, then this exceeding amount
of 1’s must have been produced by the coin tosses in step (3). This implies
that $m<\ell=(br)/4$ and therefore $X$ does not occur. Hence, to finish the
proof we need only to show that $\rho$ contains more than $k$ 1’s whp.

The expected number of 1’s in $\rho$ is $\mu=\ell\cdot 16k/(br)=4k$. Letting
$\delta=3/4$, the probability that the number of 1’s in $\rho$ is at most
$(1-\delta)\mu=k$ is, by the Chernoff bound, no more than
$e^{\delta^{2}\mu/2}=e^{-(3/4)^{2}4k/2}$. This value can be made smaller than
$1/(2k^{\eta+1})$, for any predefined parameter $\eta>0$, by choosing $k$
sufficiently large, i.e. for $k\geq k_{0}$, where $k_{0}$ is a constant not
depending on $b,b_{1}$ and $r$. ∎

Now we are ready to prove the main result of this section.

Proof of Theorem 5.2: Fix a parameter $\eta>0$ and let
$r=\frac{2k\ln^{2}k}{b_{1}\ln\ln k}$, for some constant $b_{1}$ determined in
Lemma 5.2. We will show that there exists an input constant $b$ for our
protocol such that $v$ will transmit successfully within the first $br$ rounds
of its activity.

Let $S\subseteq[1,br]$ be a set of rounds, with $|S|\geq br/4$, such that for
every $t\in S$, $\sigma[t]\leq 1$.

By Lemma 3.1, the probability of having a successful transmission for $v$ in
any $t\in S$ is at least $q_{v}[t]/4=p(t-t_{v})/4\geq p(br)$. Thus, the
probability that $v$ will not send its message successfully during all the
rounds in $S$ is no more than

$(1-p(br)/4)^{br/4}=\left(1-\frac{\ln r}{4r}\right)^{br/4}<e^{-b\ln
r/16}=\left(\frac{2k\ln^{2}k}{b_{1}\ln\ln k}\right)^{-b/16}\leq k^{-b/16},$

where the last inequality holds for sufficiently large $k$. By chosing an
input value $b$ sufficiently large, the latter value can be made less than
$1/(2k^{\eta+1})$.

By Lemma 5.4, the probability that such a set $S$ does not exist is less than
$1/(2k^{\eta+1})$, for $k$ sufficiently large.

Thus, the probability that $v$ does not transmit successfully during its first
$br$ rounds is smaller than $1/k^{\eta+1}$. Finally, taking the union bound
over all contending stations, it follows that all stations transmit
successfully within the first $br$ rounds of its activity with probability
larger than $1-1/k^{\eta}$. ∎

We conclude the section with the following simple theorem on the energy cost
of our protocol.

######  Theorem 5.3.

The total number of broadcast attempts during the execution of Protocol
SublinearDecrease$(b)$ is $O(k\log^{2}k)$ whp. The result holds even against
an adaptive adversary.

###### Proof.

Theorems 5.1 and 5.2 guarantee that any station will transmit successfully
within $O\left(k\ln^{2}k\right)$ rounds whp, regardless if acknowledgments are
allowed or not. By Fact 5.1, the expected number of transmissions within such
time interval (which is polynomial in $k$) is $O(\log^{2}k)$. Since the
broadcast attempts of a single station are independent over rounds, by using
the Chernoff bound for each station to upper bound the number of transmissions
and then the union bound over all stations, we get $O(\log^{2}k)$
transmissions for every station, whp. This implies a total of $O(k\log^{2}k)$
broadcast attempts whp. ∎

##  6 An adaptive algorithm for unknown contention

In Section 4 we have shown that, for non-adaptive algorithms, the lack of
knowledge of contention’s size, or even its linear approximation, makes the
problem complexity provably higher. However, in this section we prove that
adaptive algorithms could overcome this obstacle. We now describe a protocol
AdaptiveNoK, which resolves the contention with linear latency without any
knowledge of contention size. Besides the data packet itself, each station can
send a one-bit control message. For the sake of presentation we will refer to
these control messages as $<$D mode$>$ (encoded with bit 0) and $<$any
D-station left?$>$ (encoded with bit 1).

The algorithm works by alternating between two modes: leader election mode and
dissemination mode. The first mode aims at getting a synchronized subset of
stations and electing a leader. The task of the leader will be to coordinate
the computation in the dissemination mode, which aims at the actual contention
resolution among the synchronized subset of stations defined in the previous
execution of the leader election mode. During the dissemination mode the
leader has also the task to send periodically a message $<$D mode$>$ which
informs newly awakened stations about the mode currently executed. A formal
description of the modes and actions can be found in the pseudocode of
Protocol 3.222Here we assume that a station does not automatically switch off
after sending successfully, but, taking advantage of being already selected,
continues its activity coordinating the transmissions of the other stations.
This is allowed due to the assumed adaptiveness of the algorithm. Moreover,
the stations other than transmitting their own messages, can exchange other
information of limited (logarithmic) size; in our adaptive protocol, such
control messages have only one bit. A newly awakened station first listens for
$4$ rounds in order to determine the current mode of the system (cf. line 2).
In the leader election mode (L mode) the stations execute a wake-up protocol,
whose goal is to get just one successful transmission. For this task, we use
protocol DecreaseSlowly introduced in [29] (cf. the pseudocode of Protocol 4).
Once a successful transmission appears in some round $t$, the station which
transmitted in $t$ becomes the leader, it sets up a new variable time_counter
to $0$, and then the dissemination mode (D mode) starts. At this point the
leader and all other stations that were alive at $t$, are synchronized. Let us
denote by $C$ such a synchronized subset of stations without a leader. We can
assume that a global clock (represented by variable time_counter initiated by
the leader) starts for all the stations in $C$ at the round in which the
leader was elected. This allows us to use any contention resolution protocol
for the synchronized (i.e., static) model with unknown $k$ as a black-box – we
will call it SUniform.

Algorithm 3 AdaptiveNoK (executed by a station $u$)

1:$\mbox{{\sc status}}\leftarrow\emptyset$

2:while $\mbox{{\sc status}}\not=L$ do /*  newly woken up stations can only
enter the computation in $L$ mode */

3: listen to the channel for 4 rounds

4: if $u$ does not receive any message OR it receives message $<$is there
anybody out there?$>$ then

5: $\mbox{{\sc status}}\leftarrow L$

6: end if

7:end while

8:while $u$ is active do

9: if $\mbox{{\sc status}}=L$ then

10: execute DecreaseSlowly /*  the first successful station becomes the leader
*/

11: ${\tt time\\_counter}\leftarrow 0$ /*  now all awaken stations are
synchronized and ${\tt time\\_counter}$ will denote the current round number
started at the time the leader has been elected */

12: $\mbox{{\sc status}}\leftarrow D$ /*  once a leader has been elected the
station switches to the dissemination mode */

13: end if

14: if $\mbox{{\sc status}}=D$ then

15: if ${\tt time\\_counter}$ is odd then

16: if $u$ is not the leader then

17: execute SUniform$(u)$ (switch-off at the first successful transmission)

18: end if

19: else if ${\tt time\\_counter}=2^{x}$ for some integer $x\geq 1$ then

20: transmit $<$is there anybody out there?$>$

21: if this transmission is successful $\And$ $u$ is the leader then

22: switch-off /*  if the leader gets an acknowledgement, it switches-off and
the dissemination mode terminates */

23: end if

24: else

25: if $u$ is the leader then

26: transmit $<$D mode$>$ /*  as far as the leader is alive, the dissemination
mode continues */

27: end if

28: end if

29: end if

30:end while

Algorithm 4 DecreaseSlowly (executed by a station $u$)

1:$q\leftarrow$ some constant $>0$

2:$i\leftarrow$0

3:while $u$ is active do

4: transmit the message with probability $q\cdot\frac{1}{2q+i}$

5: if transmission is successful then

6: become a leader

7: end if

8: $i\leftarrow i+1$

9:end while

#### Protocol SUniform.

In order to implement SUniform, we can use one of the preexisting Back-
on/Back-off protocols, which guarantee that all stations transmit successfully
within $O(k)$ rounds after the synchronization round, whp. As pointed out in
[7], the idea of Back-on/Back-off (also known as Sawtooth Back-off) was
discovered in other contexts many years ago [26, 19]. This is a non-monotonic
back-off strategy defining a sequence of contention windows within which any
station chooses uniformly its transmitting round. It works in a doubly nested
loop. The outer loop doubles the contention window at each step, with the goal
of “guessing” a window size proportional to the number of competing stations.
For each such step, the innermost loop repeatedly fractions it until it
reaches size 1, so to progressively halving the number of active stations. The
number of such nested iterations is clearly $O(\log^{2}T)$, where $T$ is the
total number of rounds until termination. Gerèb-Graus and Tsantilas [26]
considered the problem of realizing arbitrary $h$-relations in a $n$-node
network. In an $h$-relation, each processor is both the source and the
destination of at most $h$ messages. Setting $n=k$ and $h=k$, a solution to
this problem can be used to solve our contention resolution among $k$
synchronized stations. The protocol of [26] realizes an $h$-relation in a
$n$-node network in $\theta(h+\log n\log\log n)$ rounds whp. Hence, translated
into our terminology and adapted to our needs, the result of [26] can be
restated as follows (see Theorem 4.2 in [26]).

######  Theorem 6.1 ([26]).

Protocol SUniform solves the contention among $k$ synchronized stations within
$T$ rounds, where $T=O(k)$, whp, i.e. with probability at least
$1-1/n^{\alpha}$ for any predefined constant $\alpha>0$. It uses
$O(\log^{2}T)$ transmissions per station.

In order to use protocol SUniform as a black-box, we need some additional
synchronization mechanism inside the protocol itself and with respect to the
main algorithm, which is described next.

First, during an execution of SUniform, all stations from set $C$ switch off
directly after a successful transmission (are not active anymore), while all
stations which are currently waking up are waiting until the end of this
particular execution of SUniform.

Second, in order to make possible that the stations can distinguish between
both modes after waking up, the algorithm SUniform is executed in odd rounds
only, while even rounds are devoted to performing the following kind of
coordination.

In rounds expressible as $2^{x}$ for integers $x>1$, all alive stations from
set $C$ and the leader transmit together the message $<$is there anybody out
there?$>$. In the remaining even rounds, the leader broadcasts the message
$<$D mode$>$. The latter transmission, which is surely successful as it is
performed by the leader only, informs the newcomers to stay silent until the
dissemination mode hasn’t finished. In order to understand when the $D$ mode
has terminated, the outcome of the former transmission (message $<$is there
anybody out there?$>$), is used. There are two cases.

1) If the leader receives an acknowledgment on such a transmission, then it
knows that it was the only transmitter (all stations in $C$ successfully
transmitted and switched off). In this case, the leader itself switches-off
and the $<$D mode$>$ message is suspended (cf. line 22).

2) If the leader does not receive an acknowledgment, it knows that there are
still some stations in $C$ which have not succeeded in transmitting a message.
Consequently, the leader keeps transmitting the $<$D mode$>$ message (cf. line
26).

Notice that at most 4 consecutive rounds would be needed to the leader, as far
as it is still alive, to send the message $<$D mode$>$ (one even round might
be skipped if it is a power of 2 larger than 2).

Now we can see how the control messages guarantee an alternation between the
two modes until no new station arrives in the system, which causes the
algorithm to stop.

#### Controlling modes.

When a first group of stations is activated (so that there is no station
already active in the system), no message can be received during the execution
of the first while loop, and so an $L$ mode is started by these stations: they
exit the loop and execute protocol DecreaseSlowly to elect a leader. Any
station that possibly wakes up during this $L$ mode, either perceives the
successful transmission of the leader election during the 4 rounds of waiting
or nothing. The condition in line 4 guarantees that in the first case the
station keeps waiting, while the latter case causes the station to exit the
loop and join the leader election.

Once a leader has been elected, all (and only) the stations that participated
to the election, start a $D$ mode. Any station that possibly wakes up during
this $D$ mode, keeps waiting in the first while loop until it gets a $<$D
mode$>$ message. Once the $D$ mode terminates, the leader receives an
acknowledgement on its transmission $<$is there anybody out there?$>$. In such
a case, all newcomers that were waiting in the while loop, either receive this
acknowledgement or (if they were activated just after) they don’t receive a
$<$D mode$>$ message. In both cases, they learn that the dissemination mode
has terminated and the condition in line 4 guarantees that they exit the loop
and start a new leader election.

This process is iterated until no new station is injected in the system, which
happens when a $D$ mode finishes and no station is waiting in the while loop.

###  6.1 Analysis

The correctness and the time complexity of this algorithm will be proved in
Theorem 6.3. The first step is to show that protocol DecreaseSlowly wakes up
the system in $O(k)$ rounds whp. In [29], an algorithm Decrease Slowly has
been presented which completes the wake-up in $O(k\log k)$ rounds whp. In the
following theorem, we improve the analysis and show that actually this
algorithm can complete the wake-up in $O(k)$ rounds whp.

######  Theorem 6.2.

Algorithm DecreaseSlowly finishes wake-up in $O(k)$ rounds whp. This results
holds even for an adaptive adversary.

###### Proof.

Let us consider the first $32qk$ rounds following the round at which the first
station wakes up and starts the computation. We will prove that by the end of
this interval the wake up has been accomplished whp.

Following the algorithm, each awake station, starting from the round at which
it wakes up, transmits with probability
$q\cdot\frac{1}{2q},q\cdot\frac{1}{2q+1},q\cdot\frac{1}{2q+2},\ldots$ If we
denote by $p_{i}$ the transmission probability of an arbitrary awake station
$u$ at the $i$th round of its computation, we have that the sum of
transmission probabilities of $u$ over $32qk$ rounds is

$s(32qk)=\sum_{i=0}^{32qk}p_{i}\leq
q\left(\sum_{i=0}^{32qk}\frac{1}{i}\right)\leq q(1+\ln(32qk))\ ,$ (7)

where in the last step we have used the known bounds for the $\delta$th
partial sum $H_{\delta}$ of the harmonic series:

$\ln(1+h)\leq H_{\delta}=\sum_{i=1}^{h}\frac{1}{i}\leq 1+\ln h\ .$ (8)

For any fixed round $t$, let us consider now the sum of transmission
probabilities of all awake stations at time $t$, denoted as in the previous
section by $\sigma[t]$. Recalling that $A[t]$ is the set of active stations at
round $t$, the probability that a station successfully transmits at round $t$
is

$\displaystyle\sum_{v\in A[t]}q_{v}[t]\cdot\prod_{w\neq v}(1-q_{w}[t])$
$\displaystyle=$ $\displaystyle\sum_{v\in A[t]}q_{v}[t]\cdot\prod_{w\neq
v}(1-q_{w}[t])^{\frac{1}{q_{w}[t]}q_{w}[t]}$ (9) $\displaystyle\geq$
$\displaystyle\sum_{v\in A[t]}q_{v}[t]\cdot\prod_{w\neq v}(1/4)^{q_{w}[t]}$
$\displaystyle>$ $\displaystyle\sigma[t]\cdot(1/4)^{\sigma[t]}.$

Since at most $k$ stations can be awake in each round, for any adversarial
wake-up strategy, the average sum $\sigma[t]$ for $t$ ranging over our
interval of $32qk$ rounds will be

$\frac{1}{32qk}\sum_{t=0}^{32qk}\sigma[t]\leq\frac{q(1+\ln(32qk))\cdot
k}{32qk}\leq\frac{\ln(32qk)}{16}\ .$

Of course, in at least half of the interval, $\sigma[t]$ must be not larger
than twice the average; therefore there is a set $T$ of at least $16qk$ rounds
such that

$\sigma[t]\leq\frac{\ln(32qk)}{8}\ ,$ (10)

for every $t\in T$. Let us consider only rounds in $T$. We say that a round
$t$ is heavy when $\sigma[t]>1/2$ and light otherwise. We distinguish two
complementary cases, thus in each execution caused by an adaptive adversary
one of them must occur. We will show that in each of these cases, no matter
how the heavy and light rounds are distributed, the wake-up occurs whp. Then,
summing up the conditional probabilities over all possible distributions of
heavy and light rounds, and by taking the union bound of the two cases, the
theorem holds. Hence, it remains to analyze these two cases.

  1. 1.

There are at least $8qk$ heavy rounds. Recalling also (10), in at least $8qk$
rounds $t$, it holds that

$\frac{1}{2}<\sigma[t]\leq\frac{\ln(32qk)}{8}\ .$ (11)

Plugging (11) into (9), we get that the success probability at round $t$ is at
least

$\frac{1}{2}\cdot\left(\frac{1}{4}\right)^{\frac{\ln(32qk)}{8}}\geq\left(\frac{1}{16}\right)^{\frac{\ln(32qk)}{8}}\geq\frac{1}{\sqrt{32qk}}\
.$

Therefore, the probability that the wake-up does not appear in $8qk$ heavy
rounds is at most $(1-1/\sqrt{32qk})^{8qk}=O(1/k^{a})$ for an arbitrary
constant $a$ depending on $q$.

  2. 2.

There are less than $8qk$ heavy rounds. So, there are at least $\delta=8qk$
light rounds. Let $t_{1},t_{2},\ldots,t_{\delta}$ be the time-ordered sequence
of light rounds. It is possible to show by induction on $i$ (cf. Claim 1 in
the proof of Theorem 10.3) that $\sigma[t_{i}]\geq q/(2q+i)$, for $1\leq
i\leq\delta$. Consequently,

$q/(2q+i)\leq\sigma[t_{i}]\leq 1/2,\mbox{ for }1\leq i\leq\delta.$

Plugging these bounds into (9) we get that the probability of successfully
waking up in the $i$th light round is at least $q/2(2q+i)$. Hence, the
probability that the wake-up is not successful is at most

$\displaystyle\prod_{i=1}^{\delta}(1-\sigma[t_{i}])$ $\displaystyle\leq$
$\displaystyle\prod_{i=1}^{\delta}\left(1-\frac{q}{2(2q+i)}\right)$
$\displaystyle\leq$
$\displaystyle\left(\frac{1}{e}\right)^{\sum_{i=1}^{\delta}\frac{q}{2(2q+i)}}\leq\left(\frac{1}{e}\right)^{\frac{q}{2}(\sum_{i=1}^{\delta}\frac{1}{i}-\sum_{i=1}^{2q}\frac{1}{i})}$
$\displaystyle=$
$\displaystyle\left(\frac{1}{e}\right)^{\frac{q}{2}(H_{\delta}-H_{2q})}\leq\left(\frac{1}{e}\right)^{\frac{q}{2}(\ln(1+\delta)-\ln(4q))}\;\;\;\mbox{
(by (\ref{harmonic}))}$ $\displaystyle=$
$\displaystyle\left(\frac{4q}{1+8qk}\right)^{q/2}\leq\left(\frac{1}{2k}\right)^{q/2}.$

∎

The following lemma shows that once a station enters the computation in $L$
mode, i.e. after it has left the first while loop in line 2 of Protocol
AdaptiveNoK, it reaches a successfull transmission within $O(k)$ rounds whp.
The final theorem will further consider the time spent inside the first while
loop.

######  Lemma 6.1.

A station $u$ sends successfully whp in $O(k)$ rounds after exiting the while
loop in line 2 of Protocol AdaptiveNoK.

###### Proof.

A station $u$ that exits the while loop in line 2 is in $L$ mode. In $L$ mode,
the station executes Protocol DecreaseSlowly which, by Theorem 6.2, allows one
of the participating stations to transmit successfully to the channel within
$O(k)$ rounds whp. The successful station becomes the leader and the status
changes to $D$ mode. Obviously, if $u$ is such a station, then we have proved
the lemma. Therefore, suppose that $u$ is not the leader. Starting from the
time at which the leader has been elected, all stations that were active at
that time are synchronized, i.e., they can start a clock at the time of the
leader election (round ${\tt time\\_counter}=0$). Let $v\not=u$ be the leader
and $A$ be the set of all other active stations synchronized at round 0
(according to the time_counter). In such a situation, $u$ and all other
stations in $A$ execute (in rounds in which time_counter is odd) protocol
SUniform guaranteeing by Theorem 6.1 contention resolution in $O(k)$ time whp
for the static model, i.e., when all participating stations start at the same
time, which is our situation. This concludes the proof. ∎

Finally, we are ready for the main theorem of this section.

######  Theorem 6.3.

Algorithm AdaptiveNoK solves the contention resolution problem with latency
$O(k)$, whp. The result holds even against an adaptive adversary.

###### Proof.

Our aim is to show that any fixed station $u$ executing AdaptiveNoK transmits
successfully its message within $O(k)$ rounds since its wake up time, whp. In
view of Lemma 6.1, it is sufficient to show that the station exits the while
loop in line 2 within $O(k)$ rounds.  Two cases can occur.

If $D$ mode is not running, the station exits the loop within 4 rounds.
Indeed, in such a case, either the station hasn’t received any message or it
has got the message $<$is there anybody out there?$>$. This corresponds to the
condition in line 4 which causes the station to leave the while loop.

If $D$ mode is running, the station stays in the while loop as long as it
keeps receiving message $<$D mode$>$.  Let us call white rounds the even
rounds expressible as $2^{x}$ for integers $x>1$, and black rounds all the
remaining even rounds. The message $<$D mode$>$ is sent by the leader when it
executes line 26, which happens in every black round, unless it got an
acknowledgement in the last execution of line 22 and switched off. Being two
consecutive black rounds at most 4 rounds apart, it will suffice to wait at
most 4 rounds for a newly woken up station to establish whether the leader is
still sending its message $<$D mode$>$. Since the delay between the
acknowledgement and the first subsequent black round is at most 2 rounds, it
will be sufficient to show that the leader gets the acknowledgement after
$O(k)$ rounds. Notice that such an acknowledgement is perceived if and only if
the leader is the only sender, that is, if and only if all stations that
started the execution of SUniform have switched off. Therefore, the leader
will get the acknowledgement in the first white round following the switching
off of all stations running SUniform, which happens after at most twice the
running time of SUniform.

The proof now follows by observing that, by Theorem 6.1, after $O(k)$ rounds
whp all the stations executing SUniform have switched off.

∎

We now conclude the section by deriving the energy cost of our adaptive
algorithm.

######  Theorem 6.4.

The expected total number of broadcast attempts during the execution of
protocol AdaptiveNoK is $O(k\log^{2}k)$. The result holds even against an
adaptive adversary.

###### Proof.

Starting in $L$ mode, the system alternates between $L$ mode and $D$ mode
until it happens that no newcomer arrives during the last $D$ mode. Therefore,
the entire round sequence of the algorithm, from start to finish, can be
partitioned into $\tau>0$ disjoint intervals
$L_{1},D_{1},L_{2},D_{2},\ldots,L_{\tau},D_{\tau}$, where $L_{j}$
(respectively $D_{j}$) is the time interval within which the system is
involved in the $j$th $L$ mode (respectively $D$ mode) and $D_{\tau}$ is the
time interval of the last $D$ mode, i.e. the one such that no new station
arrives during its execution.

For $1\leq j\leq\tau$, let $S_{j}$ be the set of stations active during the
interval $L_{j},D_{j}$. This is the set of stations that participate to the
$j$th leader election and to the subsequent dissemination mode. Recalling that
each of these stations permanently switches off by the end of this $D$ mode,
the sequence $(S_{1},S_{2},\ldots,S_{\tau})$ form a partition of the total set
of $k$ stations. To prove the theorem we will show that the expected total
number of transmissions needed during the time interval $L_{j},D_{j}$ is
$O(\kappa\log^{2}\kappa)$, where $\kappa=|S_{j}|$. By the linearity of
expectation, the theorem follows. Let us consider the execution during an
arbitrary $L_{j},D_{j}$ time interval. We count the transmissions needed in
$L_{j}$ and $D_{j}$ separately.

#### Transmissions in $L_{j}$.

For an arbitrary set of $\kappa$ stations executing this $L$ mode, let
$X(\kappa)$ and $Y(\kappa)$ be the random variables denoting respectively the
total number of transmissions spent by all stations during the time interval
$L_{j}$ and the size of $L_{j}$, i.e., the number of rounds until the first
successful transmission in protocol DecreaseSlowly. The expected total number
of transmissions is

$\displaystyle\mathbf{E}\big{(}X(\kappa)\big{)}$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{\infty}\Pr\Big{(}\Omega(\kappa^{i-1})\leq
Y(\kappa)\leq
o(\kappa^{i})\Big{)}\;\mathbf{E}\Big{(}X(\kappa)\big{|}\;\Omega(\kappa^{i-1})\leq
Y(\kappa)\leq o(\kappa^{i})\Big{)}$ (12) $\displaystyle\leq$
$\displaystyle\sum_{i=1}^{\infty}\Pr\Big{(}Y(\kappa)\geq\Omega(\kappa^{i-1})\Big{)}\;\mathbf{E}\Big{(}X(\kappa)\big{|}\;Y(\kappa)\leq
O(\kappa^{i})\Big{)}\ .$

We can now prove by induction that for any $i\geq 1$,

$\Pr\Big{(}Y(\kappa)\geq\Omega(\kappa^{i-1})\Big{)}\leq\Pr\Big{(}Y(\kappa^{i-1})\geq\Omega(\kappa^{i-1})\Big{)}=O\left(\frac{1}{\kappa^{i-1}}\right)\
.$ (13)

For $i=1$ the assertion is obvious. For $i\geq 2$, if protocol DecreaseSlowly
needs $\Omega(\kappa^{i-1})$ rounds on an input instance of $\kappa$ stations
even more so on an input instance of $\kappa^{i-1}\geq\kappa$ stations. That
is,
$\Pr\Big{(}Y(\kappa)\geq\Omega(\kappa^{i-1})\Big{)}\leq\Pr\Big{(}Y(\kappa)\geq\Omega(1)\Big{)}$,
for $i\geq 2$. The equality of (13) derives from Theorem 6.2, which on an
instance of $\kappa^{i-1}$ stations guarantees that the protocol terminates
within $O(\kappa^{i-1})$ rounds with high probability.

If we are given the information that the protocol terminates within
$O(\kappa^{i})$ rounds, then the expected total number of transmissions can be
obtained as follows,

$\mathbf{E}\Big{(}X(\kappa)\big{|}\;Y(\kappa)\leq
O(\kappa^{i})\Big{)}=\kappa\cdot\sum_{i=0}^{O(\kappa^{i})}q/(2q+i)=O(\kappa\log(\kappa^{i}))\
,$ (14)

where the equality follows by (7) and (8). Hence, plugging (13) and (14) into
(12), we get

$\mathbf{E}\big{(}X(\kappa)\big{)}\leq\sum_{i=1}^{\infty}O\left(\frac{1}{\kappa^{i-1}}\right)O(i\cdot\kappa\log\kappa)=O(\kappa\log\kappa)\
.$

#### Transmissions in $D_{j}$.

Here we need to count the transmissions required by protocol SUniform plus
those spent by the leader and the other synchronized stations during the
dissemination mode. If we let $X(\kappa)$ and $Y(\kappa)$ relate to $D_{j}$
(rather than $L_{j}$), we can observe that the expected number of
transmissions per station is again described by (12). The running time of this
$D$ mode is dominated by the number of rounds of SUniform. Hence, the upper
bound on (13) is also preserved, as Theorem 6.1 guarantees that SUniform on an
instance of $\kappa^{i-1}$ stations terminates within $O(\kappa^{i-1})$ rounds
after the synchronization round, whp.

Theorem 6.1 also states that if the protocol terminates within $O(\kappa^{i})$
rounds, then the number of transmissions spent by any station is
$O(\log^{2}(\kappa^{i}))$. If the protocol terminates within $O(\kappa^{i})$
rounds, then the leader transmits $O(k^{i})$ times and the other synchronized
stations involved in the dissemination mode, transmit only in rounds
expressible as powers of two, which are $O(\log(\kappa^{i}))$. Hence, (14) in
this case writes as

$\mathbf{E}\Big{(}X(\kappa)\big{|}\;Y(\kappa)\leq
O(\kappa^{i})\Big{)}=O(\kappa^{i}+\kappa\log^{2}(\kappa^{i})+\kappa\log(\kappa^{i}))\
.$

Now, if we choose $\alpha\geq 2$ in Theorem 6.1, we can make the probability
of failure for SUniform, on an instance of $\kappa^{i-1}$ stations, at most
$1/k^{2(i-1)}$. Consequently,

$\mathbf{E}\big{(}X(\kappa)\big{)}\leq\sum_{i=1}^{\infty}\frac{1}{\kappa^{2(i-1)}}O\left(\kappa^{i}+\kappa\log^{2}(\kappa^{i})+\kappa\log(\kappa^{i})\right)=\kappa\log^{2}\kappa\
.$

This proves that the expected total number of transmissions spent during the
interval of rounds $L_{j},D_{j}$ is $O(|S_{j}|\log^{2}|S_{j}|)$, for
$j=1,2,\ldots,\tau$. Recalling that $(S_{1},S_{2},\ldots,S_{\tau})$ is a
partition of the set of $k$ stations, by the linearity of expectation, the
theorem follows.  ∎

##  7 Discussion and open problems

Although our algorithms reach optimal or almost optimal latency and
transmission energy cost, one could ask about their efficiency in terms of the
number of listening slots. Non-adaptive algorithms have the clear advantage
that they do not need to listen to the channel. As for our adaptive algorithm,
its worst-case performance in terms of listening slots is incurred by newly
awaken stations in the very beginning of the algorithm, in particular, a
single such station could spend even $\Theta(k)$ slots listening and waiting
to change its mode to $L$. Moreover, the number of such awaiting stations
could be $\Theta(k)$, therefore even an amortized number of listening slots
per process could be as high as $\Theta(k)$. Reducing this cost without
harming latency or transmission energy is a challenging open problem, as it
also limits information flow. We conjecture, however, that such a reduction to
polylogarihmic formula per station should be doable.

Another interesting open direction is to study trade-offs between energy
consumption and other measures. In particular, is logarithmic energy necessary
for anonymous shared channel against an adaptive adversary in order to achieve
the minimum possible (asymptotically) latency $O(k)$? If so, could we lower
the energy requirement by allowing slightly larger latency, and if so, how
much larger?

There are also other model features that may influence performance of
contention resolution. For instance, the availability of a global clock may
improve synchronization, but could it be asymptotically better than the more
natural setting without global clock? If, e.g., the stations have access to a
global clock and all stations get acknowledgments of all transmissions, they
can easily solve the contention resolution problem with latency $O(k)$. They
can do it by using the wakeup UFR algorithm from paper [29]. Wakeup is
performed in odd rounds and in even rounds all stations transmit with the
probability from the last successful wakeup round. Every station switches off
after transmitting its message successfully. This approach should assure
maintaining optimal transmission probabilities of stations for a constant
fraction of active time. Will global clock be also useful, if the transmitting
station only gets acknowledgements? On the other hand, failures or external
interference may substantially worsen the performance, depending on their
severity and intensity – as it does in other related settings (c.f., job
scheduling on wireless channel under jamming and failures [5, 30]).

## References

  * [1] Norman Abramson.  The aloha system: Another alternative for computer communications.  In Proceedings of the November 17-19, 1970, Fall Joint Computer Conference, AFIPS ’70 (Fall), page 281–285, New York, NY, USA, 1970. Association for Computing Machinery.
  * [2] Dan Alistarh, Seth Gilbert, Rachid Guerraoui, Zarko Milosevic, and Calvin Newport.  Securing every bit: Authenticated broadcast in radio networks.  In Proceedings of the Twenty-Second Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’10, page 50–59, New York, NY, USA, 2010. Association for Computing Machinery.
  * [3] Lakshmi Anantharamu, Bogdan S. Chlebus, Dariusz R. Kowalski, and Mariusz A. Rokicki.  Medium access control for adversarial channels with jamming.  In Adrian Kosowski and Masafumi Yamashita, editors, Structural Information and Communication Complexity, pages 89–100, Berlin, Heidelberg, 2011\. Springer Berlin Heidelberg.
  * [4] A. Fernández Anta, M. A. Mosteiro, and J. Ramon Mu noz.  Unbounded contention resolution in multiple-access channels.  Algorithmica, 67:295–314, 2013.
  * [5] Antonio Fernández Anta, Chryssis Georgiou, Dariusz R. Kowalski, and Elli Zavou.  Adaptive packet scheduling over a wireless channel under constrained jamming.  Theor. Comput. Sci., 692:72–89, 2017.
  * [6] Baruch Awerbuch, Andrea Richa, and Christian Scheideler.  A jamming-resistant mac protocol for single-hop wireless networks.  In Proceedings of the Twenty-Seventh ACM Symposium on Principles of Distributed Computing, PODC ’08, page 45–54, New York, NY, USA, 2008. Association for Computing Machinery.
  * [7] M. A. Bender, M. Farach-Colton, S. He, B. C. Kuszmaul, and C. E. Leiserson.  Adversarial contention resolution for simple channels.  In Proceedings, 17th Annual ACM Symposium on Parallel Algorithms (SPAA), pages 325–332, New York, NY, USA, 2005. ACM.
  * [8] M. A. Bender, T. Kopelowitz, S. Pettie, and M. Young.  Contention resolution with log-logstar channel accesses.  In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (STOC), pages 499–508, Cambridge, MA, USA, 2016. ACM.
  * [9] Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Maxwell Young.  Scaling exponential backoff: Constant throughput, polylogarithmic channel-access attempts, and robustness.  J. ACM, 66(1), dec 2018.
  * [10] Michael A. Bender, Tsvi Kopelowitz, William Kuszmaul, and Seth Pettie.  Contention resolution without collision detection.  In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, page 105–118, New York, NY, USA, 2020. Association for Computing Machinery.
  * [11] Dimitri Bertsekas and Robert Gallager.  Data Networks (2nd Ed.).  Prentice-Hall, Inc., USA, 1992.
  * [12] J. Capetanakis.  Tree algorithms for packet broadcast channels.  IEEE Transactions on Information Theory, 25:505–515, 1979.
  * [13] Yi-Jun Chang, Wenyu Jin, and Seth Pettie.  Simple Contention Resolution via Multiplicative Weight Updates.  In Jeremy T. Fineman and Michael Mitzenmacher, editors, 2nd Symposium on Simplicity in Algorithms (SOSA 2019), volume 69 of OpenAccess Series in Informatics (OASIcs), pages 16:1–16:16, Dagstuhl, Germany, 2018. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [14] B. S. Chlebus.  Randomized communication in radio networks.  In P. M. Pardalos, S. Rajasekaran, J. H. Reif, and J. D. P. Rolim, editors, Handbook on Randomized Computing, pages 401–456. Springer, New York, NY, USA, 2001.
  * [15] B. S. Chlebus, D. R. Kowalski, and M. A. Rokicki.  Adversarial queuing on the multiple access channel.  ACM Transactions on Algorithms, 8:5:1–5:31, 2012.
  * [16] M. Chrobak, L. Gasieniec, and W. Rytter.  Fast broadcasting and gossiping in radio networks.  Journal of Algorithms, 43:177–189, 2002.
  * [17] G. De Marco and D. Kowalski.  Fast nonadaptive deterministic algorithm for conflict resolution in a dynamic multiple-access channel.  SIAM J. Comput, 44(3):868–888, 2015.
  * [18] Robert G. Gallager.  A perspective on multiaccess channels.  IEEE Trans. Information Theory, 31(2):124–142, 1985.
  * [19] Mihály Geréb-Graus and Thanasis Tsantilas.  Efficient optical communication in parallel computers.  In Proceedings of the Fourth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA ’92, page 41–48, New York, NY, USA, 1992\. Association for Computing Machinery.
  * [20] Seth Gilbert, Rachid Guerraoui, and Calvin Newport.  Of malicious motes and suspicious sensors: On the efficiency of malicious interference in wireless networks.  In Mariam Momenzadeh Alexander A. Shvartsman, editor, Principles of Distributed Systems, pages 215–229, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg.
  * [21] Seth Gilbert, Valerie King, Seth Pettie, Ely Porat, Jared Saia, and Maxwell Young.  (near) optimal resource-competitive broadcast with jamming.  In Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’14, page 257–266, New York, NY, USA, 2014\. Association for Computing Machinery.
  * [22] L. A. Goldberg, P. D. MacKenzie, M. Paterson, and A. Srinivasan.  Contention resolution with constant expected delay.  Journal of the ACM, 47(6):1048–1096, 2000.
  * [23] A. G. Greenberg, P. Flajolet, and R. E. Ladner.  Estimating the multiplicities of conflicts to speed their resolution in multiple access channels.  Journal of the ACM, 34(2):289–325, 1987.
  * [24] A. G. Greenberg and R. E. Ladner.  Estimating the multiplicities of conflicts in multiple access.  In IEEE, editor, Proc. of the 24th Annual Symp. on Foundations of Computer Science (FOCS) (Tucson, AZ.)., pages 383–392, Tucson, AZ, USA, 1983\. IEEE.
  * [25] A. G. Greenberg and A S. Winograd.  lower bound on the time needed in the worst case to resolve conflicts deterministically in multiple access channels.  Journal of ACM, 32:589–596, 1985.
  * [26] Ronald I. Greenberg and Charles E. Leiserson.  Randomized routing on fat-trees.  In 26th Annual Symposium on Foundations of Computer Science (sfcs 1985), pages 241–249, Portland, OR, USA, 1985. IEEE.
  * [27] J. F. Hayes.  An adaptive technique for local distribution.  IEEE Transactions on Communications, 26:1178–1186, 1978.
  * [28] Elijah Hradovich, Marek Klonowski, and Dariusz. R. Kowalski.  Contention resolution on a restrained channel.  In 2020 IEEE 26th International Conference on Parallel and Distributed Systems (ICPADS), pages 89–98, Hong Kong, 2020. IEEE.
  * [29] T. Jurdzinski and G. Stachowiak.  Probabilistic algorithms for the wakeup problem in single-hop radio networks.  Theory Comput. Syst, 38(3):347–367, 2005.
  * [30] Marek Klonowski, Dariusz R. Kowalski, Jaroslaw Mirek, and Prudence W. H. Wong.  Fault-tolerant parallel scheduling of arbitrary length jobs on a shared channel.  In Leszek Antoni Gasieniec, Jesper Jansson, and Christos Levcopoulos, editors, Fundamentals of Computation Theory - 22nd International Symposium, FCT 2019, Copenhagen, Denmark, August 12-14, 2019, Proceedings, volume 11651 of Lecture Notes in Computer Science, pages 306–321, Copenhagen, Denmark, 2019. Springer.
  * [31] J. Komlós and A. G. Greenberg.  An asymptotically optimal nonadaptive algorithm for conflict resolution in multiple-access channels.  IEEE Trans. on Information Theory, 31:302–306, 1985.
  * [32] P. Kumar and L. Merakos.  Distributed control of broadcast channels with akcnowledgement feedback: Stability and performance.  In Proceedings, 23rd IEEE Conference on Decision and Control (CDC), pages 1143 – 1148, Las Vegas, NV, USA, 1984. IEEE.