Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Composition and Scaling Challenges in Sensor Networks: An Interaction-Centric View Kapitel lesen Erstes Kapitel lesen

2011 | OriginalPaper | Buchkapitel

20. Self-Stabilizing and Self-Organizing Virtual Infrastructures for Mobile Networks

verfasst von : Shlomi Dolev, Nir Tzachar

Erschienen in: Theoretical Aspects of Distributed Computing in Sensor Networks

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Self-stabilizing algorithms can be started in any arbitrary state to exhibit a desired behavior following a convergence period. The class of self-organizing distributed algorithms is regarded here as a subclass of the self-stabilizing class of algorithms, where convergence is sub-linear in the size of the system and local perturbation of state is handled locally converging faster than the convergence from an arbitrary state. The chapter starts with a short overview of several virtual infrastructures and fitting self-stabilizing and self-organizing techniques:
  • Group communication by random walks [23]
  • Polygon-based stateless infrastructure [19]
  • Geographic quorum systems [1, 16]
  • Autonomous virtual node [18]
  • Secret swarm units [20]
  • Spanners, spanning expanders
The last design, which is based on expanders and short random walks, is described in detail.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Information Spreading in Dynamic Networks: An Analytical Approach
Nächstes Kapitel Computing by Mobile Robotic Sensors
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
We use the term “overwhelming probability” to denote a probability approaching 1 at least linearly with the size of the problem. For example, for a given n, \(1-\dfrac{1}{n}\) is an overwhelming probability.
 
2
An expander is considered “good” if it has a constant expansion parameter.
 
Literatur
1.
2.
I. Abraham, and D. Malkhi. Probabilistic quorums for dynamic systems. Distributed Computing 18, 2:113–124, (2005).CrossRef
3.
N. Alon, C. Avin, M. Koucký, G. Kozma, Z. Lotker, and M. R. Tuttle. Many random walks are faster than one. In SPAA 2008: Proceedings of the 20th Annual ACM Symposium on Parallel Algorithms and Architectures, Munich, Germany, June 14–16, 2008 F. M. auf der Heide and N. Shavit(Eds.,) ACM, pages 119–128, (2008).
4.
A. Arora, S. Dolev, and M. Gouda. Maintaining digital clocks in step. Parallel Processing Letters 1, 1:11–18, (1991).CrossRef
5.
B. Awerbuch, and G. Varghese. Distributed program checking: a paradigm for building self-stabilizing distributed protocols (Extended Abstract). In: Annual Symposium on Foundations of Computer Science (FOCS), San Juan, pages 258–267, 1991.
6.
7.
A. Cournier, S. Devismes, and V. Villain. Light enabling snap-stabilization of fundamental protocols. ACM Transactions on Autonomous and Adaptive Systems, 4(1):27, 2009.CrossRef
8.
A. Czumaj, and C. Sohler. Testing expansion in bounded-degree graphs. In FOCS (2007), IEEE Computer Society, pages. 570–578.
9.
E. W. Dijkstra. Self-stabilizing systems in spite of distributed control. Communications ACM 17, 11 643–644, 1974.CrossRef
10.
S. Dolev. Self-Stabilization. MIT Press, Cambridge, MA, 2000.MATH
11.
S. Dolev, J.A. Garay, N. Gilboa, and V. Kolesnikov. In: 47th Annual Allerton Conference on Communication, Control, and Computing, Monticello, IL, pages 1438–1445, 2009. Also brief Announcement in ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), pages 231–232, 2010.
12.
S. Dolev, J. Garay, N. Gilboa, and V. Kolesnikov. Secret sharing Krohn-Rhodes: Private and perennial distributed computation. In: Innovations in Computer Science (ICS), Beijing, China, January 2011.
13.
S. Dolev, S. Gilbert, R. Guerraoui, F. Kuhn, and C. C. Newport. The wireless synchronization problem. In: ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), Portland, pages 190–199, 2009.
14.
S. Dolev, S. Gilbert, R. Guerraoui, and C. C. Newport. Gossiping in a multi-channel radio network. In: International Symposium on Distributed Computing (DISC). Workshop on Distributed Algorithms (WDAG), pages 208–222, 2007.
15.
S. Dolev, S. Gilbert, R. Guerraoui, and C. C. Newport. Secure communication over radio channels. In: ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), Napoli, Italy, pages 105–114, 2008.
16.
S. Dolev, S. Gilbert, N. A. Lynch, A. A. Shvartsman, and J. L. Welch. GeoQuorums: Implementing atomic memory in mobile ad hoc networks, Distributed Computing 18 2:125–155, 2005.CrossRef
17.
S. Dolev, S. Gilbert, L. Lynch, E. Schiller, A. A. Shvartsman, and J. L. Welch. Virtual mobile nodes for mobile Ad Hoc networks, In: International Conference on Principles of DIStributed Computing, (DISC 2007), pages 230–244.
18.
S. Dolev, S. Gilbert, E. Schiller, A. A. Shvartsman, and J. L. Welch. Autonomous virtual mobile nodes, In DIALM-POMC (2005), pages 62–69.
19.
S. Dolev, T. Herman, and L. Lahiani. Polygonal broadcast, secret maturity, and the firing sensors, Ad Hoc Networks, 4:447–486, 2006.CrossRef
20.
S. Dolev, L. Lahiani, and M. Yung. Secret swarm unitreactive k-secret sharing, In INDOCRYPT, pages 123–137, 2007.
21.
S. Dolev, K. D. Pradhan, and J. L. Welch. Modified tree structure for location management in mobile environments, Computer Communication 19(4):335–345, 1996.CrossRef
22.
S. Dolev, M. Segal, H. Shpungin. Stretchable topology control, bounded-hop strong connectivity for flocking Swarms, 2009.
23.
S. Dolev, E. Schiller, and J. L. Welch. Random walk for self-stabilizing group communication in ad hoc networks, IEEE Transactions Mobile Computing 5, (7):893–905, 2006.
24.
S. Dolev, and N. Tzachar. Empire of colonies: Self-stabilizing and self-organizing distributed algorithms, Theoretical Computer Science, Volume 410 (6–7) pages 514–532, Special issue of OPODIS06, 2009.MATHCrossRefMathSciNet
25.
S. Dolev and N. Tzachar. Spanders: Distributed spanning expanders. In: Proceedings of the 25th ACM Symposium on Applied Computing (SAC-SCS), Nagoya, Japan, pages 1309–1314, 2010.
26.
S. Dolev, and N. Tzachar. SPANDERS: Distributed spanning expanders. TR 08-02, Department of Computer Science, Ben-Gurion University of the Negev, 2007.
27.
O. Goldreich, and D. Ron. On testing expansion in bounded-degree graphs. Electronic Colloquium on Computational Complexity (ECCC) 7:(20), 2000.
28.
S. Hoory, N. Linial, and A. Wigderson. Expander graphs and their applications, Bulletin of the AMS, volume 43, 4:439–561, 2006.CrossRefMathSciNet
29.
S. Kale, and C. Seshadrhi. Testing expansion in bounded degree graphs. ECCC report TR07–076, 2007.
30.
L. Lamport. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM 21, (7):558–565, 1978.
31.
C. Law, and K.-Y. Siu. Distributed construction of random expander networks. In: INFOCOM, 2003.
32.
L. Lovasz. Random walks on graphs: A survey.
33.
R. Motwani, and P. Raghavan. Randomized Algorithms. Cambridge university press, Cambridge, 2006.
34.
A. Nachmias, and A. Shapira. “Testing the expansion of graphs”. ECCC report TR07–118, 2007.
35.
M.K. Reiter, A. Samar, and C. Wang. Distributed construction of a fault-tolerant network from a tree. In: SRDS 05: Proceedings of the 24th IEEE Symposium on Reliable Distributed Systems, IEEE Computer Society, Washington, DC, USA, pages 155–165, 2005.
36.
S. A. Wright. “Registration of mobile packet data terminals after disaster,”, US Patent 6157633, 1996.
Metadaten
Titel
Self-Stabilizing and Self-Organizing Virtual Infrastructures for Mobile Networks
verfasst von
Shlomi Dolev
Nir Tzachar
Copyright-Jahr
2011
Verlag
Springer Berlin Heidelberg
Buch
Theoretical Aspects of Distributed Computing in Sensor Networks

Print ISBN: 978-3-642-14848-4

Electronic ISBN: 978-3-642-14849-1

Copyright-Jahr: 2011

DOI
https://doi.org/10.1007/978-3-642-14849-1_20