Fundamental algorithmic techniques for distributed computations in networks : : information dissemination and maximum matching

Abstract: Distributed graph algorithms are theoretically well-established methods for solving graph problems in distributed settings such as networks of computers in which computing units are modeled by vertices and the communication links among them by edges.

In this thesis, we study two fundamental graph problems; information dissemination and maximum matching, and provide algorithmic techniques and lower bound analyses in the CONGEST model of computation. In that, time is assumed to be synchronously slotted into consecutive rounds such that in each round, every processing unit performs an arbitrary local computation and exchanges a limited amount of information with the processing units in its neighborhood in the network.

The first part of this thesis addresses the information dissemination problem in adversarial dynamic networks whose topology changes from round to round. The problem requires the receipt of pieces of information by all the processing units in the network when the information is initially given to only a subset of them. In essence, the relation between stability and connectivity of the dynamic network and the efficiency of information dissemination is studied. The efficiency is measured by studying the necessity and sufficiency of the number of rounds (time complexity) and also the total volume of the exchanged information (message complexity) to solve the problem.

The second part of the thesis addresses the maximum matching graph problem. The problem asks for a maximum cardinality (or total weight) independent set of edges in a graph. We assume that the communication network is the same as the input graph to the problem. We present deterministic and randomized algorithms to compute and verify exact and approximate maximum matching for the weighted and unweighted versions of the problem
Abstract: Algorithmen für verteilte Graphen umfasst etablierte theoretische Methoden zur Lösung
von Graphenproblemen welche verteilt berechnet werden müssen, bspw. in einem Computer netzwerk, bei dem Recheneinheiten durch die Knoten und die Kommunikationsverbindungen zwischen ihnen durch die Kanten eines Graphs modelliert werden.

In dieser Arbeit untersuchen wir die zwei fundamentalen Graphenprobleme der Informationsverbreitung und der Berechnung eines Maximum Matchings und stellen algorithmische Techniken und Analysen von unteren Schranken im CONGEST Berechnungsmodell bereit. Bei diesem Modell wird angenommen, dass die Zeit in synchrone, aufeinanderfolgende Runden aufgeteilt ist, wobei jede Recheneinheit in jeder Runde beliebige lokale Berechnungen durchführt sowie eine begrenzte Menge an Informationen mit allen benachbarten Recheneinheiten im Netzwerk austauscht.

Der erste Teil dieser Arbeit befasst sich mit dem Problem der Informationsverbreitung in dynamischen Netzwerken, deren Topologie sich, gesteuert von einem Gegenspieler, von Runde zu Runde ändert. Bei diesem Problem fordern wir das alle Recheneinheiten eine Informationen über das Netzwerk empfangen müssen, welche anfänglich nur einer Teilmenge der Recheneinheiten bekannt ist. Im Wesentlichen wird der Zusammenhang zwischen Stabilität und Konnektivität des dynamischen Netzwerks und der Effizienz der Informationsverbreitung untersucht. Das Maß für die Effizienz welches wir untersuchen ist die (notwendige und hinreichende) Anzahl der Runden (Zeitkomplexität) sowie das Gesamtvolumen der ausgetauschten Informationen (Nachrichtenkomplexität) zur Lösung dieses Problems.

Der zweite Teil der Arbeit befasst sich mit dem Problem des “Maximum Matching” von Graphen. Bei diesem Problem möchte man eine maximale Menge von unabhängigen Kanten eines Graphen (oder eine unabhängige Kantenmenge mit maximalem Gesamtgewicht) berechnen. Wir gehen bei diesem Problem davon aus, dass das Kommunikationsnetzwerk identisch zum Eingabegraph für das Problem ist. Wir präsentieren deterministische und randomisierte Algorithmen zur genauen und approximativen Berechnung und Überprüfung eines “Maximum Matching” für die gewichtete und ungewichtete Variante des Problems

Angaben zum Objekt

• Standort: Deutsche Nationalbibliothek Frankfurt am Main
• Umfang: Online-Ressource
• Sprache: Englisch
• Anmerkungen: Universität Freiburg, Dissertation, 2020

Beteiligte, Orts- und Zeitangaben

• Ereignis: Veröffentlichung
• (wo): Freiburg
• (wer): Universität
• (wann): 2021
• Urheber: Ahmadi, Mohamad
• Beteiligte Personen und Organisationen: Kuhn, Fabian ; Albert-Ludwigs-Universität Freiburg. Fakultät für Angewandte Wissenschaften

Weitere Informationen

• DOI: 10.6094/UNIFR/175757
• URN: urn:nbn:de:bsz:25-freidok-1757574
• Rechteinformation: Der Zugriff auf das Objekt ist unbeschränkt möglich.
• Letzte Aktualisierung: 25.03.2025, 13:50 MEZ