More Like this

1. The Power of Abstract MAC Layer: A Fault-Tolerance Perspective

   https://doi.org/10.4230/LIPICS.DISC.2024.39  

   Zhang, Qinzi; Tseng, Lewis (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Alistarh, Dan (Ed.)

   This paper studies the power of the "abstract MAC layer" model in a single-hop asynchronous network. The model captures primitive properties of modern wireless MAC protocols. In this model, Newport [PODC '14] proves that it is impossible to achieve deterministic consensus when nodes may crash. Subsequently, Newport and Robinson [DISC '18] present randomized consensus algorithms that terminate with O(n³ log n) expected broadcasts in a system of n nodes. We are not aware of any results on other fault-tolerant distributed tasks in this model. We first study the computability aspect of the abstract MAC layer. We present a wait-free algorithm that implements an atomic register. Furthermore, we show that in general, k-set consensus is impossible. Second, we aim to minimize storage complexity. Existing algorithms require Ω(n log n) bits. We propose two wait-free approximate consensus and two wait-free randomized binary consensus algorithms that only need constant storage complexity (except for the phase index). One randomized algorithm terminates with O(n log n) expected broadcasts. All our algorithms are anonymous, meaning that at the algorithm level, nodes do not need to have a unique identifier. 

   more » « less
2. Fault-Tolerant Consensus with an Abstract MAC Layer

   Newport, Calvin; Robinson, Peter (October 2018, Proceedings of the International Symposium on Distributed Computing (DISC))

   In this paper, we study fault-tolerant distributed consensus in wireless systems. In more detail, we produce two new randomized algorithms that solve this problem in the abstract MAC layer model, which captures the basic interface and communication guarantees provided by most wireless MAC layers. Our algorithms work for any number of failures, require no advance knowledge of the network participants or network size, and guarantee termination with high probability after a number of broadcasts that are polynomial in the network size. Our first algorithm satisfies the standard agreement property, while our second trades a faster termination guarantee in exchange for a looser agreement property in which most nodes agree on the same value. These are the first known fault-tolerant consensus algorithms for this model. In addition to our main upper bound results, we explore the gap between the abstract MAC layer and the standard asynchronous message passing model by proving fault-tolerant consensus is impossible in the latter in the absence of information regarding the network participants, even if we assume no faults, allow randomized solutions, and provide the algorithm a constant-factor approximation of the network size. 

   more » « less
3. Byzantine Consensus in Abstract MAC Layer

   https://doi.org/10.4230/LIPICS.OPODIS.2023.9  

   Tseng, Lewis; Sardina, Callie (January 2024, International Conference on Principles of Distributed Systems)

   Bessani, Alysson; Défago, Xavier; Nakamura, Junya; Wada, Koichi; Yamauchi, Yukiko (Ed.)

   This paper studies the design of Byzantine consensus algorithms in an asynchronous single-hop network equipped with the "abstract MAC layer" [DISC09], which captures core properties of modern wireless MAC protocols. Newport [PODC14], Newport and Robinson [DISC18], and Tseng and Zhang [PODC22] study crash-tolerant consensus in the model. In our setting, a Byzantine faulty node may behave arbitrarily, but it cannot break the guarantees provided by the underlying abstract MAC layer. To our knowledge, we are the first to study Byzantine faults in this model. We harness the power of the abstract MAC layer to develop a Byzantine approximate consensus algorithm and a Byzantine randomized binary consensus algorithm. Both of our algorithms require only the knowledge of the upper bound on the number of faulty nodes f, and do not require the knowledge of the number of nodes n. This demonstrates the "power" of the abstract MAC layer, as consensus algorithms in traditional message-passing models require the knowledge of both n and f. Additionally, we show that it is necessary to know f in order to reach consensus. Hence, from this perspective, our algorithms require the minimal knowledge. The lack of knowledge of n brings the challenge of identifying a quorum explicitly, which is a common technique in traditional message-passing algorithms. A key technical novelty of our algorithms is to identify "implicit quorums" which have the necessary information for reaching consensus. The quorums are implicit because nodes do not know the identity of the quorums - such notion is only used in the analysis. 

   more » « less
4. Fairness and Delay in Heterogeneous Half- and Full-Duplex Wireless Networks

   https://doi.org/10.1109/ACSSC.2018.8645117  

   Chen, Tingjun; Diakonikolas, Jelena; Ghaderi, Javad; Zussman, Gil (October 2018, Conference record - Asilomar Conference on Signals, Systems, & Computers)

   Full-duplex (FD) wireless is an attractive communication paradigm with high potential for improving network capacity and reducing delay in wireless networks. Despite significant progress on the physical layer development, the challenges associated with developing medium access control (MAC) protocols for heterogeneous networks composed of both legacy half-duplex (HD) and emerging FD devices have not been fully addressed. In [1], we focused on the design and performance evaluation of scheduling algorithms for heterogeneous HD-FD networks and presented the distributed Hybrid-Greedy Maximal Scheduling (H-GMS) algorithm. H-GMS combines the centralized Greedy Maximal Scheduling (GMS) and a distributed queue-based random-access mechanism, and is throughput-optimal. In this paper, we analyze the delay performance of H-GMS by deriving two lower bounds on the average queue length. We also evaluate the fairness and delay performance of H-GMS via extensive simulations. We show that in heterogeneous HD-FD networks, H-GMS achieves$$16-30\times$$ better delay performance and improves fairness between FD and HD users by up to 50% compared with the fully decentralized Q-CSMA algorithm. 

   more » « less
5. Fairness and Delay in Heterogeneous Half- and Full-Duplex Wireless Networks

   Tingjun Chen, Jelena Diakonikolasy (January 2018, Asilomar Conference on Signals, Systems, and Computers)

   Abstract—Full-duplex (FD) wireless is an attractive commu- nication paradigm with high potential for improving network capacity and reducing delay in wireless networks. Despite sig- nificant progress on the physical layer development, the chal- lenges associated with developing medium access control (MAC) protocols for heterogeneous networks composed of both legacy half-duplex (HD) and emerging FD devices have not been fully addressed. In [1], we focused on the design and performance evaluation of scheduling algorithms for heterogeneous HD-FD networks and presented the distributed Hybrid-Greedy Maximal Scheduling (H-GMS) algorithm. H-GMS combines the central- ized Greedy Maximal Scheduling (GMS) and a distributed queue- based random-access mechanism, and is throughput-optimal. In this paper, we analyze the delay performance of H-GMS by deriving two lower bounds on the average queue length. We also evaluate the fairness and delay performance of H-GMS via extensive simulations. We show that in heterogeneous HD-FD networks, H-GMS achieves 16–30× better delay performance and improves fairness between FD and HD users by up to 50% compared with the fully decentralized Q-CSMA algorithm. 

   more » « less