skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Byzantine Consensus in Abstract MAC Layer
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
Award ID(s):
2334021
PAR ID:
10508476
Author(s) / Creator(s):
;
Editor(s):
Bessani, Alysson; Défago, Xavier; Nakamura, Junya; Wada, Koichi; Yamauchi, Yukiko
Publisher / Repository:
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Date Published:
Journal Name:
International Conference on Principles of Distributed Systems
Subject(s) / Keyword(s):
Byzantine Randomized Consensus Approximate Consensus Abstract MAC Theory of computation → Distributed algorithms
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; (, 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. ; (, 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. ; ; (, International Conference on Principles of Distributed Systems)
    We consider Byzantine consensus in a synchronous system where nodes are connected by a network modeled as a directed graph, i.e., communication links between neighboring nodes are not necessarily bi-directional. The directed graph model is motivated by wireless networks wherein asymmetric communication links can occur. In the classical point-to-point communication model, a message sent on a communication link is private between the two nodes on the link. This allows a Byzantine faulty node to equivocate, i.e., send inconsistent information to its neighbors. This paper considers the local broadcast model of communication, wherein transmission by a node is received identically by all of its outgoing neighbors, effectively depriving the faulty nodes of the ability to equivocate. Prior work has obtained sufficient and necessary conditions on undirected graphs to be able to achieve Byzantine consensus under the local broadcast model. In this paper, we obtain tight conditions on directed graphs to be able to achieve Byzantine consensus with binary inputs under the local broadcast model. The results obtained in the paper provide insights into the trade-off between directionality of communication links and the ability to achieve consensus. 
    more » « less
  4. ; ; (, ACM Symposium on Principles in Distributed Computing)
    This paper considers the Byzantine consensus problem for nodes with binary inputs. The nodes are interconnected by a network represented as an undirected graph, and the system is assumed to be synchronous. Under the classical point-to-point communication model, it is well-known that the following two conditions are both necessary and sufficient to achieve Byzantine consensus among n nodes in the presence of up to ƒ Byzantine faulty nodes: n & 3 #8805; 3 ≥ ƒ+ 1 and vertex connectivity at least 2 ƒ + 1. In the classical point-to-point communication model, it is possible for a faulty node to equivocate, i.e., transmit conflicting information to different neighbors. Such equivocation is possible because messages sent by a node to one of its neighbors are not overheard by other neighbors. This paper considers the local broadcast model. In contrast to the point-to-point communication model, in the local broadcast model, messages sent by a node are received identically by all of its neighbors. Thus, under the local broadcast model, attempts by a node to send conflicting information can be detected by its neighbors. Under this model, we show that the following two conditions are both necessary and sufficient for Byzantine consensus: vertex connectivity at least ⌋ 3 fƒ / 2 ⌊ + 1 and minimum node degree at least 2 ƒ. Observe that the local broadcast model results in a lower requirement for connectivity and the number of nodes n, as compared to the point-to-point communication model. We extend the above results to a hybrid model that allows some of the Byzantine faulty nodes to equivocate. The hybrid model bridges the gap between the point-to-point and local broadcast models, and helps to precisely characterize the trade-off between equivocation and network requirements. 
    more » « less
  5. ; ; ; ; ; (, SoCC '19: Proceedings of the ACM Symposium on Cloud Computing)
    null (Ed.)
    Byzantine Fault Tolerant (BFT) protocols are designed to ensure correctness and eventual progress in the face of misbehaving nodes [1]. However, this does not prevent negative effects an adversary may have on performance: a faulty node may significantly affect the latency and throughput of the system without being detected. This is especially true in speculative protocols optimized for the best-case where a single leader can force the protocol into the worst case [3]. Systems like Aardvark [2] that are designed to maximize worst-case performance tolerate byzantine behavior without necessarily detecting who the perpetrator is. By forcing regular view changes, for example, they mitigate the effects of leaders who deliberately delay dissemination of messages, even if this behavior would be difficult to prove to a third party. Byzantine faults, by definition, can be difficult to detect. An error of 'commission', such as a message with a mismatching digest, can be proven. Errors of 'omission', such as delaying or failing to relay a message, as a rule cannot be proven, and the node responsible for these types of omission faults may not appear faulty to all observers. Nevertheless, we observe that they can reliably be detected. Designing protocols that detect and eject nodes is challenging for two reasons. First, some behaviors are observed by a subset of honest nodes and cannot be objectively proven to a third party. Second, any mechanism capable of ejecting nodes could be subverted by Byzantine nodes to eject honest nodes. This paper presents the Protocol for Ejecting All Corrupted Hosts (Peach, a mechanism for detecting and ejecting faulty nodes in Byzantine fault tolerant (BFT) protocols. Nodes submit votes to a trusted configuration manager that replaces faulty nodes once a threshold of votes are received. We implement Peach for two BFT protocol variants, a traditional pbft-style three-phase protocol and a speculative protocol, and evaluate its ability to respond to Byzantine behavior. This work makes the following contributions: (1) We present and prove a necessary and sufficient constraint on cluster membership guaranteeing that any nodes causing performance degradation via acts of omission will be detected. (2) We present an agreement protocol, PEACHes, in which replicas pass votes about their subjective local observations of possible omissions to a TTP. (3) We show how the separation of detection and effectuation allows fine-grained detection of malicious behavior that is compatible and easily integrated with existing systems. (4) We present DecentBFT, an extension of BFT-Smart to which we added a speculative fast path (similar to Zyzzva) and integrated PEACHes. (5) We show DecentBFT rapidly detects and mitigates a variety of performance attacks that would have gone undetected by the state of the art. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email