Brief Announcement: Simple Majority Consensus in Networks with Unreliable Communication

Authors Ariel Livshits , Yonatan Shadmi , Ran Tamir (Averbuch)



PDF
Thumbnail PDF

File

LIPIcs.DISC.2021.59.pdf
  • Filesize: 0.5 MB
  • 4 pages

Document Identifiers

Author Details

Ariel Livshits
  • Technion - Israel Institute of Technology, Haifa, Israel
Yonatan Shadmi
  • Technion - Israel Institute of Technology, Haifa, Israel
Ran Tamir (Averbuch)
  • Technion - Israel Institute of Technology, Haifa, Israel

Acknowledgements

The authors thank Yoram Moses for his invaluable comments and suggestions.

Cite AsGet BibTex

Ariel Livshits, Yonatan Shadmi, and Ran Tamir (Averbuch). Brief Announcement: Simple Majority Consensus in Networks with Unreliable Communication. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 59:1-59:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.DISC.2021.59

Abstract

In this work, we consider a synchronous model of n faultless agents, with a complete communication graph and messages that are lost with some constant probability q ∈ (0,1). In this model we show that there exists a protocol, called the Simple Majority Protocol, that solves consensus in 3 communication rounds with probability of agreement converging to 1 as n → ∞. We also prove that 3 communication rounds are necessary for the SMP to achieve consensus, with high probability.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • Majority consensus
  • probabilistic message loss
  • distributed systems

Metrics

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

References

  1. Marcos K Aguilera. Stumbling over consensus research: Misunderstandings and issues. In Replication, pages 59-72. Springer, 2010. Google Scholar
  2. Rachid Guerraoui, Michel Hurfinn, Achour Mostéfaoui, Riucarlos Oliveira, Michel Raynal, and André Schiper. Consensus in asynchronous distributed systems: A concise guided tour. In Advances in Distributed Systems, pages 33-47. Springer, 2000. Google Scholar
  3. Joseph Y Halpern and Mark R Tuttle. Knowledge, probability, and adversaries. Journal of the ACM (JACM), 40(4):917-960, 1993. Google Scholar
  4. Eng Keong Lua, Jon Crowcroft, Marcelo Pias, Ravi Sharma, and Steven Lim. A survey and comparison of peer-to-peer overlay network schemes. IEEE Communications Surveys & Tutorials, 7(2):72-93, 2005. Google Scholar
  5. Nancy A Lynch. Distributed algorithms. Elsevier, 1996. Google Scholar
  6. Ran Tamir, Ariel Livshits, and Yonatan Shadmi. Simple majority consensus in networks with unreliable communication. arXiv preprint, 2021. URL: http://arxiv.org/abs/2104.04996.
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