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
2152077793 2166211341 2161281242 2138837863
A number of algorithmic and protocol assumptions taken for granted in the design of existing wireless communication technologies need to be revisited in extending their scope to the new cognitive radio (CR) paradigm. The fact that channel availability can rapidly change over time and the need for coordinated quiet periods in order to quickly and robustly detect the presence of incumbents, are just some of the examples of the unique challenges in protocol and algorithm design for CR networks and, in particular, in the medium access control (MAC) layer. With this in mind, in this paper we introduce a novel cognitive MAC (C-MAC) protocol for distributed multi-channel wireless networks. C-MAC operates over multiple channels, and hence is able to effectively deal with, among other things, the dynamics of resource availability due to primary users and mitigate the effects of distributed quiet periods utilized for primary user signal detection. In C-MAC, each channel is logically divided into recurring superframes which, in turn, include a slotted beaconing period (BP) where nodes exchange information and negotiate channel usage. Each node transmits a beacon in a designated beacon slot during the BP, which helps in dealing with hidden nodes, medium reservations, and mobility. For coordination amongst nodes in different channels, a rendezvous channel (RC) is employed that is decided dynamically and in a totally distributed fashion. Among other things, the RC is used to support network-wide multicast and broadcast which are often neglected in existing multi-channel MAC protocols. We present promising performance results of C- MAC. We also describe our efforts to implement features of C- MAC in a real CR prototype with Atheros chipset, which currently includes the spectrum sensing module and preliminary features of C-MAC. In this paper, we present a reservation-based medium access control (MAC) protocol with multicast support for wavelength-division multiplexing networks. Our system is based on the single-hop, passive optical star architecture. Of the available wavelengths (channels), one channel is designated as a control channel, and the remaining channels are used for data transmission. Each node is equipped with a pair of fixed transceiver to access the control channel, and a fixed transmitter and a tunable receiver to access data channels. For easy implementation of the protocol in hardware and for precisely computing the protocol's processing overhead, we give a register-transfer model of the protocol. We simulate the protocol to study its throughput behavior, and present its analytic model. For a node to be able to send data packets in successive data slots with no time gap between them, in spite of the situation that the protocol's execution time may be longer than data transmission time, we propose the idea of multiple MAC units at each node. Unicast throughput of our protocol reaches the theoretically possible maximum throughput for MAC protocols with distributed control, and the multicast throughput is at least as good as, and even better than, those delivered by existing MAC protocols with distributed control. In much of the theoretical literature on wireless algorithms, issues of message dissemination are considered together with issues of contention management. This combination leads to complicated algorithms and analysis, and makes it difficult to extend the work to harder communication problems. In this paper, we present results of a current project aimed at simplifying such algorithms and analysis by decomposing the treatment into two levels, using abstract "MAC layer" specifications to encapsulate the contention management. We use two different abstract MAC layers: the basic one of [14, 15] and a new probabilistic layer. We first present a typical randomized contention-manageent algorithm for a standard graph-based radio network model We show that it implements both abstract MAC layers. We combine this algorithm with greedy algorithms for single-message and multi-message global broadcast and analyze the combination, using both abstract MAC layers as intermediate layers. Using the basic MAC layer, we prove a bound of O(D log(n ∈) log Δ) for the time to deliver a single message everywhere with probability 1 -- ∈, where D is the network diameter, n is the number of nodes, and Δ is the maximum node degree. Using the probabilistic layer, we prove a bound of O((D + log(n ∈)) log Δ), which matches the best previously-known bound for single-message broadcast over the physical network model. For multi-message broadcast, we obtain bounds of O((D + kΔ) log(n ∈) log Δ) using the basic layer and O((D + kΔ log(n ∈)) log Δ) using the probabilistic layer, for the time to deliver a message everywhere in the presence of at most k concurrent messages. In this paper, different control channel (CC) implementations for multichannel medium access control (MAC) algorithms are compared and analyzed in the context of opportunistic spectrum access (OSA) as a function of spectrum-sensing performance and licensed user activity. The analysis is based on a discrete Markov chain model of a subset of representative multichannel OSA MAC classes that incorporates physical layer effects, such as spectrum sensing and fading. The analysis is complemented with extensive simulations. The major observations are given as follows: 1) When the CC is implemented through a dedicated channel, sharing such dedicated channel with the licensed user does not significantly decrease the throughput achieved by the OSA network when the data packet sizes are sufficiently large or the number of considered data channels is small. 2) Hopping OSA MACs, where the CC is spread over all channels, are less susceptible to licensed user activity than those with a dedicated CC (in terms of both average utilization and on off times). 3) Scanning efficiency has a large impact on the achievable performance of licensed and OSA users for all analyzed protocols. 4) The multiple rendezvous MAC class, which has yet to be proposed in OSA literature, outperforms all the multichannel MAC designs analyzed in this paper.