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.
The differences between local and global clocks for the wake-up problem were first studied in @cite_7 and then in @cite_14 @cite_0 @cite_18 . The communication model used in these papers was that of radio networks in which the main challenge is the occurrence of collisions between simultaneously received messages. A global clock is often used in the study of broadcasting in radio networks (cf. @cite_18 ).
@cite_0 @cite_18 @cite_14 @cite_7
2093347633 2116344546 2088895311 1984375161
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. 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. The paper considers broadcasting in radio networks, modeled as unit disk graphs (UDG). Such networks occur in wireless communication between sites (e.g., stations or sensors) situated in a terrain. Network stations are represented by points in the Euclidean plane, where a station is connected to all stations at distance at most 1 from it. A message transmitted by a station reaches all its neighbors, but a station hears a message (receives the message correctly) only if exactly one of its neighbors transmits at a given time step. One station of the network, called the source, has a message which has to be disseminated to all other stations. Stations are unaware of the network topology. Two broadcasting models are considered. In the conditional wake up model, the stations other than the source are initially idle and cannot transmit until they hear a message for the first time. In the spontaneous wake up model, all stations are awake (and may transmit messages) from the beginning. It turns out that broadcasting time depends on two parameters of the UDG network, namely, its diameter D and its granularity g, which is the inverse of the minimum distance between any two stations. We present a deterministic broadcasting algorithm which works in time O (D g) under the conditional wake up model and prove that broadcasting in this model cannot be accomplished by any deterministic algorithm in time better than ( (D g ) ) . For the spontaneous wake up model, we design two deterministic broadcasting algorithms: the first works in time O (D + g 2) and the second in time O (D log g). While neither of these algorithms alone is optimal for all parameter values, we prove that the algorithm obtained by interleaving their steps, and thus working in time ( O ( D + g^2, D g ) ), turns out to be optimal by establishing a matching lower bound. We present an improved algorithm to wake up a multi-hop ad-hoc radio network. The goal is to have all the nodes activated, when some of them may wake up spontaneously at arbitrary times and the remaining nodes need to be awoken by the already active ones. The best previously known wake-up algorithm was given by Chrobak, Gasieniec and Kowalski [11], and operated in time O(n5 3 log n), where n is the number of nodes. We give an algorithm with the running time O(n3 2 log n). This also yields better algorithms for other synchronization-type primitives, like leader election and local-clocks synchronization, each with a time performance that differs from that of wake-up by an extra factor of O(log n) only, and improves the best previously known method for the problem by a factor of n1 6. A wake-up algorithm is a schedule of transmissions for each node. It can be represented as a collection of binary sequences. Useful properties of such collections have been abstracted to define a (radio) synchronizer. It has been known that good radio synchronizers exist and previous algorithms [17,11] relied on this. We show how to construct such synchronizers in polynomial time, from suitable constructible expanders. As an application, we obtain a wake-up protocol for a multiple-access channel that activates the network in time O(k2 polylog n), where k is the number of stations that wake up spontaneously, and which can be found in time polynomial in n. We extend the notion of synchronizers to universal synchronizers. We show that there exist universal synchronizers with parameters that guarantee time O(n3 2 log n) of wake-up.