Document Open Access Logo

Heterogeneous Paxos

Authors Isaac Sheff , Xinwen Wang , Robbert van Renesse , Andrew C. Myers

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2020.5.pdf
  • Filesize: 0.55 MB
  • 17 pages

Document Identifiers

Author Details

Isaac Sheff
  • Max Planck Institute for Software Systems, Saarland Informatics Campus, Saarbrücken, Germany
Xinwen Wang
  • Cornell University, Ithaca, NY, USA
Robbert van Renesse
  • Cornell University, Ithaca, NY, USA
Andrew C. Myers
  • Cornell University, Ithaca, NY, USA

Cite As Get BibTex

Isaac Sheff, Xinwen Wang, Robbert van Renesse, and Andrew C. Myers. Heterogeneous Paxos. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 5:1-5:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.OPODIS.2020.5

Abstract

In distributed systems, a group of learners achieve consensus when, by observing the output of some acceptors, they all arrive at the same value. Consensus is crucial for ordering transactions in failure-tolerant systems. Traditional consensus algorithms are homogeneous in three ways:  
- all learners are treated equally, 
- all acceptors are treated equally, and 
- all failures are treated equally.  These assumptions, however, are unsuitable for cross-domain applications, including blockchains, where not all acceptors are equally trustworthy, and not all learners have the same assumptions and priorities. We present the first consensus algorithm to be heterogeneous in all three respects. Learners set their own mixed failure tolerances over differently trusted sets of acceptors. We express these assumptions in a novel Learner Graph, and demonstrate sufficient conditions for consensus.
We present Heterogeneous Paxos, an extension of Byzantine Paxos. Heterogeneous Paxos achieves consensus for any viable Learner Graph in best-case three message sends, which is optimal. We present a proof-of-concept implementation and demonstrate how tailoring for heterogeneous scenarios can save resources and reduce latency.

Subject Classification

ACM Subject Classification
  • Computer systems organization → Redundancy
  • Computer systems organization → Availability
  • Computer systems organization → Reliability
  • Computer systems organization → Peer-to-peer architectures
  • Theory of computation → Distributed algorithms
  • Information systems → Remote replication
Keywords
  • Consensus
  • Trust
  • Heterogeneous Trust

Metrics

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

Related Versions

Supplementary Materials

References

  1. https://www.hyperledger.org/wp-content/uploads/2018/08/HL_Whitepaper_IntroductiontoHyperledger.pdf, 2018. URL: https://www.hyperledger.org/wp-content/uploads/2018/08/HL_Whitepaper_IntroductiontoHyperledger.pdf.
  2. https://github.com/ConsenSys/quorum/blob/master/docs/Quorum%20Whitepaper%20v0.2.pdf, 2018. URL: https://github.com/ConsenSys/quorum/blob/master/docs/Quorum%20Whitepaper%20v0.2.pdf.
  3. A. S. Aiyer, L. Alvisi, A. Clement, M. Dahlin, J. Martin, and C. Porth. http://dx.doi.org/10.1145/1095810.1095816. In SOSP, pages 45-58, 2005.
  4. E. A. Alchieri, A. N. Bessani, J. Silva Fraga, and F. Greve. http://dx.doi.org/10.1007/978-3-540-92221-6_4. In OPODIS, pages 22-40, 2008.
  5. E. Blum, J. Katz, and J. Loss. Synchronous consensus with optimal asynchronous fallback guarantees. In Theory of Cryptography, pages 131-150, 2019. Google Scholar
  6. G. Bracha and S. Toueg. http://dx.doi.org/10.1145/800221.806706. In PODC, pages 12-26, 1983.
  7. C. Cachin and M. Backes. https://doi.ieeecomputersociety.org/10.1109/DSN.2003.1209914. In DSN, 2003.
  8. C. Cachin and B. Tackmann. https://drops.dagstuhl.de/opus/volltexte/2020/11793/. In OPODIS, 2019.
  9. B. Calder, J. Wang, A. Ogus, N. Nilakantan, A. Skjolsvold, S. McKelvie, Y. Xu, S. Srivastav, J. Wu, and H. Simitci et al. Windows Azure Storage: a highly available cloud storage service with strong consistency. In SOSP, 2011. Google Scholar
  10. M. Castro and B. Liskov. Practical Byzantine fault tolerance. In OSDI, 1999. Google Scholar
  11. D. Cavin, Y. Sasson, and A. Schiper. http://dx.doi.org/10.1007/978-3-540-28634-9_11. In ADHOC-NOW, 2004.
  12. B. Chase and E. MacBrough. http://arxiv.org/abs/1802.07242. CoRR, abs/1802.07242, 2018.
  13. A. Clement, M. Kapritsos, S. Lee, Y. Wang, L. Alvisi, M. Dahlin, and T. Riche. http://www.cs.utexas.edu/users/lorenzo/papers/clement-sosp09.pdf. In SOSP, pages 277-290, 2009.
  14. J. C. Corbett, J. Dean, M. Epstein, A. Fikes, C. Frost, J. J. Furman, S. Ghemawat, A. Gubarev, C. Heiser, and P. Hochschild et al. Spanner: Google’s globally distributed database. TOCS, 31(3):8, 2013. Google Scholar
  15. M. Correia, N. Neves, and P. Veríssimo. From consensus to atomic broadcast: Time-free byzantine-resistant protocols without signatures. Comput. J., 49:82-96, January 2006. Google Scholar
  16. K. Croman, C. Decker, I. Eyal, A. E. Gencer, A. Juels, A. Kosba, A. Miller, P. Saxena, E. Shi, E. G. Sirer, D. Song, and R. Wattenhofer. https://fc16.ifca.ai/bitcoin/papers/CDE+16.pdf. In Financial Cryptography and Data Security, 2016.
  17. C. Delporte-Gallet, H. Fauconnier, R. Guerraoui, and A. Tielmann. http://dx.doi.org/10.1007/s00446-010-0122-4. Distributed Computing, 24:137-147, November 2011.
  18. C. Dwork, N. Lynch, and L. Stockmeyer. http://dx.doi.org/10.1145/42282.42283. J. ACM, 35(2):288–323, April 1988.
  19. M. J. Fischer, N. A. Lynch, and M. S. Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2):374-382, April 1985. Google Scholar
  20. Ethereum Foundation. https://github.com/ethereum/wiki/wiki/White-Paper. Technical report, Ethereum Foundation, 2018.
  21. Á. García-Pérez and A. Gotsman. http://drops.dagstuhl.de/opus/volltexte/2018/10077. In OPODIS, pages 17:1-17:16, 2018.
  22. D. K. Gifford. Weighted voting for replicated data. In SOSP, 1979. Google Scholar
  23. F. Greve and S. Tixeuil. http://dx.doi.org/10.1109/DSN.2007.61. In DSN, pages 82-91, 2007.
  24. https://grpc.io. https://grpc.io, 2018. URL: https://grpc.io.
  25. R. Guerraoui and M. Vukolić. http://dx.doi.org/10.1145/1281100.1281120. In PODC, 2007.
  26. M. Hearn and R. G. Brown. https://www.r3.com/reports/corda-technical-whitepaper/. Technical report, r3, 2019.
  27. F. Junqueira and K. Marzullo. Designing algorithms for dependent process failures. In Workshop on Future Directions in Distributed Computing, pages 24-28, 2003. Google Scholar
  28. L. Lamport. http://dx.doi.org/10.1145/279227.279229. TOCS, 16(2):133-169, May 1998.
  29. L. Lamport. https://www.microsoft.com/en-us/research/publication/paxos-made-simple/. Technical report, Microsoft Research, December 2001.
  30. L. Lamport. https://lamport.azurewebsites.net/tla/byzsimple.pdf. In DISC, pages 211-224, 2011.
  31. L. Lamport, R. Shostak, and M. Pease. The Byzantine Generals Problem. ACM Trans. on Programming Languages and Systems, 4(3):382-401, July 1982. Google Scholar
  32. B. W. Lampson and H. E. Sturgis. http://research.microsoft.com/en-us/um/people/blampson/21-crashrecovery/Abstract.html. Technical report, Xerox Palo Alto Research Center, Palo Alto, CA, 1979.
  33. S. Liu, P. Viotti, C. Cachin, V. Quéma, and M. Vukolic. https://www.usenix.org/system/files/conference/osdi16/osdi16-liu.pdf. In OSDI, 2016.
  34. M. Lokhava, G. Losa, D. Mazières, G. Hoare, N. P. E. Barry, E. Gafni, J. Jové, R. Malinowsky, and J. M. McCaleb. http://delivery.acm.org/10.1145/3360000/3359636/p80-lokhava.pdf. In SOSP, 2019.
  35. G. Losa, E. Gafni, and D. Mazières. Stellar consensus by instantiation. In DISC, 2019. Google Scholar
  36. E. MacBrough. http://arxiv.org/abs/1802.07240. CoRR, abs/1802.07240, 2018.
  37. D. Malkhi, K. Nayak, and L. Ren. http://dx.doi.org/10.1145/3319535.3354225. In CCS, 2019.
  38. D. Malkhi and M. Reiter. Byzantine quorum systems. In STOC, 1997. Google Scholar
  39. D. Mazières. https://www.stellar.org. https://www.stellar.org, April 2015.
  40. A. Miller, Y. Xia, K. Croman, E. Shi, and D. Song. http://dx.doi.org/10.1145/2976749.2978399. In CCS, pages 31-42, 2016.
  41. S. Nakamoto. Bitcoin: A peer-to-peer electronic cash system, 2008. Google Scholar
  42. B. Preneel. http://dx.doi.org/10.1007/978-1-4419-5906-5_565. In Encyclopedia of Cryptography and Security, 2011.
  43. https://developers.google.com/protocol-buffers/. https://developers.google.com/protocol-buffers/, 2018. URL: https://developers.google.com/protocol-buffers/.
  44. D. Schwartz, N. Youngs, and A. Britto. https://ripple.com/files/ripple_consensus_whitepaper.pdf. Technical report, Ripple Labs Inc, 2014.
  45. I. Sheff, R. van Renesse, and A. C. Myers. http://arxiv.org/abs/1412.3136. CoRR, abs/1412.3136(arXiv:1412.3136), December 2014.
  46. I. Sheff, X. Wang, H. Ni, R. van Renesse, and A. C. Myers. http://arxiv.org/abs/1905.03888, 2019.
  47. I. Sheff, X. Wang, R. van Renesse, and A. C. Myers. http://arxiv.org/abs/2011.08253, 2020.
  48. H. Siu, Y. Chin, and W. Yang. http://dx.doi.org/10.1109/71.667895. Parallel and Distributed Systems, 9(4), April 1998.
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