Abstract
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 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, 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 provide a description of Generalized Paxos that is easier to understand, 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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ahamad, M., Neiger, G., Burns, J.E., Kohli, P., Hutto, P.W.: Causal memory: definitions, implementation, and programming. Distrib. Comput. 9(1), 37–49 (1995)
Burrows, M.: The chubby lock service for loosely-coupled distributed systems. In: Proceedings of 7th Symposium on Operating Systems Design and Implementation (2006)
Cachin, C., Guerraoui, R., Rodrigues, L.: Introduction to Reliable and Secure Distributed Programming, 2nd edn. Springer, Heidelberg (2011). doi:10.1007/978-3-642-15260-3
Castro, M., Liskov, B.: Practical byzantine fault tolerance. In: Proceedings of 3rd Symposium on Operating Systems Design and Implementation (OSDI) (1999)
De Prisco, R., Lampson, B., Lynch, N.A.: Revisiting the paxos algorithm. In: Mavronicolas, M., Tsigas, P. (eds.) WDAG 1997. LNCS, vol. 1320, pp. 111–125. Springer, Heidelberg (1997). doi:10.1007/BFb0030679
DeCandia, G., et al.: Dynamo: Amazon’s highly available key-value store. In: Proceedings of 21st Symposium on Operating Systems Principles (SOSP) (2007)
Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of distributed consensus with one faulty process. J. ACM 32(2), 374–382 (1985)
Junqueira, F., Reed, B., Serafini, M.: Zab: high-performance broadcast for primary-backup systems. In: 41st International Conference on Dependable Systems and Networks (2011)
Ladin, R., Liskov, B., Shrira, L.: Lazy replication: exploiting the semantics of distributed services. In: Proceedings of 9th Symposium on Principles Distributed Computing (1990)
Lamport, L.: The part-time parliament. Technical report, DEC SRC (1989)
Lamport, L.: The part-time parliament. ACM Trans. Comput. Syst. 16(2), 133–169 (1998)
Lamport, L.: Paxos made simple. SIGACT News 32(4), 18–25 (2001)
Lamport, L.: Generalized consensus and paxos. Technical report, Technical Report MSR-TR-2005-33, Microsoft Research (2005)
Lamport, L.: Fast paxos. Distrib. Comput. 19(2), 79–103 (2006)
Lamport, L.: Byzantizing paxos by refinement. In: Peleg, D. (ed.) DISC 2011. LNCS, vol. 6950, pp. 211–224. Springer, Heidelberg (2011). doi:10.1007/978-3-642-24100-0_22
Lamport, L., Shostak, R., Pease, M.: The byzantine generals problem. ACM Trans. Progr. Lang. Syst. 4(3), 382–401 (1982)
Lee, E.K., Thekkath, C.A.: Petal: distributed virtual disks. In: Proceedings of 7th International Conference on Architectural Support for Programming Languages and Operating Systems (1996)
Li, C., Porto, D., Clement, A., Gehrke, J., Preguiça, N., Rodrigues, R.: Making geo-replicated systems fast as possible, consistent when necessary. In: Proceedings of 10th Symposium on Operating Systems Design and Implementation (OSDI) (2012)
Mao, Y., Junqueira, F.P., Marzullo, K.: Mencius: building efficient replicated state machines for WANs. In: Proceedings of 8th Symposium on Operating Systems Design and Implementation (OSDI) (2008)
Martin, J.P., Alvisi, L.: Fast byzantine consensus. IEEE Trans. Dependable Secur. Comput. 3(3), 202–215 (2006)
Moraru, I., Andersen, D.G., Kaminsky, M.: There is more consensus in Egalitarian parliaments. In: Proceedings of Symposium on Operating Systems Principles (SOSP) (2013)
Nakamoto, S.: Bitcoin: a peer-to-peer electronic cash system (2008)
Pires, M., Ravi, S., Rodrigues, R.: Generalized Paxos Made Byzantine (and Less Complex). Tech. rep. (2017)
van Renesse, R.: Paxos made moderately complex. ACM Comput. Surv. 47(3), 1–36 (2011)
Singh, A., Fonseca, P., Kuznetsov, P.: Zeno: eventually consistent byzantine-fault tolerance. In: Proceedings of 6th Symposium on Networked Systems Design and Implementation (NSDI) (2009)
Vukolic, M.: Quorum systems: with applications to storage and consensus. In: Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool (2012)
Acknowledgements
This work was supported by the European Research Council (ERC-2012-StG-307732) and FCT (UID/CEC/50021/2013).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Pires, M., Ravi, S., Rodrigues, R. (2017). Generalized Paxos Made Byzantine (and Less Complex). In: Spirakis, P., Tsigas, P. (eds) Stabilization, Safety, and Security of Distributed Systems. SSS 2017. Lecture Notes in Computer Science(), vol 10616. Springer, Cham. https://doi.org/10.1007/978-3-319-69084-1_14
Download citation
DOI: https://doi.org/10.1007/978-3-319-69084-1_14
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-69083-4
Online ISBN: 978-3-319-69084-1
eBook Packages: Computer ScienceComputer Science (R0)