| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
A Time-Optimal Self-Stabilizing Synchronizer Using A Phase Clock
July-September 2007 (vol. 4 no. 3)
pp. 180-190
A synchronizer with a phase counter (sometimes called asynchronous phase clock) is an asynchronous distributed algorithm, where each node maintains a local ‘pulse counter’ that simulates the global clock in a synchronous network. In this paper we present a time optimal self-stabilizing scheme for such a synchronizer, assuming unbounded counters. We give a simple rule by which each node can compute its pulse number as a function of its neighbors’ pulse numbers. We also show that some of the popular correction functions for phase clock synchronization are not self-stabilizing in asynchronous networks. Using our rule, the counters stabilize in time bounded by the diameter of the network, without invoking global operations. We argue that the use of unbounded counters can be justified by the availability of memory for counters that are large enough to be practically unbounded, and by the existence of reset protocols that can be used to restart the counters in some rare cases where faults will make this necessary.
[1] 180 Y. Afek, S. Kutten, and M. Yung, “Local Detection for Global Self Stabilization,” Theoretical Computer Science, vol. 186, nos. 1-2, pp.199-230, Oct. 1997.[2] S. Aggarwal and S. Kutten, “Time Optimal Self-Stabilizing Spanning Tree Algorithms,” Proc. 13th Conf. Foundations of Software Technology and Theoretical Computer Science (FSTTCS '93), pp. 400-410, 1993.[3] A. Arora and M.G. Gouda, “Distributed Reset,” IEEE Trans. Computers, vol. 43, no. 9, pp. 1026-1038, Sept. 1994.[4] B. Awerbuch, “Complexity of Network Synchronization,” J. ACM, vol. 32, no. 4, pp. 804-823, Oct. 1985.[5] B. Awerbuch and R. Ostrovsky, “Memory-Efficient and Self-Stabilizing Network Reset,” Proc. 13th Ann. ACM Symp. Principles of Distributed Computing (PODC '94), pp. 254-263, 1994.[6] B. Awerbuch, B. Patt-Shamir, D. Peleg, and M. Saks, “Adapting to Asynchronous Dynamic Networks,” Proc. 24th Ann. ACM Symp. Theory of Computing (STOC '92), pp. 557-570, May 1992.[7] B. Awerbuch, B. Patt-Shamir, and G. Varghese, “Self-Stabilization by Local Checking and Correction,” Proc. 32nd Ann. Symp. Foundations of Computer Science (FOCS '91), pp. 268-277, Oct. 1991.[8] B. Awerbuch, B. Patt-Shamir, and G. Varghese, “Bounding the Unbounded,” Proc. 13th IEEE INFOCOM, pp. 776-783, June 1994.[9] B. Awerbuch, B. Patt-Shamir, G. Varghese, and S. Dolev, “Self-Stabilization by Local Checking and Global Reset (Extended Abstract),” Proc. Eighth Int'l Workshop Distributed Algorithms (WDAG '94), pp. 326-339, 1994.[10] B. Awerbuch and D. Peleg, “Network Synchronization with Polylogarithmic Overhead,” Proc. 31st Ann. Symp. Foundations of Computer Science (FOCS '90), 1990.[11] A. Arora, S. Dolev, and M.G. Gouda, “Maintaining Digital Clocks in Step,” Parallel Processing Letters, vol. 1, pp. 11-18, 1991.[12] B. Awerbuch and M. Sipser, “Dynamic Networks Are as Fast as Static Networks,” Proc. 29th Ann. Symp. Foundations of Computer Science (FOCS '88), pp. 206-220, Oct. 1988.[13] B. Awerbuch and G. Varghese, “Distributed Program Checking: A Paradigm for Building Self-Stabilizing Distributed Protocols,” Proc. 32nd Ann. Symp. Foundations of Computer Science (FOCS '91), pp. 258-267, Oct. 1991.[14] J.E. Burns and J. Pachl, “Uniform Self-Stabilizing Rings,” ACM Trans. Programming Languages and Systems, vol. 11, no. 2, pp. 330-344, 1989.[15] J.E. Burns, M.G. Gouda, and R.E. Miller, “On Relaxing Interleaving Assumptions,” Proc. MCC Workshop Self Stabilizing Systems, 1989.[16] C. Boulinier, F. Petit, and V. Villain, “When Graph Theory Helps Self-Stabilization,” Proc. 23rd ACM Ann. Symp. Principles of Distributed Computing (PODC '04), pp. 150-159, 2004.[17] S. Chandrasekar and P.K. Srimani, “A Self-Stabilizing Algorithm to Synchronize Digital Clocks in a Distributed System,” Computers and Electrical Eng., vol. 20, no. 6, pp. 439-444, 1994.[18] A. Ciuffoletti, “Self-Stabilizing Clock Synchronization in a Hierarchical Network,” Proc. Third Workshop Self-Stabilizing Systems, pp. 86-93, 1999.[19] E.W. Dijkstra, “Self Stabilization in Spite of Distributed Control,” Comm. ACM, vol. 17, pp. 643-644, 1974.[20] S. Dolev, “Possible and Impossible Self-Stabilizing Digital Clock Synchronization in General Graphs,” Real-Time Systems, vol. 12, pp. 95-107, 1997.[21] S. Dolev and T. Herman, “Superstabilizing Protocols for Dynamic Distributed Systems,” Chicago J. Theoretical Computer Science, 1997.[22] S. Dolev and T. Herman, “Parallel Composition of Stabilizing Algorithms,” Proc. Fourth Workshop Self-Stabilizing Systems (WSS' 99), pp. 25-32, 1999.[23] S. Dolev, A. Israeli, and S. Moran, “Uniform Dynamic Self-Stabilizing Leader Election,” IEEE Trans. Parallel and Distributed Systems, vol. 8, no. 4, pp. 424-440, Apr. 1997.[24] S. Dolev and J.L. Welch, “Wait-Free Clock Synchronization,” Algorithmica, vol. 18, no. 4, pp. 486-511, 1997.[25] S. Dolev and J.L. Welch, “Self-Stabilizing Clock Synchronization in the Presence of Byzantine Faults,” J. ACM, vol. 51, no. 5, pp. 780-799, 2004.[26] S. Even and S. Rajsbaum, “Unison, Canon, and Sluggish Clocks in Networks Controlled by a Synchronizer,” Math. Systems Theory, vol. 28, no. 5, pp. 421-435, 1995.[27] S. Finn, “Resynch Procedures and a Fail-Safe Network Protocol,” IEEE Trans. Comm., vol. 27, no. 6, pp. 840-845, June 1979.[28] J.-M. Couvreur, N. Francez, and M. Gouda, “Asynchronous Unison,” Proc. 12th Int'l Conf. Distributed Computing Systems (ICDCS '92), pp. 468-493, 1992.[29] T. Herman, “A Stabilizing Repair Timer,” Proc. 12th Int'l Symp. Distributed Computing (DISC '98), pp. 186-200, 1998.[30] T. Herman and S. Ghosh, “Stabilizing Phase Clocks,” Information Processing Letters, vol. 54, no. 5, pp. 259-265, June 1995.[31] M.G. Gouda and T. Herman, “Stabilizing Unison,” Information Processing Letters, vol. 35, pp. 171-175, 1990.[32] R. Guerraoui and M. Vukolic, “How Fast Can a Very Robust Read Be,” Proc. 25th ACM Ann. Symp. Principles of Distributed Computing (PODC '06), 2006.[33] S.T. Huang and T.J. Liu, “Four-State Stabilizing Phase Clock for Unidirectional Rings of Odd Size,” Information Processing Letters, vol. 65, no. 6, pp. 325-329, 1998.[34] S.T. Huang and T.J. Liu, “Self-Stabilizing 2(m)-Clock for Unidirectional Rings of Odd Size,” Distributed Computing, vol. 12, pp. 41-46, 1999.[35] S.-T. Huang, T.-J. Liu, and S.-S. Hung, “Asynchronous Phase Synchronization in Uniform Unidirectional Rings,” IEEE Trans. Parallel and Distributed Systems, vol. 15, no. 4, pp. 378-384, Apr. 2004.[36] S.S. Kulkarni and A. Arora, “Multitolerant Barrier Synchronization,” Information Processing Letters, vol. 64, no. 1, pp. 29-36, Oct. 1997.[37] S.S. Kulkarni and A. Arora, “Low-Cost Fault-Tolerance in Barrier Synchronizations,” Proc. Int'l Conf. Parallel Processing (ICPP '98), Aug. 1998.[38] L. Lamport, “Time, Clocks, and the Ordering of Events in a Distributed System,” Comm. ACM, vol. 21, no. 7, pp. 558-565, July 1978.[39] C. Lin and J. Simon, “Possibility and Impossibility Results for Self-Stabilizing Phase Clocks on Synchronous Rings,” Proc. Second Workshop Self-Stabilizing Systems, pp. 10.1-10.15, 1995.[40] J. Lundelius and N. Lynch, “An Upper and Lower Bound for Clock Synchronization,” Information and Computation, vol. 62, no. 2-3, pp. 190-204, 1984.[41] N. Lynch, Distributed Algorithms. Morgan Kaufmann, 1996.[42] D.L. Mills, “Network Time Protocol: Specification and Implementation (Version 1),” RFC-1059, DARPA Network Working Group, Univ. of Delaware, July 1988.[43] J. Misra, “Phase Synchronization,” Information Processing Letters, vol. 38, pp. 101-105, 1991.[44] S. Moriya, M. Inoue, T. Masuzawa, and H. Fujiwara, “SelfStabilizing WaitFree Clock Synchronization with Bounded Space,” Proc. Second Int'l Conf. Principles of Distributed Systems (OPODIS '98), pp. 129-144, 1998.[45] A.A. Nanavati, “A Simple Self-Stabilizing Reset Protocol,” Proc. ACM Symp. Applied Computing, pp. 93-97, 1996.[46] M. Papatriantafilou and P. Tsigas, “On Self-Stabilizing Wait-Free Clock Synchronization,” Parallel Processing Letters, vol. 7, no. 3, pp.321-328, 1997.[47] D. Peleg and J.D. Ullman, “An Optimal Synchronizer for the Hypercube,” SIAM J. Computing, vol. 18, no. 2, pp. 740-747, 1989.[48] J.M. Spinelli and R.G. Gallager, “Broadcasting Topology Information in Computer Networks,” IEEE Trans. Comm., May 1989.[49] G. Tel, Introduction to Distributed Algorithms, second ed. Cambridge Univ. Press, 2000.[50] G. Varghese, “Self-Stabilization by Local Checking and Correction,” PhD dissertation, Laboratory for Computer Science, Massachusetts Inst. of Tech nology, 1992.[51] G. Varghese, “Self-Stabilization by Counter Flushing,” SIAM J. Computing, vol. 30, no. 2, pp. 486-510, 2000.
Index Terms:
Computer Systems Organization, COMPUTER-COMMUNICATION NETWORKS, Distributed networks, Mathematics of Computing, DISCRETE MATHEMATICS , Graph Theory, Reliability, Theory
Citation:
Baruch Awerbuch, Shay Kutten, Yishay Mansour, Boaz Patt-Shamir, George Varghese, "A Time-Optimal Self-Stabilizing Synchronizer Using A Phase Clock," IEEE Transactions on Dependable and Secure Computing, vol. 4, no. 3, pp. 180-190, July-Sept. 2007, doi:10.1109/TDSC.2007.1007
