Mobile ad hoc networks consist of potentially moving, computing nodes that communicate via radio and do not have access to any fixed infrastructure. The knowl- edge about nearby nodes is a fundamental requirement and is part of many of the known solutions to problems in mobile and wireless networks including routing, broad- casting, distributed token circulation, etc. The existing solutions for this problem of knowing about neighbors are probabilistic. In this thesis, we give a first step towards a distributed, deterministic algorithm for finding out about the neighboring nodes. In particular, we focus on the problem of maintaining information about neighboring nodes in a one dimensional mobile and wireless ad hoc environment. Under some simplifying assumptions, we give an algorithm for the problem and a proof of correctness for the algorithm. We deal with efficiency in terms of both time and space. We prove a tight bound on the speed of propagation of the message when the nodes are sufficiently dense. We also consider the case when multiple clusters merge together. Our algorithm is space efficient in that the nodes do not include information about all the nodes they know in their broadcast message at all times. Nodes also store only the information about relevant nodes in their local store and purge information about nodes that have moved out of range. Our work shows that it is possible to solve the problem deterministically, and with reasonable values of the parameters, under some simplifying assumptions. Numerous interesting open questions remain in the area regarding how to relax the assumptions to make the approach more practical.

There are many variants of leader election algorithm in distributed networks. In this research, an agent based approach to leader election in distributed networks is investigated. Agents have shown to be useful in several ways. In the theoretical perspective, agents sometime help in reducing the message complexity of the system and sometimes help in lowering time complexity. In a more practical sense, agents perform operations independent of the processors, thereby lending a more flexible algorithm supporting different types of networks.

There are many variants of leader election algorithm in distributed networks. In this research, an agent based approach to leader election in distributed networks is investigated. Agents have shown to be useful in several ways. In the theoretical perspective, agents sometime help in reducing the message complexity of the system and sometimes help in lowering time complexity. In a more practical sense, agents perform operations independent of the processors, thereby lending a more flexible algorithm supporting different types of networks.

We develop two algorithms for important problems in mobile ad hoc networks (MANETs). A MANET is a collection of mobile processors (“nodes”) which communicate via message passing over wireless links. Each node can communicate directly with other nodes within a specified transmission radius; other communication is accomplished via message relay. Communication links may go up and down in a MANET (as nodes move toward or away from each other); thus, the MANET can consist of multiple connected components, and connected components can split and merge over time. We first present a deterministic leader election algorithm for asynchronous MANETs along with a correctness proof for it. Our work involves substantial modifications of an existing algorithm and its proof, and we adapt the existing algorithm to the asynchronous environment. Our algorithm’s running time and message complexity compare favorably with existing algorithms for leader election in MANETs. Second, many algorithms for MANETs require or can benefit from knowledge about the size of the network in terms of the number of processors. As such, we present an algorithm to approximately determine the size of a MANET. While the algorithm’s approximations of network size are only rough ones, the algorithm has the important qualities of requiring little communication overhead and being tolerant of link failures.

How much damage can a malicious tiny device cause in a single-hopwireless network? Imagine two players, Alice and Bob, who want toexchange information. Collin, a malicious adversary, wants to preventthem from communicating. By broadcasting at the same time as Alice orBob, Collin can destroy their messages or overwhelm them with his ownmalicious data. Being a tiny device, however, Collin can onlybroadcast up to B times. Given that Alice and Bob do not knowB, and cannot distinguish honest from malicious messages, howlong can Collin prevent them from communicating? We show the answerto be 2B + Theta(lg|V|) communication rounds, where V is theset of values that Alice and Bob may transmit. We prove this resultto be optimal by deriving an algorithm that matches our lowerbound---even in the stronger case where Alice and Bob do not start thegame at the same time.We then argue that this specific 3-player game captures the generalextent to which a malicious adversary can disrupt coordination in asingle-hop wireless network. We support this claim by deriving---via reduction from the 3-player game---round complexity lower boundsfor several classical n-player problems: 2B + Theta(lg|V|) for reliable broadcast,2B + Omega(lg(n/k)) for leader election among k contenders,and 2B + Omega(k*lg(|V|/k)) for static k-selection. We then consider an extension of our adversary model that also includes up to t crash failures. We study binary consensus as the archetypal problem for this environment and show a bound of 2B + Theta(t) rounds. We conclude by providing tight, or nearly tight, upper bounds for all four problems. The new upper and lower bounds in this paper represent the first such results for a wireless network in which the adversary has the ability to disrupt communication.

Nous proposons tout d'abord une étude de plusieurs problèmes de l'algorithmique distribuée. Nous fournissons un modèle formel appliqué aux réseaux de diffusion anonymes. Dans ce modèle, nous caractérisons les graphes dans lesquels il est possible de résoudre l'énumération et l'élection. Cette caractérisation se base sur la notion d'homomorphisme de graphes. Nous proposons deux algorithmes dont la complexité est polynomiale et qui améliorent les complexités exponentielles connues jusqu'à présent. Dans un second temps, nous étudions le problème du calcul de l'état global et nous introduisons la notion de weak snapshot. Nous montrons qu'il existe des solutions pour ce problème dans les réseaux anonymes. Nous présentons plusieurs résultats concernant le calcul de l'état global en liaison avec des applications telles que le calcul de points de reprise, la détection de la terminaison ou encore le calcul d'une cartographie du réseau. Dans un cadre plus pratique, nous présentons la conception, le développement et l'implémentation des algorithmes proposés pour le calcul de l'état global au sein du logiciel de simulation et de visualisation ViSiDiA. / In this thesis, we first present a study of several problems in the field of distributed algorithms. We provide a formal model that relies on anonymous networks. In this model, we characterize graphs in which it is possible to solve enumeration and leader election problems. This characterization is based on graph homomorphism. We introduce two algorithms with polynomial complexities that improve existing works with exponential complexities. On the other hand, we study the snapshot problem and we introduce the notion of weak snapshot. We show that there exist solutions for this problem in the context of anonymous networks. We present several results about distributed snapshots that deal with checkpoint and rollback recovery, termination detection or the cartography computation of a network. In a practical aspect, we present the conception, the development process and the implementation of these distributed snapshot algorithms within the simulation and visualization software ViSiDiA.

Les récentes avancées technologiques en particulier dans le domaine de la miniaturisation de dispositifs robotiques laissent présager l'émergence de grands ensembles distribués de petits robots qui coopéreront en vue d'accomplir des tâches complexes (e.g., robotique modulaire, robots en essaims, microsystèmes électromécaniques distribués). Ces grands ensembles seront composés d'entités indépendantes, intelligentes et communicantes qui agiront comme un ensemble à part entière. Pour cela, elles s'auto-organiseront et collaboreront en vue d'accomplir des tâches complexes. Ces systèmes présenteront les avantages d'être plus polyvalents et plus robustes que les systèmes robotiques conventionnels tout en affichant un prix réduit. Ces ensembles formeront des systèmes distribués complexes dans lequel chaque entité sera un système embarqué à part entière avec ses propres capacités et ressources toute fois limitées. Coordonner de tels systèmes posent des défis majeurs et ouvrent de nouvelles opportunités dans l'algorithmique distribuée. Je défends la thèse qu'il faut d'ores et déjà identifier et implémenter des algorithmes distribués servant de primitives de base à la coordination de ces ensembles. Dans ce travail, nous nous focalisons sur une classe particulière de robots, à savoir les robots modulaires distribués formant de grands ensembles de modules fortement contraints en ressources (mémoire, calculs, etc.), placés dans une grille régulière et capables de communiquer entre voisins connexes uniquement. J'ai identifié et implémente trois primitives servant à la coordination de ces systèmes, à savoir l'élection d'un nœud central au réseau, la synchronisation temporelle ainsi que l'auto-reconfiguration. Dans ce manuscrit, je propose un ensemble d'algorithmes distribués réalisant ces primitives. J'ai évalué mes algorithmes en utilisant des expériences sur des modules matériels et en simulation sur des systèmes, composés de quelques dizaines à plus d'une dizaine de milliers de modules. Ces expériences montrent que nos algorithmes passent à l'échelle et sont adaptés aux grands ensembles distribués de systèmes embarqués avec des ressources fortement limités à la fois en mémoire et en calcul. / Technological advances especially in the miniaturization of robotic devices foreshadow the emergence of large-scale ensembles of small-size resource-constrained robots that distributively cooperate to achieve complex tasks (e.g., modular self-reconfigurable robots, swarm robotic systems, distributed microelectromechanical systems, etc.). These ensembles are formed from independent, intelligent and communicating units which act as a whole ensemble. These units cooperatively self-organize themselves to achieve common goals. These systems are tought to be more versatile and more robust than conventional robotic systems while having at the same time a lower cost.These ensembles form complex asynchronous distributed systems in which every unit is an embedded system with its own but limited capabilities. Coordination of such large-scale distributed embedded systems poses significant algorithmic issues and open for new opportunities in distributed algorithms. In my thesis, I defend the idea that distributed algorithmic primitives suitable for the coordination of these ensembles should be both identified and designed.In this work, we focus on a specific class of modular robotics systems, namely large-scale distributed modular robotic ensembles composed of resource-constrained modules that are organized in a lattice structure and which can only communicate with neighboring modules. We identified and implemented three building blocks, namely centrality-based leader election, time synchronization and self-reconfiguration.We propose a collection of distributed algorithms to realize these primitives. We evaluate them using both hardware experiments and simulations on systems ranging from a dozen of modules to more than a dozen of thousands of modules. We show that our algorithms scale well and are suitable for large-scale embedded distributed systems with scarce memory and computing resources.

A distributed system is defined as a collection of autonomous computers connected by a network, and with the appropriate distributed software for the system to be seen by users as a single entity capable of providing computing facilities. Distributed systems with centralised control have a distinguished control node, called leader node. The main role of a leader node is to distribute and manage shared resources in a resource-efficient manner. A distributed system with centralised control can use stream processing networks for communication. In a stream processing system, applications typically act as continuous queries, ingesting data continuously, analyzing and correlating the data, and generating a stream of results. Fault tolerance is the ability of a system to process the information, even if it happens any failure or anomaly in the system. Fault tolerance has become an important requirement for distributed systems, due to the possibility of failure has currently risen to the increase in number of nodes and the runtime of applications in distributed system. Therefore, to resolve this problem, it is important to add fault tolerance mechanisms order to provide the internal capacity to preserve the execution of the tasks despite the occurrence of faults. If the leader on a centralised control system fails, it is necessary to elect a new leader. While leader election has received a lot of attention in message-passing systems, very few solutions have been proposed for shared memory systems, as we propose. In addition, rollback-recovery strategies are important fault tolerance mechanisms for distributed systems, since that it is based on storing information into a stable storage in failure-free state and when a failure affects a node, the system uses the information stored to recover the state of the node before the failure appears. In this thesis, we are focused on creating two fault tolerance mechanisms for distributed systems with centralised control that uses stream processing for communication. These two mechanism created are leader election and log-based rollback-recovery, implemented using LPEL. The leader election method proposed is based on an atomic Compare-And-Swap (CAS) instruction, which is directly available on many processors. Our leader election method works with idle nodes, meaning that only the non-busy nodes compete to become the new leader while the busy nodes can continue with their tasks and later update their leader reference. Furthermore, this leader election method has short completion time and low space complexity. The log-based rollback-recovery method proposed for distributed systems with stream processing networks is a novel approach that is free from domino effect and does not generate orphan messages accomplishing the always-no-orphans consistency condition. Additionally, this approach has lower overhead impact into the system compared to other approaches, and it is a mechanism that provides scalability, because it is insensitive to the number of nodes in the system.

Cette thèse est consacrée à l'étude des processus stochastiques décentralisés. Parmi les exemples typiques de ces processus figurent la dynamique météorologique, la circulation automobile, la façon dont nous rencontrons nos amis, etc. Dans cette thèse, nous exploitons une large palette d'outils probabilistes permettant d'analyser des chaînes de Markov afin d'étudier un large éventail de ces processus distribués : modèle des feux de forêt (réseaux sociaux), balls-into-bins avec suppression, et des dynamiques et protocoles de consensus fondamentaux tels que Voter Model, 2-Choices, et 3-Majority. / This thesis is devoted to the study of stochastic decentralized processes. Typical examples in the real world include the dynamics of weather and temperature, of traffic, the way we meet our friends, etc. We take the rich tool set from probability theoryfor the analysis of Markov Chains and employ it to study a wide range of such distributed processes: Forest Fire Model (social networks), Balls-into-Bins with Deleting Bins, and fundamental consensus dynamics and protocols such as the Voter Model, 2-Choices, and 3-Majority.

Das Internet und darauf aufbauende Infrastrukturen haben sich als zentrale Medien zum weltweiten Abruf und Austausch von Informationen etabliert. Im Zuge dessen ist das Internet ein wichtiges Werkzeug zur globalen Vernetzung von Aktivisten und Journalisten geworden, welche dieses zudem als Plattform zur Veröffentlichung von Rechercheergebnissen und Beweismaterial verwenden. Um den Zugang zu kompromittierenden oder als unerwünscht erachteten Informationen über das Internet zu unterbinden, haben jedoch Regierungen weltweit weitreichende technische Zensurmaßnahmen implementiert. Um diesen Maßnahmen entgegenzuwirken sind Betroffene darauf angewiesen, ihre digitale Kommunikation über Geräte von Drittanbietern zu leiten, welche sich außerhalb des Einflussbereichs des Zensors befinden und deren Rolle als Umgehungsknoten für den Zensor schwer zu detektieren ist. Eine vielversprechender Ansatz zur Realisierung solcher Gegenmaßnahmen sind Friend-to-Friend (F2F) Overlay-Netzwerke. Ähnlich zu Anonymisierungsnetzwerken wie Tor und AN.ON setzen sich F2F Overlays aus den Knoten von mehreren Betreibern zusammen, wodurch ein Single Point of Failure vermieden wird. Um gegen Unterwanderung zu schützen wird jedoch die Kommunikation zwischen den Knoten in F2F Overlays auf jene Paare beschränkt, deren Betreiber sich gegenseitig vertrauen. Folglich erfordert das Aufdecken der Knoten eines F2F Overlays die Identifizierung und Kompromittierung deren Betreiber durch den Zensor mit Hilfe von Social-Engineering-Methoden. Um Anwendungsfälle wie anonymes Blogging zu unterstützen, benötigen F2F Overlays ein Routing-Protokoll, welches Datenübertragungen zwischen Knoten ohne wechselseitig vertraute Betreiber ermöglicht. Aufgrund seiner hohen Effizienz und Ausfalltoleranz gilt Routing anhand von Rooted Spanning Tree (RST) Embeddings hierfür als besonders vielversprechender Kandidat. Dabei wählen die teilnehmenden Knoten zunächst einen Knoten als Wurzel und formen, ausgehend von diesem, einen virtuellen Wurzelbaum über das F2F Overlay. Anschließend wird jedem Knoten eine virtuelle Adresse zugewiesen, welche dessen Position in dem zuvor erzeugten Wurzelbaum eindeutig repräsentiert. In F2F Overlays muss davon ausgegangen werden, dass ein Zensor, welcher einen Teil der Knotenbetreiber kompromittieren konnte, mit Hilfe eigener Knoten aktive Angriffe auf das Routing durchführt, um die Verbreitung von Inhalten zu unterbinden. Bisherige Forschung zu Routing anhand von RST Embeddings konzentriert sich jedoch primär auf die Steigerung dessen Effizienz sowie der Verbesserung dessen Robustheit gegenüber permanenter Ausfälle. In dieser Arbeit werden bisher unbekannte Angriffe auf RST-Embedding-basierte Routing-Protokolle vorgestellt, welche von bösartigen F2F-Overlay-Teilnehmern mit geringem Aufwand durchgeführt werden können. Ergänzend stellen wir anschließend Maßnahmen vor, welche derartige Routing-Protokolle inhärent robuster gegen Fehlverhalten machen. Ein wesentlicher Einflussfaktor bezüglich der Effektivität der identifizierten Angriffe ist die Tatsache, ob der gewählte Wurzelknoten ein Knoten des Angreifers ist oder nicht. Während die von uns vorgestellten Schutzmaßnahmen die Auswirkung der Angriffe auch in dem Fall begrenzen, dass der Wurzelnoten sich bösartig verhält, so erfordert das Routing von Nachrichten dabei nichtsdestotrotz erhöhten Aufwand bei gleichzeitig reduzierter Erfolgswahrscheinlichkeit. Die Wurzelwahlverfahren bisheriger RST-Embedding-basierter Routing-Protokolle können in F2F Overlays jedoch nicht auf sichere Weise umgesetzt werden, so dass ein Angreifer mit geringem Aufwand erreichen kann, dass einer seiner Knoten als Wurzel gewählt wird. Während es in F2F Overlays allgemein nicht ausgeschlossen werden kann, dass ein bösartiger Knoten als Wurzel gewählt wird, so ist es dennoch erstrebenswert, die Wahrscheinlichkeit der Wahl eines nicht-bösartigen Knotens zu erhöhen. Da bisherige Verfahren zur sicheren, verteilten Wahl eines Knotens nicht effektiv in F2F Overlays umgesetzt werden können, wird in dieser Arbeit ein neues Wurzelwahlverfahren vorgestellt. Dieses basiert auf lokalen, randomisierten Mehrheitsentscheidungen, um einen Konsens auf einen einzelnen Knoten herbeizuführen. Ergänzend dazu werden Ergebnisse einer Simulationsstudie anhand realer sozialer Graphen vorgestellt, welche belegen, dass dieser Ansatz einer Unterwanderung widersteht, wenn der Angreifer eine geringe Anzahl von Teilnehmern kompromittieren konnte. Gleichzeitig legen die Ergebnisse der Studie nahe, dass dieses Verfahren auch in F2F Overlays mit zehntausenden von Knoten in kurzer Zeit eine Einigung auf einen gemeinsamen Wurzelknoten für den Großteil der Knoten erreicht. Zur Effizienzsteigerung leiten aktuelle RST-Embedding-basierte Routing-Protokolle die Addressen anhand von Breitensuchbäumen ab. Der Aufbau derartiger Bäume erfordert jedoch, dass jeder Knoten seinem Nachbarn die eigene Hop-Distanz zum Wurzelknoten mitteilt. Dabei können Angreiferknoten gezielt inkorrekte Distanzwerte versenden, um die Anzahl der gutartigen Knoten zu maximieren, welche diese als Elternknoten wählen und folglich von anschließenden Angriffen betroffen sind. Um derartige Angriffe zu unterbinden, wird in dieser Arbeit zudem ein verteilter, selbststabilisierender Algorithmus zum Aufbau von Breitensuchbäumen vorgestellt. Dieser verwendet kryptografische Signaturen in Kombination mit Zeitstempeln, um inkorrekte sowie veraltete Distanzwerte erkennbar zu machen. Die Nutzung von RST Embeddings birgt neben Angriffen auf deren Verfügbarkeit das Risiko, dass ein interner Angreifer Informationen über die Topologie des zugrundeliegenden Netzwerkes gewinnen kann. Im Kontext von F2F Overlays ist dies problematisch, da deren Struktur dem sozialen Netzwerk deren Teilnehmern entspricht. Erlangt ein Angreifer einen Schnappschuss der Topologie eines F2F Overlays oder eines Teils davon, so kann er diesen mit der Topologie anderer sozialer Netzwerkgraphen abgleichen, um bisher unbekannte Teilnehmer aufzudecken. Das konkrete Ausmaß, in dem RST Embeddings sowie das darauf aufbauende Routing Rückschlüsse über die Topologie des Netzwerkes zulassen wurde bisher jedoch nicht untersucht. Der vierte Beitrag dieser Dissertation besteht daher aus einer detaillierten Analyse bezüglich der konkreten Informationen, welche ein interner Angreifer anhand der durch RST-Embedding-basierte Routing-Protokolle propagierten Daten gewinnen kann. / Today, the Internet plays a vital role in enabling activists and journalists to collaborate and to publish critical information on a global scale. As a consequence, governments around the globe have implemented technical censorship measures to keep citizens from accessing content that is deemed inappropriate or compromising. To address such censorship measures, a circumvention infrastructure is needed that allows affected individuals to route their online communication through third-party servers that are outside of the censor’s influence and whose use for circumvention is difficult to detect for the censor. A promising substrate to realize such an infrastructure are Friend-to-Friend (F2F) overlay networks. Similar to anonymization networks like Tor and AN.ON, F2F overlay nodes may be operated by different individuals, thus avoiding a single point of failure. To protect against infiltration, F2F overlays additionally restrict communication between participating devices to those pairs whose operators mutually trust each other. Thus, censors need to perform social engineering in order to discover operators and their nodes. To realize use cases that require communication between nodes of participants without mutual trust, such as distributed and redundant content storage or anonymous blogging, F2F overlays require a routing protocol suitable for large, dynamic networks. Among the current research on routing protocols for F2F overlays, routing based on rooted spanning tree (RST) embeddings emerged as the most promising candidate due to its high efficiency and fault tolerance. In this approach, nodes collaboratively determine a rooted spanning tree over the overlay topology and, starting from the elected root node, assign each node a virtual address that encodes its unique position in the tree. Given that a censor may compromise a fraction of the participants of an F2F overlay, it is likely that the censor will use nodes under their control to actively attack the routing protocol in order to disrupt communication. However, existing research on RST embeddings concentrates on their efficient implementation as well as resilience to permanent faults, thus leaving open in which ways such routing protocols can be attacked. Towards this end, this thesis presents previously unknown attacks that malicious participants of an F2F overlay can easily perform against state-of-the-art routing protocols. As these attacks cannot be reliably attributed to malicious nodes, we propose countermeasures that improve the inherent resilience of such protocols against misbehaving nodes. A fundamental risk that cannot completely be avoided in F2F overlays is that a malicious node may be chosen as the root node of the embedding, giving it a particularly strong position for attacks. While our proposed countermeasures limit the impact of malicious root behavior, routing in such a scenario nonetheless comes at the cost of increased routing overhead and an increased chance of routing failure. Since existing routing protocols based on RST embeddings employ insecure root election schemes, it is desirable to increase the likelihood that a benign node is chosen as root. Because existing secure protocols for node election cannot be used effectively in F2F overlays, we propose a novel root election protocol that leverages local voting algorithms to reach consensus on a single node. Simulations on real-world social graphs show that in F2F overlays, the protocol is able to reach consensus among a large fraction of nodes quickly and, in contrast to election protocols used by state-of-the-art routing algorithms, resists compromise by malicious nodes. To improve efficiency, state-of-the-art protocols embed breadth-first-search (BFS) trees for address assignment, whose formation relies on the truthful reporting of hop distances. In the presence of a benign root node, malicious nodes may deliberately propagate incorrect distance values to maximize the number of benign nodes that choose them as parent, thus increasing the impact of subsequent attacks. To defend against such misbehavior, we furthermore propose a self-stabilizing BFS formation algorithm that leverages cryptographic signatures to make incorrectly reported distances detectable. Additional to the risk of attacks aiming at the disruption of communication, RST embeddings and the routing based on them inherently leaks information about the topology of the underlying network to its participants. Such leakage is problematic in F2F overlays, as topology snapshots can be linked with graph data from further sources in order to identify participants. However, the concrete inferences malicious participants can make from the routing control data propagated by state-of-the-art protocols has not been investigated so far. The fourth contribution of this thesis therefore lies in the analysis of which information about the topology of an F2F overlay malicious participants can infer from the control data propagated by RST embedding algorithms as well as the resulting routing of messages.