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 Multiple Access Channel (MAC) is a popular and well-studied medium of communication. Most research concerning the MAC has been done under the radio communication model in which processors can send an entire message in a single round, and this message is heard by other processors if exactly one processor transmits, and all others listen in this round. This communication model is incomparable to the beeping model: on the one hand it is much stronger, as large messages (and not only beeps) can be sent in a single round, but on the other hand it is weaker, as it requires a unique transmitter in a round to make the transmission successful, while in the beeping model many beeps may be heard simultaneously. Leader election was studied in a MAC under the radio model, both in the deterministic @cite_3 @cite_12 and in the randomized setting @cite_16 @cite_6 .
@cite_16 @cite_12 @cite_3 @cite_6
2080763277 2036925455 1965299092 2033487809
A problem related to the decentralized control of a multiple access channel is considered: Suppose k stations from an ensemble of n simultaneously transmit to a multiple access channel that provides the feedback 0, 1, or 2+, denoting k = 0, k = 1, or k ≥ 2, respectively. If k = 1, then the transmission succeeds. But if k ≥ 2, as a result of the conflict, none of the transmissions succeed. An algorithm to resolve a conflict determines how to schedule retransmissions so that each of the conflicting stations eventually transmits singly to the channel. In this paper, a general model of deterministic algorithms to resolve conflicts is introduced, and it is established that, for all k and n (2 ≤ k ≤ n ), O( k (log n ) (log k )) time must elapse in the worst case before all k transmissions succeed. Selective families, a weaker variant of superimposed codes [KS64, F92, 197, CR96], have been recently used to design Deterministic Distributed Broadcast (DDB) protocols for unknown radio networks (a radio network is said to be unknown when the nodes know nothing about the network but their own label) [CGGPR00, CGOR00]. We first provide a general almost tight lower bound on the size of selective families. Then, by reverting the selective families - DDB protocols connection, we exploit our lower bound to construct a family of “hard” radio networks (i.e. directed graphs). These networks yield an O(n log D) lower bound on the completion time of DDB protocols that is superlinear (in the size n of the network) even for very small maximum eccentricity D of the network, while all the previous lower bounds (e.g. O(D log n) [CGGPR00]) are superlinear only when D is almost linear. On the other hand, the previous upper bounds are all superlinear in n independently of the eccentricity D and the maximum in-degree d of the network. We introduce a broadcast technique that exploits selective families in a new way. Then, by combining selective families of almost optimal size with our new broadcast technique, we obtain an O(Dd log3 n) upper bound that we prove to be almost optimal when d = O(n D). This exponentially improves over the best known upper bound [CGR00) when D, d = O(polylogn). Furthermore, by comparing our deterministic upper bound with the best known randomized one [BGI87] we obtain a new, rather surprising insight into the real gap between deterministic and randomized protocols. It turns out that this gap is exponential (as discovered in [BGI87]), but only when the network has large maximum in-degree (i.e. d = O(na), for some constant a > O). We then look at the multibroadcast problem on unknown radio networks. A similar connection to that between selective families and (single) broadcast also holds between superimposed codes and multibroadcast. We in fact combine a variant of our (single) broadcast technique with superimposed codes of almost optimal size available in literature [EFF85, HS87, I97, CHI99]. This yields a multibroadcast protocol having completion time O(Dd2 log3 n). Finally, in order to determine the limits of our multibroadcast technique, we generalize (and improve) the best known lower bound [CR96] on the size of superimposed codes. We propose two selection protols that run on multiple access channels in log-logarithmic expected time, and establish a complementary lower bound showing that the first protocols falls within an additive constant of optimality and that the second differs from optimality by less than any multiplicative factor infinitesimally greater than 1 as the size of the problem approaches infinity. It is difficult to second-guess the fast-changing electronics industry, but our mathematical analysis could be relevant outside the traditional interests of communications protocols to semaphore-like problems.