Abstract
Vector clock algorithms are basic wait-free building blocks that facilitate causal ordering of events. As wait-free algorithms, they are guaranteed to complete their operations within a finite number of steps. Stabilizing algorithms allow the system to recover after the occurrence of transient faults, such as soft errors and arbitrary violations of the assumptions according to which the system was designed to behave.
We present the first, to the best of our knowledge, stabilizing vector clock algorithm for asynchronous crash-prone message-passing systems that can recover in a wait-free manner after the occurrence of transient faults (as well as communication and crash failures) in the absence of execution fairness. We use bounded message and storage sizes and do not rely on any means of synchronization.
The proposed algorithm provides bounded time recovery during fair executions that follow the last transient fault. The novelty is for the case of more challenging settings that consider no execution fairness. The proposed algorithm guarantees a bound on the number of times in which the system might violate safety (while existing algorithms might block forever due to the presence of both transient faults and crash failures).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Georgiou, C., Shvartsman, A.A.: Cooperative task-oriented computing: algorithms and complexity. Synth. Lect. Distrib. Comput. Theory 2(2), 1–167 (2011)
Dijkstra, E.W.: Self-stabilizing systems in spite of distributed control. Commun. ACM 17(11), 643–644 (1974)
Burns, J.E., Gouda, M.G., Miller, R.E.: Stabilization and pseudo-stabilization. Distrib. Comput. 7(1), 35–42 (1993)
Alon, N., Attiya, H., Dolev, S., Dubois, S., Potop-Butucaru, M., Tixeuil, S.: Practically stabilizing SWMR atomic memory in message-passing systems. J. Comput. Syst. Sci. 81(4), 692–701 (2015)
Dolev, S., Kat, R.I., Schiller, E.M.: When consensus meets self-stabilization. J. Comput. Syst. Sci. 76(8), 884–900 (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). https://doi.org/10.1007/978-3-319-09581-3_8
Dolev, S., Georgiou, C., Marcoullis, I., Schiller, E.M.: Practically stabilizing virtual synchrony. In: Stabilization, Safety, and Security of Distributed Systems, SSS (2015)
Arora, A., Kulkarni, S.S., Demirbas, M.: Resettable vector clocks. J. Parallel Distrib. Comput. 66(2), 221–237 (2006)
Tanenbaum, A.S., Van Steen, M.: Distributed Systems: Principles and Paradigms. Prentice-Hall, Upper Saddle River (2007)
Almeida, J.B., Almeida, P.S., Baquero, C.: Bounded version vectors. In: Guerraoui, R. (ed.) DISC 2004. LNCS, vol. 3274, pp. 102–116. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-30186-8_8
Malkhi, D., Terry, D.B.: Concise version vectors in WinFS. Distrib. Comput. 20(3), 209–219 (2007)
Bonomi, S., Dolev, S., Potop-Butucaru, M., Raynal, M.: Stabilizing server-based storage in Byzantine asynchronous message-passing systems. In: Symposium on Principles of. Distributed Computing, PODC, pp. 471–479. ACM(2015)
Salem, I., Schiller, E.M.: Practically-self-stabilizing vector clocks in the absence of execution fairness. CoRR abs/1712.08205 (2017)
Dolev, S., Dubois, S., Potop-Butucaru, M., Tixeuil, S.: Stabilizing data-link over non-FIFO channels with optimal fault-resilience. Inf. Process. Lett. 111(18), 912–920 (2011)
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). https://doi.org/10.1007/978-3-642-33536-5_14
Dolev, S.: Self-Stabilization. MIT Press, Cambridge (2000)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Salem, I., Schiller, E.M. (2019). Practically-Self-stabilizing Vector Clocks in the Absence of Execution Fairness. In: Podelski, A., Taïani, F. (eds) Networked Systems. NETYS 2018. Lecture Notes in Computer Science(), vol 11028. Springer, Cham. https://doi.org/10.1007/978-3-030-05529-5_21
Download citation
DOI: https://doi.org/10.1007/978-3-030-05529-5_21
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-05528-8
Online ISBN: 978-3-030-05529-5
eBook Packages: Computer ScienceComputer Science (R0)