Document Open Access Logo

Byzantine Agreement with Median Validity

Authors David Stolz, Roger Wattenhofer

PDF

File

Thumbnail PDF
PDF
LIPIcs.OPODIS.2015.22.pdf
  • Filesize: 466 kB
  • 14 pages

Document Identifiers

Subject Classification

Keywords
  • Reliability
  • fault-tolerance
  • median
  • consensus

Metrics

Abstract

We introduce a stronger validity property for the byzantine agreement problem with orderable initial values: The median validity property. In particular, the decision value is required to be close to the median of the initial values of the non-byzantine nodes. The proximity to the median scales with the desired level of fault-tolerance: If no fault-tolerance is required, algorithms have to decide for the true median. If the number of failures is maximal, algorithms must still decide on a value within the range of the input values of the non-byzantine nodes. We present a deterministic algorithm satisfying this property for n >= 3t+1 within t+1 phases, where t is the maximum number of byzantine nodes and n is the total number of nodes.

Cite As Get BibTex

David Stolz and Roger Wattenhofer. Byzantine Agreement with Median Validity. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 22:1-22:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.OPODIS.2015.22

Author Details

David Stolz
Roger Wattenhofer

References

  1. Atul Adya, William J Bolosky, Miguel Castro, Gerald Cermak, Ronnie Chaiken, John R Douceur, Jon Howell, Jacob R Lorch, Marvin Theimer, and Roger P Wattenhofer. Farsite: Federated, available, and reliable storage for an incompletely trusted environment. ACM SIGOPS Operating Systems Review, 36(SI):1-14, 2002. Google Scholar
  2. Michael Ben-Or. Another advantage of free choice (extended abstract): Completely asynchronous agreement protocols. In Proceedings of the second annual ACM symposium on Principles of distributed computing, pages 27-30. ACM, 1983. Google Scholar
  3. Piotr Berman and Juan A Garay. Asymptotically optimal distributed consensus. Springer, 1989. Google Scholar
  4. Piotr Berman, Juan A Garay, and Kenneth J Perry. Towards optimal distributed consensus. In Foundations of Computer Science, 1989., 30th Annual Symposium on, pages 410-415. IEEE, 1989. Google Scholar
  5. Mike Burrows. The chubby lock service for loosely-coupled distributed systems. In Proceedings of the 7th symposium on Operating systems design and implementation, pages 335-350. USENIX Association, 2006. Google Scholar
  6. Miguel Castro, Barbara Liskov, et al. Practical byzantine fault tolerance. In OSDI, volume 99, pages 173-186, 1999. Google Scholar
  7. Danny Dolev, Nancy A Lynch, Shlomit S Pinter, Eugene W Stark, and William E Weihl. Reaching approximate agreement in the presence of faults. Journal of the ACM (JACM), 33(3):499-516, 1986. Google Scholar
  8. Danny Dolev, Ruediger Reischuk, and H Raymond Strong. Early stopping in byzantine agreement. Journal of the ACM (JACM), 37(4):720-741, 1990. Google Scholar
  9. Michael J Fischer and Nancy A Lynch. A lower bound for the time to assure interactive consistency. Information processing letters, 14(4):183-186, 1982. Google Scholar
  10. Michael J Fischer, Nancy A Lynch, and Michael S Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM (JACM), 32(2):374-382, 1985. Google Scholar
  11. Matthias Fitzi and Juan A Garay. Efficient player-optimal protocols for strong and differential consensus. In Proceedings of the twenty-second annual symposium on Principles of distributed computing, pages 211-220. ACM, 2003. Google Scholar
  12. Oded Goldreich and Erez Petrank. The best of both worlds: Guaranteeing termination in fast randomized byzantine agreement protocols. Information Processing Letters, 36(1):45-49, 1990. Google Scholar
  13. Rachid Guerraoui, Nikola Knežević, Vivien Quéma, and Marko Vukolić. The next 700 bft protocols. In Proceedings of the 5th European conference on Computer systems, pages 363-376. ACM, 2010. Google Scholar
  14. Andreas Haeberlen, Petr Kouznetsov, and Peter Druschel. The case for byzantine fault detection. In HotDep, 2006. Google Scholar
  15. Patrick Hunt, Mahadev Konar, Flavio Paiva Junqueira, and Benjamin Reed. Zookeeper: Wait-free coordination for internet-scale systems. In USENIX Annual Technical Conference, volume 8, page 9, 2010. Google Scholar
  16. Soummya Kar and José MF Moura. Distributed consensus algorithms in sensor networks with imperfect communication: Link failures and channel noise. Signal Processing, IEEE Transactions on, 57(1):355-369, 2009. Google Scholar
  17. Ramakrishna Kotla, Lorenzo Alvisi, Mike Dahlin, Allen Clement, and Edmund Wong. Zyzzyva: speculative byzantine fault tolerance. ACM SIGOPS Operating Systems Review, 41(6):45-58, 2007. Google Scholar
  18. Leslie Lamport and P Michael Melliar-Smith. Synchronizing clocks in the presence of faults. Journal of the ACM (JACM), 32(1):52-78, 1985. Google Scholar
  19. Leslie Lamport, Robert Shostak, and Marshall Pease. The byzantine generals problem. ACM Trans. on Programming Languages and Systems (TOPLAS), 4(3):382-401, 1982. Google Scholar
  20. Jacob R Lorch, Atul Adya, William J Bolosky, Ronnie Chaiken, John R Douceur, and Jon Howell. The smart way to migrate replicated stateful services. ACM SIGOPS Operating Systems Review, 40(4):103-115, 2006. Google Scholar
  21. Gil Neiger. Distributed consensus revisited. Information Processing Letters, 49(4):195-201, 1994. Google Scholar
  22. Diego Ongaro and John Ousterhout. In search of an understandable consensus algorithm. In Proc. USENIX Annual Technical Conference, pages 305-320, 2014. Google Scholar
  23. Stacy Patterson, Bassam Bamieh, and Amr El Abbadi. Distributed average consensus with stochastic communication failures. In Decision and Control, 2007 46th IEEE Conference on, pages 4215-4220. IEEE, 2007. Google Scholar
  24. Marshall Pease, Robert Shostak, and Leslie Lamport. Reaching agreement in the presence of faults. Journal of the ACM (JACM), 27(2):228-234, 1980. Google Scholar
  25. Wei Ren and Randal W Beard. Distributed consensus in multi-vehicle cooperative control. Springer, 2008. Google Scholar
  26. Lili Su and Nitin Vaidya. Byzantine multi-agent optimization: Part I. arXiv preprint arXiv:1506.04681, 2015. Google Scholar
  27. Timothy Wood, Rahul Singh, Arun Venkataramani, Prashant Shenoy, and Emmanuel Cecchet. Zz and the art of practical bft execution. In Proceedings of the sixth conference on Computer systems, pages 123-138. ACM, 2011. Google Scholar
  28. Lin Xiao, Stephen Boyd, and Seung-Jean Kim. Distributed average consensus with least-mean-square deviation. Journal of Parallel and Distributed Computing, 67(1):33-46, 2007. Google Scholar
  29. Lin Xiao, Stephen Boyd, and Sanjay Lall. A scheme for robust distributed sensor fusion based on average consensus. In Information Processing in Sensor Networks, 2005. IPSN 2005. Fourth International Symposium on, pages 63-70. IEEE, 2005. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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