Abstract
This brief announcement presents a fault-tolerant self-stabilizing distributed clock synchronization protocol for an arbitrary, non-partitioned digraph. Synchronization algorithms are essential for managing the use of resources and controlling communication in a distributed system. Synchronization of a distributed system is the process of achieving and maintaining a bounded skew among independent local time clocks. A distributed system is said to be self-stabilizing if, from an arbitrary state, it is guaranteed to reach a legitimate state in a finite amount of time and remain in a legitimate state. For clock synchronization, a legitimate state is a state where all parts in the system are in synchrony. The self-stabilizing distributed-system clock synchronization problem is, therefore, to develop an algorithm (i.e., a protocol) to achieve and maintain synchrony of local clocks in a distributed system after experiencing system-wide disruptions in the presence of network element imperfections. The convergence and closure properties address achieving and maintaining networksynchrony, respectively.
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
Torres-Pomales, W., Malekpour, M.R., Miner, P.S.: ROBUS-2: A fault-tolerant broadcast communication system. NASA/TM-2005-213540, p. 201 (March 2005)
Dolev, S., Welch, J.L.: Self-Stabilizing Clock Synchronization in the Presence of Byzantine Faults. Journal of the ACM 51(5), 780–799 (2004)
Srikanth, T.K., Toueg, S.: Optimal clock synchronization. Journal of the ACM 34(3), 626–645 (1987)
Davies, D., Wakerly, J.F.: Synchronization and matching in redundant systems. IEEE Transactions on Computers 27(6), 531–539 (1978)
Malekpour, M.R.: A Self-Stabilizing Synchronization Protocol For Arbitrary Digraphs. In: The 17th IEEE Pacific Rim International Symposium on Dependable Computing (PRDC 2011), Pasadena, California, December 12-14 (2011)
Malekpour, M.R.: Model Checking A Self-Stabilizing Synchronization Protocol For Arbitrary Digraphs. In: The 31st Digital Avionics Systems Conference (DASC), Williamsburg, Virginia (to appear October 14-18, 2012)
Malekpour, M.R.: Correctness Proof of A Self-Stabilizing Synchronization Protocol For Arbitrary Digraphs. NASA/TM-2011-217184, p. 31 (October 2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Malekpour, M.R. (2012). Brief Announcement: Self-stabilizing Synchronization of Arbitrary Digraphs in Presence of Faults. In: Richa, A.W., Scheideler, C. (eds) Stabilization, Safety, and Security of Distributed Systems. SSS 2012. Lecture Notes in Computer Science, vol 7596. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-33536-5_4
Download citation
DOI: https://doi.org/10.1007/978-3-642-33536-5_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-33535-8
Online ISBN: 978-3-642-33536-5
eBook Packages: Computer ScienceComputer Science (R0)