Abstract
Current reconfiguration techniques depend on starting the system in a consistent configuration, in which all participating entities are in a predefined state. Starting from that state, the system must preserve consistency as long as a predefined churn rate of processors joins and leaves is not violated, and unbounded storage is available. Many systems cannot control this churn rate and lack access to unbounded storage. System designers that neglect the outcome of violating the above assumptions may doom the system to exhibit illegal behaviors. We present the first automatically recovering reconfiguration scheme that recovers from transient faults, such as temporal violations of the above assumptions. Our self-stabilizing solutions regain safety automatically by assuming temporal access to reliable failure detectors (FDs). Once safety is established, the FD reliability is no longer needed. Still, liveness is conditioned by the FD’s unreliable signals. Our self-stabilizing reconfiguration techniques can serve as the basis for the implementation of several dynamic services over message passing systems. Examples include self-stabilizing reconfigurable virtual synchrony, extendable to a self-stabilizing reconfigurable state machine replication.
A full version of this paper can be found in [8].
S. Dolev—The research was partially supported by the Rita Altura Trust Chair in Computer Sciences; Frankel center for computer science, grant of the Ministry of Science, Technology and Space, Israel, and the National Science Council (NSC) of Taiwan; the Ministry of Foreign Affairs, Italy; the Ministry of Science, Technology and Space, Infrastructure Research in the Field of Advanced Computing and Cyber Security and the Israel National Cyber Bureau.
I. Marcoullis—Partially supported by a Doctoral Scholarship program of the University of Cyprus.
This is a preview of subscription content, log in via an institution.
Buying options
Tax calculation will be finalised at checkout
Purchases are for personal use only
Learn about institutional subscriptionsNotes
- 1.
Transient faults pose challenges in managing dynamic membership that justify the use of FDs; see discussion in Related work.
References
Aguilera, M.K., Keidar, I., Malkhi, D., Shraer, A.: Dynamic atomic storage without consensus. J. ACM 58(2), 7 (2011)
Alon, N., Attiya, H., Dolev, S., Dubois, S., Potop-Butucaru, M., Tixeuil, S.: Practically stabilizing SWMR atomic memory in message-passing systems. J. Comp. Syst. Sci. 81(4), 692–701 (2015)
Attiya, H., Chung, H.C., Ellen, F., Kumar, S., Welch, J.L.: Simulating a shared register in an asynchronous system that never stops changing. In: Moses, Y. (ed.) DISC 2015. LNCS, vol. 9363, pp. 75–91. Springer, Heidelberg (2015). doi:10.1007/978-3-662-48653-5_6
Birman, K., Malkhi, D., van Renesse, R.: Virtually synchronous methodology for dynamic service replication. Technical report MSR-TR-2010-151, Microsoft Research (2010)
Blanchard, P., Dolev, S., Beauquier, J., Delaët, S.: Practically self-stabilizing paxos replicated state-machine. In: Noubir, G., Raynal, M. (eds.) NETYS 2014. LNCS, vol. 8593, pp. 99–121. Springer, Cham (2014). doi:10.1007/978-3-319-09581-3_8
Dolev, S.: Self-Stabilization. The MIT press, Cambridge (2000)
Dolev, S., Georgiou, C., Marcoullis, I., Schiller, E.M.: Self-stabilizing virtual synchrony. In: Pelc, A., Schwarzmann, A.A. (eds.) SSS 2015. LNCS, vol. 9212, pp. 248–264. Springer, Cham (2015). doi:10.1007/978-3-319-21741-3_17
Dolev, S., Georgiou, C., Marcoullis, I., Schiller, E.M.: Self-stabilizing reconfiguration. CoRR, abs/1606.00195 (2016)
Dolev, S., Hanemann, A., Schiller, E.M., Sharma, S.: Self-stabilizing end-to-end communication in (bounded capacity, omitting, duplicating and non-FIFO) dynamic networks. In: Richa, A.W., Scheideler, C. (eds.) SSS 2012. LNCS, vol. 7596, pp. 133–147. Springer, Heidelberg (2012). doi:10.1007/978-3-642-33536-5_14
Dolev, S., Herman, T.: Superstabilizing protocols for dynamic distributed systems. Chicago J. Theor. Comput. Sci. (1997)
Dolev, S., Schiller, E., Welch, J.L.: Random walk for self-stabilizing group communication in ad hoc networks. IEEE Trans. Mob. Comput. 5(7), 893–905 (2006)
Dolev, S., Tzachar, N.: Empire of colonies: self-stabilizing and self-organizing distributed algorithm. Theor. Comput. Sci. 410(6–7), 514–532 (2009)
Gafni, E., Malkhi, D.: Elastic configuration maintenance via a parsimonious speculating snapshot solution. In: Moses, Y. (ed.) DISC 2015. LNCS, vol. 9363, pp. 140–153. Springer, Heidelberg (2015). doi:10.1007/978-3-662-48653-5_10
Gilbert, S., Lynch, N.A., Shvartsman, A.A.: Rambo: a robust, reconfigurable atomic memory service for dynamic networks. Distrib. Comput. 23(4), 225–272 (2010)
Jehl, L., Vitenberg, R., Meling, H.: SmartMerge: a new approach to reconfiguration for atomic storage. In: Moses, Y. (ed.) DISC 2015. LNCS, vol. 9363, pp. 154–169. Springer, Heidelberg (2015). doi:10.1007/978-3-662-48653-5_11
Lamport, L., Malkhi, D., Zhou, L.: Reconfiguring a state machine. SIGACT News 41(1), 63–73 (2010)
Musial, P.M., Nicolaou, N.C., Shvartsman, A.A.: Implementing distributed shared memory for dynamic networks. Commun. ACM 57(6), 88–98 (2014)
Spiegelman, A., Keidar, I., Malkhi, D.: Dynamic reconfiguration: a tutorial. In: OPODIS (2015)
Vukolic, M.: Quorum Systems: With Applications to Storage and Consensus. Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool Publishers, San Rafael (2012)
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
Dolev, S., Georgiou, C., Marcoullis, I., Schiller, E.M. (2017). Self-stabilizing Reconfiguration. In: El Abbadi, A., Garbinato, B. (eds) Networked Systems. NETYS 2017. Lecture Notes in Computer Science(), vol 10299. Springer, Cham. https://doi.org/10.1007/978-3-319-59647-1_5
Download citation
DOI: https://doi.org/10.1007/978-3-319-59647-1_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-59646-4
Online ISBN: 978-3-319-59647-1
eBook Packages: Computer ScienceComputer Science (R0)