Abstract
A snap-stabilizing protocol, starting from any arbitrary initial configuration, always behaves according to its specification. In [4], we presented the first snap-stabilizing depth-first search (DFS) wave protocol for arbitrary rooted networks working under an unfair daemon. However, this protocol needs O(N N) states per processors (where N is the number of processors) and needs ids on processors. In this paper, we propose an original snap-stabilizing solution for this problem with a strongly enhanced space complexity, i.e., O(Δ2 × N) states where Δ is the degree of the network. Furthermore, this new protocol does not need a completely identified network: only the root needs to be identified, i.e., the network is semi-anonymous.
A full version of this paper is available at www.laria.u-picardie.fr/~devismes/tr2005-05.pdf
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Blin, L., Cournier, A., Villain, V.: An improved snap-stabilizing PIF algorithm. In: Huang, S.-T., Herman, T. (eds.) SSS 2003. LNCS, vol. 2704, pp. 199–214. Springer, Heidelberg (2003)
Bui, A., Datta, A.K., Petit, F., Villain, V.: State-optimal snap-stabilizing PIF in tree networks. In: Proceedings of the Fourth Workshop on Self-Stabilizing Systems, Austin, Texas, USA, pp. 78–85. IEEE Computer Society Press, Los Alamitos (1999)
Cournier, A., Datta, A.K., Petit, F., Villain, V.: Enabling snap-stabilization. In: 23th International Conference on Distributed Computing Systems (ICDCS 2003), Providence, Rhode Island USA, pp. 12–19. IEEE Computer Society Press, Los Alamitos (2003)
Cournier, A., Devismes, S., Petit, F., Villain, V.: Snap-stabilizing depth-first search on arbitrary networks. In: Higashino, T. (ed.) OPODIS 2004. LNCS, vol. 3544, pp. 267–282. Springer, Heidelberg (2005)
Cournier, A., Devismes, S., Villain, V.: A snap-stabilizing dfs with a lower space requirement. Technical Report 2005-05, LaRIA, CNRS FRE 2733 (2004)
Datta, A.K., Johnen, C., Petit, F., Villain, V.: Self-stabilizing depth-first token circulation in arbitrary rooted networks. Distributed Computing 13(4), 207–218 (2000)
Dijkstra, E.W.: Self stabilizing systems in spite of distributed control. Communications of the Association of the Computing Machinery 17, 643–644 (1974)
Dolev, S., Israeli, A., Moran, S.: Uniform dynamic self-stabilizing leader election. IEEE Transactions on Parallel and Distributed Systems 8(4), 424–440 (1997)
Huang, S.T., Chen, N.S.: Self-stabilizing depth-first token circulation on networks. Distributed Computing 7, 61–66 (1993)
Johnen, C., Alari, C., Beauquier, J., Datta, A.K.: Self-stabilizing depth-first token passing on rooted networks. In: Mavronicolas, M. (ed.) WDAG 1997. LNCS, vol. 1320, pp. 260–274. Springer, Heidelberg (1997)
Johnen, C., Beauquier, J.: Space-efficient distributed self-stabilizing depth-first token circulation. In: Proceedings of the Second Workshop on Self-Stabilizing Systems, Las Vegas (UNLV), USA, May 28-29, pp. 4.1–4.15 (1995); Chicago Journal of Theoretical Computer Science (1995)
Petit, F., Villain, V.: Time and space optimality of distributed depth-first token circulation algorithms. In: Proceedings of DIMACS Workshop on Distributed Data and Structures, Princeton, USA, pp. 91–106. Carleton University Press, Ottawa (1999)
Tel, G.: Introduction to distributed algorithms, 2nd edn. Cambridge University Press, Cambridge (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cournier, A., Devismes, S., Villain, V. (2005). A Snap-Stabilizing DFS with a Lower Space Requirement. In: Tixeuil, S., Herman, T. (eds) Self-Stabilizing Systems. SSS 2005. Lecture Notes in Computer Science, vol 3764. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11577327_3
Download citation
DOI: https://doi.org/10.1007/11577327_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29814-4
Online ISBN: 978-3-540-32123-1
eBook Packages: Computer ScienceComputer Science (R0)