This paper studies the Contention resolution problem on a shared channel (also known as a multiple access channel). A set of$n$stations are connected to a common device and are able to communicate by transmitting and listening. Each station may have a message to broadcast. At any round, a transmission is successful if and only if exactly one station is transmitting at that round. Simultaneous transmissions interfere one another and, as a result, the respective messages are lost. The Contention resolution is the fundamental problem of scheduling the transmissions into rounds in such a way that any station delivers successfully its message on the channel. We consider a general dynamic distributed setting. We assume that the stations can join (or be activated on) the channel at arbitrary times (dynamic scenario). This has to be contrasted with the simplified static scenario, in which all stations are assumed to be activated simultaneously. We also assume that the stations are not able to detect whether a collision among simultaneous transmissions occurred (model without collision detection). Finally, there is no global clock in the system: each station measures the time using its own local clock which starts when the station is activated and is possibly out of sync with respect to the other stations. We study non-adaptive deterministic distributed algorithms for the contention resolution problem and assess their efficiency both in terms of channel utilization (also called throughput) and energy consumption. While this topic has been quite extensively examined for randomized algorithms, this is, to the best of our knowledge, the first paper to discuss to which extent deterministic contention resolution algorithms can be efficient in terms of both channel utilization and energy consumption. Our results imply an exponential separation gap between static and dynamic setting with respect to channel utilization. We also show that the knowledge of the number of participating stations k (or an upper bound on it) has a substantial impact on the energy consumption.

A shared communication channel (also known as a multiple access channel) is among the most popular and widely studied models of communication and distributed computing. In this model, stations are able to communicate by transmitting and listening to a shared channel. A fundamental problem, called contention resolution, is to allow any station to successfully deliver its message by resolving the conflicts that arise when several stations transmit simultaneously on the channel. Despite a long history, many fundamental questions remain open in the realistic scenario when up to k stations out of n join the channel at different times. In this work we explore the impact of asynchrony, knowledge (or linear estimate) of contenders, and acknowledgments, on latency and channel utilization of non-adaptive deterministic algorithms. We show that if the number of contenders k (or a linear upper bound on it) is known and the stations switch-off after acknowledgment of their successful transmissions, the channel admits efficient solutions. In the same settings, we show that the ignorance of contention k makes the channel nearly quadratically less efficient, even if the stations could switch-off after acknowledgments. We present an algorithm which nearly matches this complexity (for unknown k) which is achieved even if acknowledgments are not provided. We show how the above algorithm could be further improved if stations could switch off upon acknowledgment. Surprisingly, our results imply an exponential impact of knowledge of contention on deterministic utilization of asynchronous channel by deterministic algorithms - it is known that for synchronized channel this feature does not influence asymptotically the channel utilization. The second implication concerns the impact of acknowledgments - they exponentially improve deterministic channel utilization if (some estimate of) k is known, unlike in the case of randomized algorithms where the improvement is only polynomial, while they are not particularly helpful in case of unknown contention. Finally, note that non-adaptive algorithms use fixed transmission schedules, which could be naturally translate into codes in the radio or beeping model - in this context our results indicate under which conditions such codes could be efficient.

A shared channel, also called multiple-access channel, is one of the fundamental communication models. Autonomous entities communicate over a shared medium, and one of the main challenges is how to efficiently resolve collisions occurring when more than one entity attempts to access the channel at the same time. In this work we explore the impact of asynchrony, knowledge (or linear estimate) of the number of contenders, and acknowledgments, on both latency and channel utilization for the Contention resolution problem with non-adaptive deterministic algorithms.

We consider synchronous distributed systems in which processors communicate by shared read- write variables. Processors are anonymous and do not know their number n. The goal is to assign individual names by all the processors to themselves. We develop algorithms that accomplish this for each of the four cases determined by the following independent properties of the model: concurrently attempting to write distinct values into the same shared memory register either is allowed or not, and the number of shared variables either is a constant or it is unbounded. For each such a case, we give a Monte Carlo algorithm that runs in the optimum expected time and uses the expected number of O(n log n) random bits. All our algorithms produce correct output upon termination with probabilities that are 1−n^{−Ω(1)}, which is best possible when terminating almost surely and using O(n log n) random bits.

In this work we address the question whether a simple shared channel could be efficiently utilized, that is, with a constant throughput and linear packet latency. A shared channel (also called a multiple access channel), introduced nearly 50 years ago in the context of the Ethernet [36], is among the most popular and widely studied models of communication and distributed computing. In a nutshell, a number of stations is able to communicate by transmitting and listening to a shared channel, and a message is successfully delivered to all stations if and only if its source station is the only transmitter at a time. Despite of a vast amount of work in the last decades, many fundamental questions remain open, such as: What is the impact of asynchrony on channel utilization? How important is the knowledge/estimate of the number of contenders? Could non-adaptive protocols (i.e., random codes) be asymptotically as efficient as adaptive protocols? In this work we present a broad picture of results answering the above mentioned questions for a 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 contention size k (i.e., random codes with knowledge of k) achieve constant channel throughput and linear message latency even for very weak channels, i.e., with feedback restricted to simple acknowledgments 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 achieving throughput \omega((\log\log k)^2/(\log k)) and/or admitting latency o(k\log k/(\log\log k)^2). This means, in particular, that coding (even random) with acknowledgments is not very efficient on a shared channel without synchronization or estimate of contention size. We also present a non-adaptive algorithm with no knowledge of contention size that almost matches these two complexities. More specifically, it achieves latency O(k\log^2 k) and channel utilization \Omega(1/\log^2 k) even if stations do not switch off after successful transmissions (and thus, could disturb other stations in succeeding), and could be improved by factor \Theta(\log\log k) if stations switch off after acknowledgment. Despite the absense of a collision detection mechanism, our algorithms are also efficient in terms of energy. The maximum number of channel accesses (including transmissions and listenings) for our non-adaptive solutions, with and without knowledge of k, is respectively O(\log k) and O(\log^2 k) whp. Regarding the adaptive algorithm, we argue that a simple modification of our protocol preserves constant throughput and linear latency while achieving O(\log k) maximum number of channel accesses per station whp.

We consider a communication channel in which the only available mode of communication is transmitting beeps. A beep transmitted by a station attached to the channel reaches all the other stations instantaneously. Stations are anonymous, in that they do not have any individual identifiers. The algorithmic goal is to assign names to the stations in such a manner that the names make a contiguous segment of positive integers starting from 1. We develop a Las Vegas naming algorithm, for the case when the number of stations n is known, and a Monte Carlo algorithm, for the case when the number of stations n is not known. The given randomized algorithms are provably optimal with respect to the expected time 𝒪( n log n), the expected number of used random bits 𝒪( n log n), and the probability of error.

We consider single-hop radio networks with multiple channels as a model of wireless networks. There are n stations connected to b radio channels that do not provide collision detection. A station uses all the channels concurrently and independently. Some k stations may become active spontaneously at arbitrary times. The goal is to wake up the network, which occurs when all the stations hear a successful transmission on some channel. Duration of a waking-up execution is measured starting from the first spontaneous activation. We present a deterministic algorithm that wakes up a network in O(klog1/b⁡klog⁡n) time, where k is unknown. We give a deterministic scalable algorithm for the special case when b>dlog⁡log⁡n, for some constant d>1, which wakes up a network in O(kblog⁡nlog⁡(blog⁡n)) time, with k unknown. This algorithm misses time optimality by at most a factor of O(log⁡n(log⁡b+log⁡log⁡n)), because any deterministic algorithm requires Ω(kblog⁡nk) time. We give a randomized algorithm that wakes up a network within O(k1/bln⁡1ϵ) rounds with a probability that is at least 1−ϵ, for any 0<ϵ<1, where k is known. We also consider a model of jamming, in which each channel in any round may be jammed to prevent a successful transmission, which happens with some known parameter probability p, independently across all channels and rounds. For this model, we give two deterministic algorithms for unknown k: one wakes up a network in time O(log−1⁡(1p)klog⁡nlog1/b⁡k), and the other in time O(log−1⁡(1p)kblog⁡nlog⁡(blog⁡n)) when the inequality b>log⁡(128blog⁡n) holds, both with probabilities that are at least 1−1/poly(n).

A classical problem in addressing a decentralized multiple-access channel is resolving conflicts when a set of stations attempt to transmit at the same time on a shared communication channel. In a static scenario, i.e., when all stations are activated simultaneously, Komlós and Greenberg [IEEE Trans. Inform. Theory, 31 (1985), pp. 302--306] in their seminal work showed that it is possible to resolve the conflict among $k$ stations from an ensemble of $n$, with a nonadaptive deterministic algorithm in time $O(k + k \log(n/k))$ in the worst case. In this paper we show that in a dynamic scenario, when the stations can join the channel at arbitrary rounds, there is a nonadaptive deterministic algorithm guaranteeing a successful transmission for each station in only a slightly bigger time: $O(k\log n\log\log n)$ in the worst case. This almost matches the $\Omega(k\log n/\log k)$ lower bound by Greenberg and Winograd [J. ACM, 32 (1985), pp. 589--596] that holds even in much stronger settings: for adaptive algorithms, in the static scenario, and with additional channel feedback--collision detection. In terms of channel utilization, our result implies throughput, understood as the average number of successful transmissions per time unit, $\Omega(1/(\log n\log\log n))$ on the dynamic deterministic channel.

Multiple access channel is a well-known communication model that deploys properties of many network systems, such as Aloha multi-access systems, local area Ethernet networks, satellite communication systems, packet radio networks. The fundamental aspect of this model is to provide efficient communication and computation in the presence of restricted access to the communication resource: at most one station can successfully transmit at a time, and a wasted round occurs when more than one station attempts to transmit at the same time. In this work we consider the problem of contention resolution in a multiple access channel in a realistic scenario when up to k stations out of n join the channel at different times. The goal is to let at least one station to transmit alone, which results in successful delivery of the message through the channel. We present three deterministic algorithms: two of them working under some constrained scenarios, and achieving asymptotically optimal time complexity Θ(k log(n/k)), while the third general algorithm accomplishes the goal in time O(k logn log log n).

We are given $n$ stations of which $k$ are active, while the remaining $n-k$ are asleep. The active stations communicate via a multiple-access channel. If a subset $Q$ of active stations transmits in the same round, all active stations can recognize from the signal strength how many stations have transmitted (i.e., they learn the size of set $Q$), even though they may not be able to decode the contents of transmitted messages. The goal is to let each active station to learn about the set of all active stations. It is well known that $\Theta(k\log_{k+1} n)$ rounds are enough, even for non-adaptive deterministic algorithms. A natural interesting generalization arises when we are required to identify a subset of $m\leq k$ active stations. We show that while for randomized or for adaptive deterministic algorithms $O(m \log_{m+1} n)$ rounds are sufficient, the non-adaptive deterministic counterpart still requires $\Theta(k\log_{k+1} n)$ rounds, therefore, finding any subset of active stations is not easier than finding all of them by a non-adaptive deterministic algorithm. We prove our results in the more general framework of combinatorial search theory, where the problem of identifying active stations on a multiple-access channel can be viewed as a variant of the well-known counterfeit coin problem.

We consider the problem of broadcasting in an unknown radio network modeled as a directed graph $G=(V,E)$, where $|V|=n$. In unknown networks, every node knows only its own label, while it is unaware of any other parameter of the network, including its neighborhood and even any upper bound on the number of nodes. We show an $\mathcal{O}(n\log n\log\log n)$ upper bound on the time complexity of deterministic broadcasting. This is an improvement over the currently best upper bound $\mathcal{O}(n\log^2n)$ for arbitrary networks, thus shrinking exponentially the existing gap between the lower bound $\Omega(n\log n)$ and the upper bound from $\mathcal{O}(\log n)$ to $\mathcal{O}(\log\log n)$.

We study a version of the beta-assignment problem (Chang and Lee, 1988) on asynchronous rings: consider a set of items and a set of m colors, where each item is associated to one color. Consider also n computational agents connected by an asynchronous ring. Each agent holds a subset of the items, where initially different agents might hold items associated to the same color. We analyze the problem of distributively assigning colors to agents in such a way that (a) each color is assigned to one agent and (b) the number of different colors assigned to each agent is minimum. Since any color assignment requires that the items be distributed according to it (e.g. all items of the same color are to be held by only one agent), we define the cost of a color assignment as the amount of items that need to be moved, given an initial allocation. We first show that any distributed algorithm for this problem on the ring requires a communication complexity of Omega(n middot m) and then we exhibit a polynomial time distributed algorithm with message complexity matching the bound, that determines a color assignment with cost at most (2 + epsi) times the optimal cost, for any 0 < epsi < 1

Every node of an undirected connected graph is colored white or black. Adjacent nodes can be compared and the outcome of each comparison is either 0 (same color) or 1 (different colors). The aim is to discover a node of the majority color, or to conclude that there is the same number of black and white nodes. We consider randomized algorithms for this task and establish upper and lower bounds on their expected running time. Our main contribution are lower bounds showing that some simple and natural algorithms for this problem cannot be improved in general. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

We consider the time of deterministic broadcasting in networks whose nodes have limited knowledge of network topology. Each node v knows only the part of the network within knowledge radius r from it, i.e., it knows the graph induced by all nodes at distance at most r from v . Apart from that, each node knows only the maximum degree Δ of the network and the number n of nodes. One node of the network, called the source , has a message which has to reach all other nodes. We adopt the widely studied communication model called the one-way model in which, in every round, each node can communicate with at most one neighbor, and in each pair of nodes communicating in a given round, one can only send a message while the other can only receive it. This is the weakest of all store-and-forward models for point-to-point networks, and hence our algorithms work for other models as well in at most the same time. We show tradeoffs between knowledge radius and time of deterministic broadcasting, when knowledge radius is small, i.e., when nodes are only aware of their close vicinity. While for knowledge radius 0, minimum broadcasting time is θ(e), where e is the number of edges in the network, broadcasting can be usually completed faster for positive knowledge radius. Our main results concern knowledge radii 1 and 2. We develop fast broadcasting algorithms and analyze their execution time. We also prove lower bounds on broadcasting time, showing that our algorithms are close to optimal, for a given knowledge radius. For knowledge radius 1 we develop a broadcasting algorithm working in time O (min( n , D 2 Δ)), where n is the number of nodes, D is the diameter of the network, and Δ is the maximum degree. We show that for bounded maximum degree Δ this algorithm is asymptotically optimal. For knowledge radius 2 we show how to broadcast in time O ( D Δ log n )) and prove a lower bound Ω( D Δ) on broadcasting time, when D Δ ∈ O ( n ). This lower bound is valid for any constant knowledge radius. For knowledge radius log * n+3 we show how to broadcast in time O ( D Δ). Finally, for any knowledge radius r , we show a broadcasting algorithm working in time O ( D 2 Δ/ r ). These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.