Abstract
In this research, we present the first time-optimal self stabilizing algorithm for synchronous distributed spanning tree construction, assuming the standard shared registers size (O(logn) bits, where n stands for the number of processes in the system), or, similarly, standard message size. Previous algorithms with O(diameter) stabilization time complexity assumed that a larger message can be sent through each link in one time unit. Hence, when assuming the standard message size, the time complexity of previous algorithms was not O(diameter). The current algorithm stabilizes in O(diameter) time without having previous knowledge of the network size or diameter. The only assumption we make is that we have some polynomial (possibly very large) given upper bound on the network size. However, the time complexity of the algorithm does not depend on that upper bound. Using our results, most known distributed global tasks, such as distributed reset, can be performed in a relatively easy way and in optimal time. As a building block, we present a new self stabilizing silent phase clock algorithm for synchronous networks (based on a known non-silent algorithm). It is optimal in time too. We believe it may be an interesting contribution by itself.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Afek, Y., Bremler-Barr, A.: Self-stabilizing unidirectional network algorithms by power supply. Chicago J. Theor. Comput. Sci. (1998)
Afek, Y., Kutten, S., Yung, M.: Memory-efficient self stabilizing protocols for general networks. In: van Leeuwen, J., Santoro, N. (eds.) WDAG 1990. LNCS, vol. 486, pp. 15–28. Springer, Heidelberg (1991)
Afek, Y., Kutten, S., Yung, M.: The local detection paradigm and its application to self-stabilization. Theor. Comput. Sci., 199–229 (1997)
Aggarwal, S., Kutten, S.: Time optimal self-stabilizing spanning tree algorithms. In: Shyamasundar, R.K. (ed.) FSTTCS 1993. LNCS, vol. 761, pp. 400–410. Springer, Heidelberg (1993)
Arora, A., Gouda, M.G.: Distributed reset. In: Veni Madhavan, C.E., Nori, K.V. (eds.) FSTTCS 1990. LNCS, vol. 472, pp. 316–331. Springer, Heidelberg (1990)
Awerbuch, B.: Complexity of network synchronization. J. ACM 32(4), 804–823 (1985)
Awerbuch, B., Cidon, I., Kutten, S.: Optimal maintenance of a spanning tree. J. ACM 55(4) (2008)
Awerbuch, B., Kutten, S., Mansour, Y., Patt-Shamir, B., Varghese, G.: A time-optimal self-stabilizing synchronizer using a phase clock. IEEE Trans. Dependable Sec. Comput. 4(3), 180–190 (2007)
Awerbuch, B., Mansour, Y., Kutten, S., Patt-Shamir, B., Varghese, G.: Time optimal self-stabilizing synchronization. In: STOC, pp. 652–661 (1993)
Awerbuch, B., Patt-Shamir, B., Varghese, G.: Self-stabilization by local checking and correction. In: FOCS, pp. 268–277 (1991)
Boulinier, C., Petit, F., Villain, V.: When graph theory helps self-stabilization. In: PODC, pp. 150–159 (2004)
Burman, J., Kutten, S.: Time optimal asynchronous self-stabilizing spanning tree. In: Pelc, A. (ed.) DISC 2007. LNCS, vol. 4731, pp. 92–107. Springer, Heidelberg (2007)
Petit, F., Boulinier, C., Villain, V.: Synchronous vs. asynchronous unison. Algoritmica 51(1), 61–80 (2008)
Chen, N.-S., Yu, H.-P., Huang, S.-T.: A self-stabilizing algorithm for constructing spanning trees. Inf. Process. Lett., 147–151 (1991)
Cournier, A.: A new polynomial silent stabilizing spanning-tree construction algorithm, 141–153 (2009)
Datta, A.K., Larmore, L.L., Piniganti, H.: Self-stabilizing leader election in dynamic networks. In: Dolev, S., Cobb, J., Fischer, M., Yung, M. (eds.) SSS 2010. LNCS, vol. 6366, pp. 35–49. Springer, Heidelberg (2010)
Datta, A.K., Larmore, L.L., Vemula, P.: An o(n)-time self-stabilizing leader election algorithm. J. Parallel Distrib. Comput. 71(11), 1532–1544 (2011)
Dijkstra, E.W.: Self stabilization in spite of distributed control. Comm. ACM 17, 167–180 (1974)
Dolev, D., Shavit, N.: Bounded concurrent time-stamping. SIAM J. Comput., 418–455 (1997)
Dolev, S., Israeli, A., Moran, S.: Self-stabilization of dynamic systems assuming only read/write atomicity. In: PODC, pp. 103–117 (1990)
Dubois, S., Guerraoui, R.: Introducing speculation in self-stabilization: an application to mutual exclusion. In: PODC, pp. 290–298 (2013)
Gallager, R.G., Humblet, P.A., Spira, P.M.: A distributed algorithm for minimum-weight spanning trees. ACM Trans. Program. Lang. Syst. 5(1), 66–77 (1983)
Gosh, S., Gupta, A., Pemmaraju, S.V.: A fault containing self stabilizing algorithm for spanning trees. Journal of Computing and Information 2, 322–338 (1996)
Gouda, M.G., Herman, T.: Stabilizing unison. Inf. Process. Lett. 35(4), 171–175 (1990)
Herman, T., Ghosh, S.: Stabilizing phase-clocks. Inf. Process. Lett. 54(5), 259–265 (1995)
Kurose, J.F., Ross, K.W.: Computer Networking: A Top-Down Approach, 2nd edn. Addison Wesley (2003)
Kutten, S., Porat, A.: Maintenance of a spanning tree in dynamic networks. In: Jayanti, P. (ed.) DISC 1999. LNCS, vol. 1693, pp. 342–355. Springer, Heidelberg (1999)
Matias, Y., Afek, Y.: Simple and efficient election algorithms for anonymous networks. In: Bermond, J.-C., Raynal, M. (eds.) WDAG 1989. LNCS, vol. 392, pp. 183–194. Springer, Heidelberg (1989)
Peleg, D.: Distributed computing: a locality-sensitive approach. Society for Industrial and Applied Mathematics (2000)
Perlman, R.J.: Fault-tolerant broadcast of routing information. Computer Networks 7, 395–405 (1983)
Dolev, S., Israeli, A., Moran, S.: Uniform dynamic self-stabilizing leader election. In: Toueg, S., Kirousis, L.M., Spirakis, P.G. (eds.) WDAG 1991. LNCS, vol. 579, pp. 167–180. Springer, Heidelberg (1992)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kravchik, A., Kutten, S. (2013). Time Optimal Synchronous Self Stabilizing Spanning Tree. In: Afek, Y. (eds) Distributed Computing. DISC 2013. Lecture Notes in Computer Science, vol 8205. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-41527-2_7
Download citation
DOI: https://doi.org/10.1007/978-3-642-41527-2_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-41526-5
Online ISBN: 978-3-642-41527-2
eBook Packages: Computer ScienceComputer Science (R0)