Abstract
This paper addresses reconfiguration of a Replicated State Machine (RSM) in an asynchronous system. It is well known that consensus cannot be solved in an asynchronous system. Therefore an RSM providing strong consistency, cannot guarantee progress in an asynchronous system. However, we show that reconfiguring the RSM is possible in a purely asynchronous system. This differs from all existing reconfiguration methods which rely on consensus to choose a new configuration. Since a reconfiguration to a new set of machines or even a different datacenter can serve to restore synchrony between replicas, asynchronous reconfiguration can also serve to increase the availability of an RSM.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Schneider, F.B.: Implementing fault-tolerant services using the state machine approach: a tutorial. ACM Comput. Surv. 22(4), 299–319 (1990)
Lamport, L.: The part-time parliament. ACM Trans. Comput. Syst. 16(2), 133–169 (1998)
Lamport, L.: Paxos made simple. ACM SIGACT News (December 2001)
Shraer, A., Reed, B., Malkhi, D., Junqueira, F.: Dynamic reconfiguration of primary/backup clusters. USENIX ATC (2011)
Lamport, L., Malkhi, D., Zhou, L.: Vertical paxos and primary-backup replication. In: PODC (2009)
Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of distributed consensus with one faulty process. J. ACM 32(2), 374–382 (1985)
Chandra, T.D., Hadzilacos, V., Toueg, S., Charron-Bost, B.: On the impossibility of group membership. In: PODC (1996)
Chandra, T.D., Toueg, S.: Unreliable failure detectors for reliable distributed systems. J. ACM 43, 225–267 (1996)
Lamport, L., Malkhi, D., Zhou, L.: Reconfiguring a state machine. SIGACT News 41(1), 63–73 (2010)
Lorch, J.R., Adya, A., Bolosky, W.J., Chaiken, R., Douceur, J.R., Howell, J.: The smart way to migrate replicated stateful services. In: EuroSys (2006)
Aguilera, M.K., Keidar, I., Malkhi, D., Shraer, A.: Dynamic atomic storage without consensus. J. ACM 58(2), 7 (2011)
Chockler, G.V., Keidar, I., Vitenberg, R.: Group communication specifications: a comprehensive study. ACM Comput. Surv. 33(4), 427–469 (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Jehl, L., Meling, H. (2014). Asynchronous Reconfiguration for Paxos State Machines. In: Chatterjee, M., Cao, Jn., Kothapalli, K., Rajsbaum, S. (eds) Distributed Computing and Networking. ICDCN 2014. Lecture Notes in Computer Science, vol 8314. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-45249-9_8
Download citation
DOI: https://doi.org/10.1007/978-3-642-45249-9_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-45248-2
Online ISBN: 978-3-642-45249-9
eBook Packages: Computer ScienceComputer Science (R0)