• search hit 8 of 33
Back to Result List

Harnessing Complex Structures and Collective Dynamics in Large Networked Computing Systems

Nutzung komplexer Strukturen und kollektiver Dynamik in großen, vernetzten Rechnersystemen

  • We are living in a connected world, surrounded by interwoven technical systems. Since they pervade more and more aspects of our everyday lives, a thorough understanding of the structure and dynamics of these systems is becoming increasingly important. However - rather than being blueprinted and constructed at the drawing board - many technical infrastructures like for example the Internet's global router network, the World Wide Web, large scale Peer-to-Peer systems or the power grid - evolve in a distributed fashion, beyond the control of a central instance and influenced by various surrounding conditions and interdependencies. Hence, due to this increase in complexity, making statements about the structure and behavior of tomorrow's networked systems is becoming increasingly complicated. A number of failures has shown that complex structures can emerge unintentionally that resemble those which can be observed in biological, physical and social systems. In this dissertation, we investigate how such complex phenomena can be controlled and actively used. For this, we review methodologies stemming from the field of random and complex networks, which are being used for the study of natural, social and technical systems, thus delivering insights into their structure and dynamics. A particularly interesting finding is the fact that the efficiency, dependability and adaptivity of natural systems can be related to rather simple local interactions between a large number of elements. We review a number of interesting findings about the formation of complex structures and collective dynamics and investigate how these are applicable in the design and operation of large scale networked computing systems. A particular focus of this dissertation are applications of principles and methods stemming from the study of complex networks in distributed computing systems that are based on overlay networks. Here we argue how the fact that the (virtual) connectivity in such systems is alterable and widely independent from physical limitations facilitates a design that is based on analogies between complex network structures and phenomena studied in statistical physics. Based on results about the properties of scale-free networks, we present a simple membership protocol by which scale-free overlay networks with adjustable degree distribution exponent can be created in a distributed fashion. With this protocol we further exemplify how phase transition phenomena - as occurring frequently in the domain of statistical physics - can actively be used to quickly adapt macroscopic statistical network parameters which are known to massively influence the stability and performance of networked systems. In the case considered in this dissertation, the adaptation of the degree distribution exponent of a random, scale-free overlay allows - within critical regions - a change of relevant structural and dynamical properties. As such, the proposed scheme allows to make sound statements about the relation between the local behavior of individual nodes and large scale properties of the resulting complex network structures. For systems in which the degree distribution exponent cannot easily be derived for example from local protocol parameters, we further present a distributed, probabilistic mechanism which can be used to monitor a network's degree distribution exponent and thus to reason about important structural qualities. Finally, the dissertation shifts its focus towards the study of complex, non-linear dynamics in networked systems. We consider a message-based protocol which - based on the Kuramoto model for coupled oscillators - achieves a stable, global synchronization of periodic heartbeat events. The protocol's performance and stability is evaluated in different network topologies. We further argue that - based on existing findings about the interrelation between spectral network properties and the dynamics of coupled oscillators - the proposed protocol allows to monitor structural properties of networked computing systems. An important aspect of this dissertation is its interdisciplinary approach towards a sensible and constructive handling of complex structures and collective dynamics in networked systems. The associated investigation of distributed systems from the perspective of non-linear dynamics and statistical physics highlights interesting parallels both to biological and physical systems. This foreshadows systems whose structures and dynamics can be analyzed and understood in the conceptual frameworks of statistical physics and complex systems.
  • Wir leben in einer vernetzten Welt, umgeben von miteinander verflochtenen, technischen Systemen. Da diese immer mehr Bereiche unseres Lebens durchdringen, gewinnt ein genaues Verständnis ihrer Struktur und Dynamik einen immer größeren Stellenwert. Gleichzeitig entstehen technische Infrastrukturen wie zum Beispiel das globale Router-Netzwerk des Internets, das World Wide Web, große Peer-to-Peer Systeme oder globale Stromnetze nicht "am Reißbrett" sondern entwickeln sich - von vielerlei Bedingungen und Wechselwirkungen beeinflusst - verteilt und außerhalb des Einflussbereichs zentraler Instanzen. Für zukünftige vernetzte Rechnersysteme wird es aufgrund der zunehmenden Komplexität immer schwieriger Aussagen über deren Struktur und Verhalten zu treffen. Eine Reihe von Störungen hat hierbei gezeigt, dass ungewollt komplexe Strukturen entstehen können, welche jenen in physikalischen, biologischen und sozialen Systemen ähneln. In dieser Arbeit gehen wir der Frage nach, wie solche komplexe Phänomene beschrieben, beherrscht und aktiv genutzt werden können. Hierzu betrachten wir methodische Ansätze aus der Erforschung zufälliger und komplexer Netzwerke, welche verstärkt zur Untersuchung natürlicher, sozialer und technischer Systeme verwendet werden und Einblicke in deren Struktur und Dynamik liefern. Einen besonderen Stellenwert nimmt die Beobachtung ein, dass die Effizienz, Zuverlässigkeit und Anpassungsfähigkeit natürlicher Systeme auf verhältnismäßig einfache, lokale und oftmals randomisierte Interaktionen zwischen einer großen Zahl von Elementen zurückgeführt werden kann. Wir fassen einige interessante Ergebnisse über die Entstehung komplexer Netzstrukturen und kollektiver Dynamik zusammen und untersuchen, wie diese beim Entwurf und Betrieb großer vernetzter Rechnersysteme nutzbar sind. Ein besonderes Augenmerk dieser Dissertation liegt auf der Anwendung von Prinzipien und Methoden aus dem Umfeld komplexer Netzwerke im Kontext verteilter Systeme, welche auf Overlay-Netzwerken beruhen. Die Tatsache, dass die (virtuelle) Konnektivität in solchen Systemen weitgehend unabhängig von physikalischen Beschränkungen angepasst werden kann, ermöglicht eine Konstruktion auf der Grundlage von Analogien zwischen komplexen Netzstrukturen und Phänomenen der statistischen Physik. Aufbauend auf Erkenntnissen über die Eigenschaften skalenfreier Netze, stellen wir ein einfaches Verbindungsprotokoll vor, mit dessen Hilfe skalenfreie Overlaynetze mit anpassbarem Knotengradexponenten auf verteilte Art und Weise erzeugt werden können. In diesem Zusammenhang demonstrieren wir, dass auf Grundlage des vorgestellten Protokolls Phasenübergangsphänomene, wie sie häufig im Umfeld der statistischen Physik auftreten, aktiv zur Anpassung makroskopischer, statistischer Netzparameter genutzt werden können, welche die Stabilität und Leistung vernetzter Systeme massiv beeinflussen. Im konkreten Fall erlaubt die Anpassung des Exponenten der Knotengradverteilung skalenfreier Overlays in kritischen Bereichen eine schnelle Veränderung relevanter struktureller sowie dynamischer Eigenschaften. Insofern ermöglicht es das untersuchte Protokoll, belastbare Aussagen über die Beziehung zwíschen dem mikroskopischen, lokalen Verhalten einzelner Netzknoten sowie den makroskopischen Eigenschaften resultierender, komplexer Netzstrukturen zu treffen. Für Systeme in denen der Knotengradexponent nicht auf einfache Art und Weise auf Grundlage lokaler Protokollparameter ableitbar ist wird zudem ein verteiltes, probabilistisches Verfahren vorgestellt, welches eine Überwachung des Exponenten und damit die Ableitung wichtiger Netzeigenschaften erlaubt. Schließlich wendet sich die Dissertation der Untersuchung nicht-linearer Dynamik in vernetzten Systemen zu. Wir betrachten ein nachrichtenbasiertes Protokoll, welches auf Basis des Kuramoto-Modells für gekoppelte Oszillatoren eine stabile, globale Synchronisation periodischer Ereignisse erreicht. Die Effizienz und Stabilität des Verfahrens wird in einer Reihe von Netztopologien untersucht. Darüber hinaus deuten wir an, dass das Verfahren - basierend auf Erkenntnissen über die Wechselwirkungen zwischen spektralen Netzeigenschaften und der Dynamik gekoppelter Oszillatoren - eine Überwachung struktureller Eigenschaften vernetzter Rechnersysteme erlaubt. Ein wichtiger Aspekt der Dissertation ist ihr interdisziplinärer Ansatz zur Schaffung eines bewussten und konstruktiven Umgangs mit komplexen Strukturen und kollektiver Dynamik in vernetzten Systemen. Die damit verknüpfte Untersuchung verteilter Systeme aus der Perspektive der nicht-linearen Dynamik und der statistischen Physik zeigt interessante Parallelen zu physikalischen, biologischen und sozialen Systemen auf. Dies verspricht Systeme deren Struktur und Verhalten mittels Methoden der komplexen Systeme und der statistischen Physik analysiert und verstanden werden kann.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Ingo Scholtes
URN:urn:nbn:de:hbz:385-7725
DOI:https://doi.org/10.25353/ubtr-xxxx-ab01-e3c9/
Advisor:Peter Sturm
Document Type:Doctoral Thesis
Language:English
Date of completion:2012/09/14
Publishing institution:Universität Trier
Granting institution:Universität Trier, Fachbereich 4
Date of final exam:2011/05/27
Release Date:2012/09/14
Tag:Komplexe Netzwerke; Komplexe Systeme; Statistische Mechanik komplexer Netze
Statistical Mechanics of complex networks; complex networks; complex systems
GND Keyword:Kom; Netzwerk; Nichtlineare Dynamik; Peer-to-Peer-Netz; Robustheit; Selbstorganisation; Synchronisierung; Telekommunikationsnetz; Zufallsgraph
Institutes:Fachbereich 4 / Informatik
Dewey Decimal Classification:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik

$Rev: 13581 $