TY - GEN
T1 - Fault-tolerant consensus with an abstract MAC layer
AU - Newport, Calvin
AU - Robinson, Peter
N1 - Funding Information:
Calvin Newport acknowledges the support of the National Science Foundation, award number 1733842. 2 Peter Robinson acknowledges the support of the Natural Sciences and Engineering Research Council of Canada (NSERC), RGPIN-2018-06322.
Funding Information:
1 Calvin Newport acknowledges the support of the National Science Foundation, award number 1733842. 2 Peter Robinson acknowledges the support of the Natural Sciences and Engineering Research Council of Canada (NSERC), RGPIN-2018-06322.
Publisher Copyright:
© Calvin Newport and Peter Robinson.
PY - 2018/10/1
Y1 - 2018/10/1
N2 - 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.
AB - 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.
KW - Abstract MAC layer
KW - Consensus
KW - Fault tolerance
KW - Wireless networks
UR - http://www.scopus.com/inward/record.url?scp=85059618113&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85059618113&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.DISC.2018.38
DO - 10.4230/LIPIcs.DISC.2018.38
M3 - Conference contribution
AN - SCOPUS:85059618113
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 32nd International Symposium on Distributed Computing, DISC 2018
A2 - Schmid, Ulrich
A2 - Widder, Josef
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 32nd International Symposium on Distributed Computing, DISC 2018
Y2 - 15 October 2018 through 19 October 2018
ER -