Self-stabilizing and self-orgenizing mobile networks

ABSTRACT

Self-stabilization ([Dij74], [Dolev00] is an important property of any dynamic long-lived system. Self-stabilizing systems may start operating in any arbitrary state, and can therefore recover following a temporary violation of the assumption made by the system designer. Mobile ad-hoc networks are very dynamic in nature and must cope with unreliable and sometimes unpredictable environments. Thus the design of self-stabilizing mobile and ad-hoc networks is of great importance. Self-stabilizing networks are self-organizing if they start to operate as they should in sub-linear time. We overview several recent works demonstrating several directions for creating adaptive infrastructures and abstractions; namely self-stabilizing and self-organizing infrastructures. These infrastructures fit the mobile ad-hoc network characteristic.

REFERENCES

• 1: The virtual infrastructure project. http://groups.csail.mit.edu/tds/vi-project.
• 2: Edsger W. Dijkstra, Self-stabilizing systems in spite of distributed control, Communications of the ACM, v.17 n.11, p.643-644, Nov. 1974 [doi>10.1145/361179.361202]
• 3: Shlomi Dolev, Self-stabilization, MIT Press, Cambridge, MA, 2000
• 4: Shlomi Dolev , Seth Gilbert , Rachid Guerraoui , Calvin Newport, Secure communication over radio channels, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada [doi>10.1145/1400751.1400767]
• 5: Shlomi Dolev , Seth Gilbert , Nancy A. Lynch , Alexander A. Shvartsman , Jennifer L. Welch, GeoQuorums: implementing atomic memory in mobile ad hoc networks, Distributed Computing, v.18 n.2, p.125-155, December 2005 [doi>10.1007/s00446-005-0140-9]
• 6: Shlomi Dolev , Seth Gilbert , Elad Schiller , Alex A. Shvartsman , Jennifer Welch, Autonomous virtual mobile nodes, Proceedings of the 2005 joint workshop on Foundations of mobile computing, September 02-02, 2005, Cologne, Germany [doi>10.1145/1080810.1080821]
• 7: Dolev, S., Herman, T., and Lahiani, L. Polygonal broadcast, secret maturity, and the firing sensors. Ad Hoc Networks 4, 4 (2006), 447--486.
• 8: Dolev, S., Lahiani, L., and Yung, M. Secret swarm unitreactive k-secret sharing. In INDOCRYPT (2007), pp. 123--137.
• 9: Shlomi Dolev , Elad Schiller , Jennifer L. Welch, Random Walk for Self-Stabilizing Group Communication in Ad Hoc Networks, IEEE Transactions on Mobile Computing, v.5 n.7, p.893-905, July 2006 [doi>10.1109/TMC.2006.104]
• 10: Dolev, S., and Tzachar, N. Empire of colonies: Self-stabilizing and self-organizing distributed algorithms. In OPODIS (2006), pp. 230--243.
• 11: Dolev, S., and Tzachar, N. Spanders: Distributed spanning expanders. In Dept. of Computer Science, Ben-Gurion University, TR-08-02 (2007).

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

Additional Classification:
  F. Theory of Computation
  F.0 GENERAL

General Terms:
Algorithms

Keywords:
mobile ad-hoc networks, self-organization, self-stabilization, swarm