[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Empire of Colonies Self-stabilizing and Self-organizing Distributed Algorithms

Extended Abstract

  • Conference paper
Principles of Distributed Systems (OPODIS 2006)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 4305))

Included in the following conference series:

Abstract

Self-stabilization ensures automatic recovery from an arbitrary state; we define self-organization as a property of algorithms which display local attributes. More precisely, we say that an algorithm is self-organizing if (1) it converges in sublinear time and (2) reacts “fast” to topology changes. If s(n) is an upper bound on the convergence time and d(n) is an upper bound on the convergence time following a topology change, then s(n) ∈o(n) and d(n) ∈o(s(n)). The self-organization property can then be used for gaining, in sub-linear time, global properties and reaction to changes. We present self-stabilizing and self-organizing algorithms for many distributed algorithms, including distributed snapshot and leader election.

We present a new randomized self-stabilizing distributed algorithm for cluster definition in communication graphs of bounded degree processors. These graphs reflect sensor networks deployment. The algorithm converges in O(logn) expected number of rounds, handles dynamic changes locally and is, therefore, self-organizing. Applying the clustering algorithm to specific classes of communication graphs, in O(logn) levels, using an overlay network abstraction, results in a self-stabilizing and self-organizing distributed algorithm for hierarchy definition.

Given the obtained hierarchy definition, we present an algorithm for hierarchical distributed snapshot. The algorithms are based on a new basic snap-stabilizing snapshot algorithm, designed for message passing systems in which a distributed spanning tree is defined and in which processors communicate using bounded links capacity. The combination of the self-stabilizing and self-organizing distributed hierarchy construction and the snapshot algorithm form an efficient self-stabilizer transformer. Given a distributed algorithm for a specific task, we are able to convert the algorithm into a self-stabilizing algorithm for the same task with an expected convergence time of O(log2 n) rounds.

Partially supported by IBM, Israeli ministry of science, Deutsche Telekom, Rita Altura Trust Chair in Computer Sciences, Israeli Grid Consortium and the Lynn and William Frankel Center for Computer Sciences.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Afek, Y., and Dolev, S., “Local Stabilizer,” Journal of Parallel and Distributed Computing, special issue on self-stabilizing distributed systems, Vol. 62, No. 5, pp. 745-765 (May 2002). Also in Proc. of the 5th Israeli Symposium on Theory of Computing and Systems, (ISTCS 1997), pp. 74-84, 1997.

    MATH  Google Scholar 

  2. Anceaume, E., Défago, X., Gradinariu, M., Roy, M.: Towards a theory of self-organization. In: Anderson, J.H., Prencipe, G., Wattenhofer, R. (eds.) OPODIS 2005. LNCS, vol. 3974, pp. 191–205. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  3. Bui, A., Datta, A.K., Petit, F., Villain, V.: State-optimal snap-stabilizing PIF in tree networks. In: Proceedings of the Third Workshop on Self-Stabilizing Systems, pp. 78–85 (1999)

    Google Scholar 

  4. Burman, J., Kutten, S., Herman, T., Patt-Shamir, B.: Asynchronous and Fully Self-Stabilizing Time-Adaptive Majority Consensus. In: 9th International Conference on Principels of Distributed Systems, OPODIS (2005)

    Google Scholar 

  5. Chandy, M., Lamport, L.: Distributed snapshots: determining global states of distributed systems. ACM Transactions on Computing Systems 3(1), 63–75 (1985)

    Article  Google Scholar 

  6. Tanenbaum, A.: Computer Networking, 4th edn. Prentice Hall, Englewood Cliffs (2002)

    Google Scholar 

  7. Cournier, A., Datta, A., Petit, F., Villain, V.,: Enabling snap-stabilization. In: Proc. of the 23rd International Conference on Distributed Computing Systems, pp. 12–19 (2003)

    Google Scholar 

  8. Demirbas, M., Arora, A., Mittal, V.: FLOC: A fast local clustering service for wireless sensor networks. In: Workshop on Dependability Issues in Wireless Ad Hoc Networks and Sensor Networks (DIWNAS/DSN) (2004)

    Google Scholar 

  9. Dijkstra, E.W.: Self-stabilizing systems in spite of distributed control. Communications of the ACM 17(11), 643–644 (1974)

    Article  MATH  Google Scholar 

  10. Dolev, S.: Optimal Time Self-Stabilization in Uniform Dynamic Systems. Parallel Processing Letters 8(1), 7–18 (1998)

    Article  MathSciNet  Google Scholar 

  11. Dolev, S.: Self-stabilization. MIT Press, Cambridge (2000)

    MATH  Google Scholar 

  12. Dolev, S., Herman, T.: SuperStabilizing Protocols for Dynamic Distributed Systems. In: Proc. of the 2nd Workshop on Self-Stabilizing Systems (May 1995); Chicago Journal of Theoretical Computer Science, 3(4) special issue on self-stabilization (1997)

    Google Scholar 

  13. Dolev, S., Kranakis, E., Krizanc, D., Peleg, D.: Bubbles: Adaptive Routing Scheme for High-Speed Dynamic Networks. SIAM Journal on Computing 29(3), 804–833 (1999); Also in Proc. of the 27th ACM Symposium on Theory of Computing (STOC 1995) pp. 528–537 (1995)

    Article  MathSciNet  Google Scholar 

  14. Dolev, S., Tzachar, N.: Colonies: Self-Stabilizing and Self-Organizing Distributed Algorithms, Technical report #06–01, Ben Gurion University of the Negev (October 2005), http://www.cs.bgu.ac.il/tzachar/papers/tech0601.pdf

  15. Gärtner, F.C., Pagnia, H.: Time-Efficient Self-Stabilizing Algorithms through Hierarchical Structures. In: Proc. to the Sixth Symposium on Self-Stabilizing Systems, pp. 154–168 (2003)

    Google Scholar 

  16. Ghosh, S., Gupta, A., Herman, T., Pemmaraju, S.: Fault-Containing Self-Stabilizing Algorithms. In: PODC 1996, pp. 45–54 (1996)

    Google Scholar 

  17. Henzinger, M., King, V.: Randomized Fully Dynamic Graph Algorithms with Polylogrithmic Time per Operation. Journal of the ACM 46(4), 502–516 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  18. Katz, S., Perry, K.: Self-stabilizing extensions for message-passing systems. In: Proceedings of the ninth annual ACM symposium on Principles of distributed computing, pp. 91–101 (1990)

    Google Scholar 

  19. Kirschenhofer, P., Prodinger, H.: A Result in Order Statistics Related to Probabilistic Counting. Computing 46, 15–27

    Google Scholar 

  20. Kutten, S., Peleg, D.: Tight Fault Locality. In: Annual Symposium on Foundations of Computer Science (FOCS) (1995)

    Google Scholar 

  21. Kuhn, F., Moscibroda, T., Wattenhofer, R.: What cannot be computed locally! In: Proceedings of the 23rd ACM Symposium on Principles of Distributed Computing (PODC), pp. 300–309 (2004)

    Google Scholar 

  22. Lamport, L.: Time, clocks, and the ordering of events in a distributed system. Communications of the ACM 12(7), 558–565 (1978)

    Article  Google Scholar 

  23. Linial, N., London, E., Rabinovich, Y.: The Geometry of Graphs and Some of its Algorithmic Applications. In: Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, pp. 577–591 (October 1994)

    Google Scholar 

  24. Luby, M.: A Simple Parallel Algorithm for the Maximal Independent Set Proble. SIAM journal of Computing 15(4), 1036–1053 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  25. Moscibroda, T., Wattenhofer, R.: Efficient Computation of Maximal Independent Sets in Unstructured Multi-Hop Radio Networks. In: The 1st IEEE International Conference on Mobile Ad-hoc and Sensor Systems, Fort Lauderdale, Florida (2004)

    Google Scholar 

  26. Plaxton, C.G., Rajaraman, R., Richa, A.W.: Accessing nearby copies of replicated objects in a distributed environment. In: Proceedings of the Ninth Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 311–320. ACM Press, New York (1997)

    Chapter  Google Scholar 

  27. Varghese, G.: Self-stabilization by counter flushing. SIAM Journal on Computing 30(2), 486–510 (2000) ; Also in, Symposium on Principles of Distributed Computing, pp. 244-253, 1994

    Article  MATH  MathSciNet  Google Scholar 

  28. Zhang, H., Arora, A.: GS3: Scalable Self-configuration and Self-healing in Wireless Networks. In: Symposium on Principles of Distributed Computing, pp. 58–67 (2002)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Ben-Gurion University of the Negev, Israel

    Shlomi Dolev & Nir Tzachar

Authors
  1. Shlomi Dolev
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Nir Tzachar
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Computer Science and Artificial Intelligence Laboratory, MIT, USA

    Mariam Momenzadeh Alexander A. Shvartsman

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Dolev, S., Tzachar, N. (2006). Empire of Colonies Self-stabilizing and Self-organizing Distributed Algorithms. In: Shvartsman, M.M.A.A. (eds) Principles of Distributed Systems. OPODIS 2006. Lecture Notes in Computer Science, vol 4305. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11945529_17

Download citation

  • DOI: https://doi.org/10.1007/11945529_17

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-49990-9

  • Online ISBN: 978-3-540-49991-6

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation