Abstract
Self-stabilizing protocols can tolerate any type and any number of transient faults. But self-stabilizing protocols have no guarantee of their behavior against permanent faults. Thus, investigation concerning self-stabilizing protocols resilient to permanent faults is important.
This paper proposes a self-stabilizing link-coloring protocol resilient to (permanent) Byzantine faults in tree networks. The protocol assumes the central daemon, and uses Δ + 1 colors where Δ is the maximum degree in the network. This protocol guarantees that, for any nonfaulty process v, if the distance from v to any Byzantine ancestor of v is greater than two, v reaches its desired states within three rounds and never changes its states after that. Thus, it achieves fault containment with radius of two. Moreover, we prove that the containment radius becomes Ω(log n) when we use only Δ colors, and prove that the containment radius becomes Ω(n) under the distributed daemon. These lower bound results prove necessity of Δ + 1 colors and the central daemon to achieve fault containment with a constant radius.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Anagnostou, E., Hadzilacos, V.: Tolerating transient and permanent failures. In: Schiper, A. (ed.) WDAG 1993. LNCS, vol. 725, pp. 174–188. Springer, Heidelberg (1993)
Arora, A., Zhang, H.: Lsrp: Local stabilization in shortest path routing. In: Proceedings of the 2003 International Conference on Dependable Systems and Networks, pp. 139–148 (2003)
Beauquier, J., Kekkonen-Moneta, S.: Fault-tolerance and self-stabilization: impossibility results and solutions using self-stabiling failure detectors. International Journal of Systems Science 28(11), 1177–1187 (1997)
Beauquier, J., Kekkonen-Moneta, S.: On ftss-solvable distributed problems. In: Proceedings of the 6th Annual ACM Symposium on Principles of Distributed Computing, p. 290 (1997)
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.: Self-Stabilization. MIT Press, Cambridge (2000)
Ghosh, S., Gupta, A.: An exercise in fault-containment: self-stabilizing leader election. Information Processing Letters 59(5), 281–288 (1996)
Ghosh, S., Gupta, A., Herman, T., Pemmaraju, S.V.: Fault-containing self-stabilizing algorithms. In: Proceedings of the 15th Annual ACM Symposium on Principles of Distributed Computing, pp. 45–54 (1996)
Ghosh, S., Pemmaraju, S.V.: Tradeoffs in fault-containing self-stabilization. In: Proceedings of the 3rd Workshop on Self-Stabilizing Systems, pp. 157–169 (1997)
Gopal, A.S., Perry, K.J.: Unifying self-stabilization and fault-tolerance. In: Proceedings of the 12th Annual ACM Symposium on Principles of Distributed Computing, pp. 195–206 (1993)
Grable, D.A., Panconesi, A.: Nearly optimal distributed edge colouring in o(log log n) rounds. In: Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 278–285 (1997)
Katayama, Y., Masuzawa, T.: A fault-containing self-stabilizing protocol for constructing a minimum spanning tree. IEICE Transactions J84-D-I(9), 1307–1317 (2001)
Kutten, S., Patt-Shamir, B.: Stabilizing time-adaptive protocols. Theoretical Computer Science 220(1), 93–111 (1999)
Marathe, M.V., Panconesi, A., Risinger, L.D.: An experimental study of a simple, distributed edge coloring algorithm. In: Proceedings of the 12th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 166–175 (2000)
Masuzawa, T.: A fault-tolerant and self-stabilizing protocol for the topology problem. In: Proceedings of the 2nd Workshop on Self-Stabilizing Systems, pp. 1.1–1.15 (1995)
Matsui, H., Inoue, M., Masuzawa, T., Fujiwara, H.: Fault-tolerant and self-stabilizing protocols using an unreliable failure detector. IEICE Transactions on Information and Systems E83-D(10), 1831–1840 (2000)
Nesterenko, M., Arora, A.: Tolerance to unbounded byzantine faults. In: Proceedings of 21st IEEE Symposium on Reliable Distributed Systems, pp. 22–29 (2002)
Panconesi, A., Srinivasan, A.: Fast randomized algorithms for distributed edge coloring. In: Proceedings of the 11th Annual ACM Symposium on Principles of Distributed Computing, pp. 251–262 (1992)
Ukena, S., Katayama, Y., Masuzawa, T., Fujiwara, H.: A self-stabilizing spanning tree protocol that tolerates non-quiescent permanent faults. IEICE Transaction J85-D-I(11), 1007–1014 (2002)
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
Sakurai, Y., Ooshita, F., Masuzawa, T. (2005). A Self-stabilizing Link-Coloring Protocol Resilient to Byzantine Faults in Tree Networks. In: Higashino, T. (eds) Principles of Distributed Systems. OPODIS 2004. Lecture Notes in Computer Science, vol 3544. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11516798_21
Download citation
DOI: https://doi.org/10.1007/11516798_21
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-27324-0
Online ISBN: 978-3-540-31584-1
eBook Packages: Computer ScienceComputer Science (R0)