{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T23:56:27Z","timestamp":1790812587544,"version":"4.1.0"},"reference-count":25,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2018,9,17]],"date-time":"2018-09-17T00:00:00Z","timestamp":1537142400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>One of the most recent members of the Paxos family of protocols is Generalized Paxos. This variant of Paxos has the characteristic that it departs from the original specification of consensus, allowing for a weaker safety condition where different processes can have a different views on a sequence being agreed upon. However, much like the original Paxos counterpart, Generalized Paxos does not have a simple implementation. Furthermore, with the recent practical adoption of Byzantine fault tolerant protocols in the context of blockchain protocols, it is timely and important to understand how Generalized Paxos can be implemented in the Byzantine model. In this paper, we make two main contributions. First, we attempt to provide a simpler description of Generalized Paxos, based on a simpler specification and the pseudocode for a solution that can be readily implemented. Second, we extend the protocol to the Byzantine fault model, and provide the respective correctness proof.<\/jats:p>","DOI":"10.3390\/a11090141","type":"journal-article","created":{"date-parts":[[2018,9,17]],"date-time":"2018-09-17T10:42:20Z","timestamp":1537180940000},"page":"141","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Generalized Paxos Made Byzantine (and Less Complex)"],"prefix":"10.3390","volume":"11","author":[{"given":"Miguel","family":"Pires","sequence":"first","affiliation":[{"name":"INESC-ID and Instituto Superior T\u00e9cnico (Universidade de Lisboa), R. Alves Redol 9, 1000-029 Lisbon, Portugal"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Srivatsan","family":"Ravi","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Information Sciences Insititute, University of Southern California, Los Angeles, CA 90007, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8367-4024","authenticated-orcid":false,"given":"Rodrigo","family":"Rodrigues","sequence":"additional","affiliation":[{"name":"INESC-ID and Instituto Superior T\u00e9cnico (Universidade de Lisboa), R. Alves Redol 9, 1000-029 Lisbon, Portugal"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2018,9,17]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1145\/279227.279229","article-title":"The Part-Time Parliament","volume":"16","author":"Lamport","year":"1998","journal-title":"ACM Trans. Comput. Syst."},{"key":"ref_2","unstructured":"Lamport, L. (1989). The Part-Time Parliament, DEC SRC. Technical Report."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"De Prisco, R., Lampson, B., and Lynch, N.A. (1997). Revisiting the Paxos Algorithm. Distributed Algorithms, Proceedings of the 11th Workshop on Distributed Algorithms, Saarbr\u00fccken, Germany, 24\u201326 September 1997, Springer. LNCS 1320.","DOI":"10.1007\/BFb0030679"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Lee, E.K., and Thekkath, C.A. (1996, January 1\u20134). Petal: Distributed Virtual Disks. Proceedings of the 7th International Conference on Architectural Support for Programming Languages and Operating Systems, Cambridge, MA, USA.","DOI":"10.1145\/237090.237157"},{"key":"ref_5","unstructured":"Burrows, M. (2006, January 6\u20138). The Chubby Lock Service for Loosely-coupled Distributed Systems. Proceedings of the 7th Symposium on Operating Systems Design and Implementation, Seattle, WA, USA."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Junqueira, F., Reed, B., and Serafini, M. (2011, January 27\u201330). Zab: High-performance Broadcast for Primary-backup Systems. Proceedings of the 41st International Conference on Dependable Systems and Networks, Hong Kong, China.","DOI":"10.1109\/DSN.2011.5958223"},{"key":"ref_7","first-page":"18","article-title":"Paxos Made Simple","volume":"32","author":"Lamport","year":"2001","journal-title":"SIGACT News"},{"key":"ref_8","first-page":"1","article-title":"Paxos Made Moderately Complex","volume":"47","year":"2011","journal-title":"ACM Comput. Surv."},{"key":"ref_9","unstructured":"Castro, M., and Liskov, B. (1999, January 22\u201325). Practical Byzantine Fault Tolerance. Proceedings of the 3rd Symposium on Operating Systems Design and Implementation (OSDI), New Orleans, LA, USA."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Peleg, D. (2011). Byzantizing Paxos by Refinement. Distributed Computing, Proceedings of the 25th International Symposium (DISC 2011), Rome, Italy, 20\u201322 September 2011, Springer.","DOI":"10.1007\/978-3-642-24100-0"},{"key":"ref_11","unstructured":"Nakamoto, S. (2018, September 17). Bitcoin: A Peer-to-Peer Electronic Cash System. Available online: https:\/\/bitcoin.org\/en\/bitcoin-paper."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/s00446-006-0005-x","article-title":"Fast paxos","volume":"19","author":"Lamport","year":"2006","journal-title":"Distrib. Comput."},{"key":"ref_13","unstructured":"Lamport, L. (2005). Generalized Consensus and Paxos, Available online: https:\/\/www.microsoft.com\/en-us\/research\/publication\/generalized-consensus-and-paxos\/."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Ladin, R., Liskov, B., and Shrira, L. (1990, January 22\u201324). Lazy replication: Exploiting the semantics of Distributed Services. Proceedings of the 9th Symposium on Principles Distributed Computing, Quebec City, QC, Canada.","DOI":"10.1145\/93385.93399"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"DeCandia, G., Hastorun, D., Jampani, M., Kakulapati, M., Lakshman, A., Pilchin, A., Sivasubramanian, S., Vosshall, P., and Vogels, W. (2007, January 14\u201317). Dynamo: Amazon\u2019s Highly Available Key-value Store. Proceedings of the 21st ACM SIGOPS Symposium on Operating Systems Principles (SOSP \u201907), Stevenson, WA, USA.","DOI":"10.1145\/1294261.1294281"},{"key":"ref_16","unstructured":"Spirakis, P., and Tsigas, P. (2017). Generalized Paxos Made Byzantine (and Less Complex). Stabilization, Safety, and Security of Distributed Systems, Springer International Publishing."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1145\/3149.214121","article-title":"Impossibility of Distributed Consensus with one Faulty Process","volume":"32","author":"Fischer","year":"1985","journal-title":"J. ACM"},{"key":"ref_18","unstructured":"Mao, Y., Junqueira, F.P., and Marzullo, K. (2008, January 8\u201310). Mencius: Building Efficient Replicated State Machines for WANs. Proceedings of the Symposium on Operating System Design and Implementation, San Diego, CA, USA."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Moraru, I., Andersen, D.G., and Kaminsky, M. (2013, January 3\u20136). There is more consensus in Egalitarian parliaments. Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles (Sosp \u201913), Farminton, PA, USA.","DOI":"10.1145\/2517349.2517350"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1145\/357172.357176","article-title":"The Byzantine Generals Problem","volume":"4","author":"Lamport","year":"1982","journal-title":"ACM Trans. Progr. Lang. Syst."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1145\/7531.7533","article-title":"On the Minimal Synchronism Needed for Distributed Consensus","volume":"34","author":"Dolev","year":"1987","journal-title":"J. ACM"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Vukolic, M. (2018, September 17). Quorum Systems: With Applications to Storage and Consensus; Synthesis Lectures on Distributed Computing Theory, Morgan & Claypool; 2012. Available online: https:\/\/www.morganclaypool.com\/doi\/abs\/10.2200\/S00402ED1V01Y201202DCT009.","DOI":"10.1007\/978-3-031-02007-0_5"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Cachin, C., Guerraoui, R., and Rodrigues, L.E.T. (2011). Introduction to Reliable and Secure Distributed Programming, Springer. [2nd ed.].","DOI":"10.1007\/978-3-642-15260-3"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/BF01784241","article-title":"Causal memory: Definitions, implementation, and programming","volume":"Volume 9","author":"Ahamad","year":"1995","journal-title":"Distributed Computing"},{"key":"ref_25","unstructured":"Li, C., Porto, D., Clement, A., Gehrke, J., Pregui\u00e7a, N., and Rodrigues, R. (2012, January 8\u201310). Making Geo-Replicated Systems Fast as Possible, Consistent when Necessary. Proceedings of the 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI \u201912), Hollywood, CA, USA."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/9\/141\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:21:02Z","timestamp":1760196062000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/9\/141"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9,17]]},"references-count":25,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2018,9]]}},"alternative-id":["a11090141"],"URL":"https:\/\/doi.org\/10.3390\/a11090141","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,9,17]]}}}