Consensus is one of the fundamental tasks studied in distributed computing. Processors have input values from some set @math and they have to decide the same value from this set. If all processors have the same input value, then they must all decide this value. We study the task of consensus in a Multiple Access Channel (MAC) prone to faults, under a very weak communication model called the @math . Communication proceeds in synchronous rounds. Some processors wake up spontaneously, in possibly different rounds decided by an adversary. In each round, an awake processor can either listen, i.e., stay silent, or beep, i.e., emit a signal. In each round, a fault can occur in the channel independently with constant probability @math . In a fault-free round, an awake processor hears a beep if it listens in this round and if one or more other processors beep in this round. A processor still dormant in a fault-free round in which some other processor beeps is woken up by this beep and hears it. In a faulty round nothing is heard, regardless of the behaviour of the processors. An algorithm working with error probability at most @math , for a given @math , is called @math - @math . Our main result is the design and analysis, for any constant @math , of a deterministic @math -safe consensus algorithm that works in time @math in a fault-prone MAC, where @math is the smallest input value of all participating processors. We show that this time cannot be improved, even when the MAC is fault-free. The main algorithmic tool that we develop to achieve our goal, and that might be of independent interest, is a deterministic algorithm that, with arbitrarily small constant error probability, establishes a global clock in a fault-prone MAC in constant time.
We present the communication model, which assumes nodes have minimal knowledge about their environment and severely limited communication capabilities. Specifically, nodes have no information regarding the local or global structure of the network, don't have access to synchronized clocks and are woken up by an adversary. Moreover, instead on communicating through messages they rely solely on carrier sensing to exchange information. We study the problem of , a variant of vertex coloring specially suited for the studied beeping model. Given a set of resources, the goal of interval coloring is to assign every node a large contiguous fraction of the resources, such that neighboring nodes share no resources. To highlight the importance of the discreteness of the model, we contrast it against a continuous variant described in [17]. We present an O(1 @math (T ) @math T @math O( n) @math (T ) @math O( n) @math ( n)$ on the time required to solve interval coloring for this model against randomized algorithms. This lower bound implies that our algorithm is asymptotically optimal for constant degree graphs.  Radio networks model wireless communication when processing units communicate using one wave frequency. This is captured by the property that multiple messages arriving simultaneously to a node interfere with one another and none of them can be read reliably. We present improved solutions to the problem of waking up such a network. This requires activating all nodes in a scenario when some nodes start to be active spontaneously, while every sleeping node needs to be awaken by receiving successfully a message from a neighbor. Our contributions concern the existence and efficient construction of universal radio synchronizers, which are combinatorial structures introduced in [6] as building blocks of efficient wake-up algorithms. First we show by counting that there are (n,g)-universal synchronizers for @math . Next we show an explicit construction of (n,g)-universal-synchronizers for @math . By way of applications, we obtain an existential wake-up algorithm which works in time @math and an explicitly instantiated algorithm that works in time @math , where n is the number of nodes and @math is the maximum in-degree in the network. Algorithms for leader-election and synchronization can be developed on top of wake-up ones, as shown in [7], such that they work in time slower by a factor of @math than the underlying wake-up ones. This paper studies the differences between two levels of synchronization in a distributed broadcast system (or a multiple-access channel). In the globally synchronous model, all processors have access to a global clock. In the locally synchronous model, processors have local clocks ticking at the same rate, but each clock starts individually when the processor wakes up. We consider the fundamental problem of waking up all n processors of a completely connected broadcast system. Some processors wake up spontaneously, while others have to be woken up. Only awake processors can send messages; a sleeping processor is woken up upon hearing a message. The processors hear a message in a given round if and only if exactly one processor sends a message in that round. Our goal is to wake up all processors as fast as possible in the worst case, assuming an adversary controls which processors wake up and when. We analyze the problem in both the globally synchronous and locally synchronous models with or without the assumption that n is known to the processors. We propose randomized and deterministic algorithms for the problem, as well as lower bounds in some of the cases. These bounds establish a gap between the globally synchronous and locally synchronous models.