Document Open Access Logo

Fault-Tolerant Consensus with an Abstract MAC Layer

Authors Calvin Newport, Peter Robinson

PDF
Thumbnail PDF

File

LIPIcs.DISC.2018.38.pdf
  • Filesize: 494 kB
  • 20 pages

Document Identifiers

Author Details

Calvin Newport
  • Georgetown University, Washington, D.C., USA
Peter Robinson
  • McMaster University, Hamilton, Canada

Funding

  • Newport, Calvin: Calvin Newport acknowledges the support of the National Science Foundation, award number 1733842.
  • Robinson, Peter: Peter Robinson acknowledges the support of the Natural Sciences and Engineering Research Council of Canada (NSERC), RGPIN-2018-06322.

Cite As Get BibTex

Calvin Newport and Peter Robinson. Fault-Tolerant Consensus with an Abstract MAC Layer. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 38:1-38:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.DISC.2018.38

Abstract

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • abstract MAC layer
  • wireless networks
  • consensus
  • fault tolerance

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Mohssen Abboud, Carole Delporte-Gallet, and Hugues Fauconnier. Agreement without knowing everybody: a first step to dynamicity. In Proceedings of the International Conference on New Technologies in Distributed Systems, 2008. Google Scholar
  2. Marcos Kawazoe Aguilera, Wei Chen, and Sam Toueg. Failure detection and consensus in the crash-recovery model. Distributed computing, 13(2):99-125, 2000. Google Scholar
  3. Eduardo AP Alchieri, Alysson Neves Bessani, Joni da Silva Fraga, and Fabíola Greve. Byzantine consensus with unknown participants. In Proceedings of the International Conference on the Principles of Distributed Systems. Springer, 2008. Google Scholar
  4. Khaled Alekeish and Paul Ezhilchelvan. Consensus in sparse, mobile ad hoc networks. IEEE Transactions on Parallel and Distributed Systems, 23(3):467-474, 2012. Google Scholar
  5. James Aspnes. Fast deterministic consensus in a noisy environment. Journal of Algorithms, 45(1):16-39, 2002. Google Scholar
  6. Hagit Attiya, Alla Gorbach, and Shlomo Moran. Computing in totally anonymous asynchronous shared memory systems. Information and Computation, 173(2):162-183, 2002. Google Scholar
  7. John Augustine, Gopal Pandurangan, Peter Robinson, and Eli Upfal. Distributed agreement in dynamic peer-to-peer networks. J. Comput. Syst. Sci., 81(7):1088-1109, 2015. URL: http://dx.doi.org/10.1016/j.jcss.2014.10.005.
  8. R. Bar-Yehuda, O. Goldreich, and A. Itai. On the Time Complexity of Broadcast in Radio Networks: an Exponential Gap Between Determinism and Randomization. In Proceedings of the ACM Conference on Distributed Computing, 1987. Google Scholar
  9. Michael Ben-Or. Another advantage of free choice (extended abstract): Completely asynchronous agreement protocols. In Proceedings of the ACM Conference on Distributed Computing, pages 27-30. ACM, 1983. Google Scholar
  10. François Bonnet and Michel Raynal. Anonymous Asynchronous Systems: the Case of Failure Detectors. In Proceedings of the International Conference on Distributed Computing, 2010. Google Scholar
  11. David Cavin, Yoav Sasson, and André Schiper. Consensus with unknown participants or fundamental self-organization. In ADHOC-NOW, 2004. Google Scholar
  12. Tushar Deepak Chandra. Polylog randomized wait-free consensus. In Proceedings of the ACM Conference on Distributed Computing, 1996. Google Scholar
  13. Tushar Deepak Chandra and Sam Toueg. Unreliable failure detectors for reliable distributed systems. Journal of the ACM, 43(2):225-267, 1996. Google Scholar
  14. Alejandro Cornejo, Nancy Lynch, Saira Viqar, and Jennifer L Welch. Neighbor Discovery in Mobile Ad Hoc Networks Using an Abstract MAC Layer. In Proceedings of the Annual Allerton Conference on Communication, Control, and Computing, 2009. Google Scholar
  15. Alejandro Cornejo, Saira Viqar, and Jennifer L Welch. Reliable Neighbor Discovery for Mobile Ad Hoc Networks. Ad Hoc Networks, 12:259-277, 2014. Google Scholar
  16. A. Czumaj and W. Rytter. Broadcasting Algorithms in Radio Networks with Unknown Topology. Journal of Algorithms, 60:115-143, 2006. Google Scholar
  17. Sebastian Daum, Seth Gilbert, Fabian Kuhn, and Calvin Newport. Broadcast in the Ad Hoc SINR Model. In Proceedings of the International Conference on Distributed Computing, 2013. Google Scholar
  18. Cynthia Dwork, David Peleg, Nicholas Pippenger, and Eli Upfal. Fault tolerance in networks of bounded degree. SIAM Journal on Computing, 17(5):975-988, 1988. Google Scholar
  19. Michael J Fischer, Nancy A Lynch, and Michael S Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2), 1985. Google Scholar
  20. L. Gasieniec, D. Peleg, and Q. Xin. Faster Communication in Known Topology Radio Networks. Distributed Computing, 19(4):289-300, 2007. Google Scholar
  21. O. Goussevskaia, R. Wattenhofer, M.M. Halldorsson, and E. Welzl. Capacity of Arbitrary Wireless Networks. In Proceedings of the IEEE International Conference on Computer Communications, 2009. Google Scholar
  22. Fabiola Greve and Sebastien Tixeuil. Knowledge connectivity vs. synchrony requirements for fault-tolerant agreement in unknown networks. In Proceedings of the IEEE/IFIP International Conference on Dependable Systems and Networks, 2007. Google Scholar
  23. Rachid Guerraoui, Michel Hurfinn, Achour Mostéfaoui, Riucarlos Oliveira, Michel Raynal, and André Schiper. Consensus in asynchronous distributed systems: A concise guided tour. Advances in Distributed Systems, Lecture Notes in Computer Science, 1752:33-47, 2000. Google Scholar
  24. Rachid Guerraoui and Andre Schiper. Consensus: the big misunderstanding [distributed fault tolerant systems]. In Proceedings of the IEEE Computer Society Workshop on Future Trends of Distributed Computing Systems, 1997. Google Scholar
  25. Rachid Guerraoui and André Schiper. The generic consensus service. IEEE Transactions on Software Engineering, 27(1):29-41, 2001. Google Scholar
  26. Magnus M. Halldorsson and Pradipta Mitra. Wireless Connectivity and Capacity. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 2012. Google Scholar
  27. Tomasz Jurdzinski, Dariusz R. Kowalski, Michal Rozanski, and Grzegorz Stachowiak. Distributed Randomized Broadcasting in Wireless Networks under the SINR Model. In Proceedings of the International Conference on Distributed Computing, 2013. Google Scholar
  28. Tomasz Jurdziński and Grzegorz Stachowiak. Probabilistic Algorithms for the Wakeup Problem in Single-Hop Radio Networks. In Algorithms and Computation, pages 535-549. Springer, 2002. Google Scholar
  29. Majid Khabbazian, Fabian Kuhn, Dariusz Kowalski, and Nancy Lynch. Decomposing Broadcast Algorithms Using Abstract MAC Layers. In Proceedings of the International Workshop on the Foundations of Mobile Computing, 2010. Google Scholar
  30. Majid Khabbazian, Fabian Kuhn, Nancy Lynch, Muriel Medard, and Ali ParandehGheibi. MAC Design for Analog Network Coding. In Proceedings of the International Workshop on the Foundations of Mobile Computing, 2011. Google Scholar
  31. Valerie King, Jared Saia, Vishal Sanwalani, and Erik Vee. Towards secure and scalable computation in peer-to-peer networks. In Foundations of Computer Science, 2006. FOCS'06. 47th Annual IEEE Symposium on, pages 87-98. IEEE, 2006. Google Scholar
  32. D.R. Kowalski and A. Pelc. Broadcasting in Undirected Ad Hoc Radio Networks. Distributed Computing, 18(1):43-57, 2005. Google Scholar
  33. Fabian Kuhn, Nancy Lynch, and Calvin Newport. The Abstract MAC Layer. In Proceedings of the International Conference on Distributed Computing, 2009. Google Scholar
  34. Fabian Kuhn, Nancy Lynch, and Calvin Newport. The Abstract MAC Layer. Distributed Computing, 24(3-4):187-206, 2011. Google Scholar
  35. Leslie Lamport. The part-time parliament. ACM Transactions on Computer Systems, 16(2):133-169, 1998. Google Scholar
  36. Nancy A Lynch. Distributed algorithms. Morgan Kaufmann, 1996. Google Scholar
  37. Thomas Moscibroda. The Worst-Case Capacity of Wireless Sensor Networks. In Proceedings of the ACM/IEEE International Conference on Information Processing in Sensor Networks, 2007. Google Scholar
  38. Thomas Moscibroda and Roger Wattenhofer. Maximal Independent Sets in Radio Networks. In Proceedings of the ACM Conference on Distributed Computing, 2005. Google Scholar
  39. Thomas Moscibroda and Roger Wattenhofer. The Complexity of Connectivity in Wireless Networks. In Proceedings of the IEEE International Conference on Computer Communications, 2006. Google Scholar
  40. Achour Mostefaoui and Michel Raynal. Solving consensus using Chandra-Touegs unreliable failure detectors. Lecture Notes in Computer Science, 1693:49-63, 1999. Google Scholar
  41. Calvin Newport. Consensus with an Abstract MAC Layer. In Proceedings of the ACM Conference on Distributed Computing, 2014. Google Scholar
  42. Calvin Newport and Peter Robinson. Fault-Tolerant Consensus with an Abstract MAC Layer. Technical report, https://www.cas.mcmaster.ca/robinson/random-aml.pdf, 2018.
  43. Eric Ruppert. The Anonymous Consensus Hierarchy and Naming Problems. In Proceedings of the International Conference on Principles of Distributed Systems, 2007. Google Scholar
  44. Andre Schiper. Early consensus in an asynchronous system with a weak failure detector. Distributed Computing, 10(3):149-157, 1997. Google Scholar
  45. Einar W Vollset and Paul D Ezhilchelvan. Design and performance-study of crash-tolerant protocols for broadcasting and reaching consensus in MANETs. In IEEE Symposium on Reliable Distributed Systems, 2005. Google Scholar
  46. Weigang Wu, Jiannong Cao, and Michel Raynal. Eventual clusterer: A modular approach to designing hierarchical consensus protocols in manets. IEEE Transactions onParallel and Distributed Systems, 20(6):753-765, 2009. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact