This dissertation presents algorithms for data structures called distributed hash tables (DHT) or structured overlay networks, which are used to build scalable self-managing distributed systems. The provided algorithms guarantee lookup consistency in the presence of dynamism: they guarantee consistent lookup results in the presence of nodes joining and leaving. Similarly, the algorithms guarantee that routing never fails while nodes join and leave. Previous algorithms for lookup consistency either suffer from starvation, do not work in the presence of failures, or lack proof of correctness. Several group communication algorithms for structured overlay networks are presented. We provide an overlay broadcast algorithm, which unlike previous algorithms avoids redundant messages, reaching all nodes in O(log n) time, while using O(n) messages, where n is the number of nodes in the system. The broadcast algorithm is used to build overlay multicast. We introduce bulk operation, which enables a node to efficiently make multiple lookups or send a message to all nodes in a specified set of identifiers. The algorithm ensures that all specified nodes are reached in O(log n) time, sending maximum O(log n) messages per node, regardless of the input size of the bulk operation. Moreover, the algorithm avoids sending redundant messages. Previous approaches required multiple lookups, which consume more messages and can render the initiator a bottleneck. Our algorithms are used in DHT-based storage systems, where nodes can do thousands of lookups to fetch large files. We use the bulk operation algorithm to construct a pseudo-reliable broadcast algorithm. Bulk operations can also be used to implement efficient range queries. Finally, we describe a novel way to place replicas in a DHT, called symmetric replication, that enables parallel recursive lookups. Parallel lookups are known to reduce latencies. However, costly iterative lookups have previously been used to do parallel lookups. Moreover, joins or leaves only require exchanging O(1) messages, while other schemes require at least log(f) messages for a replication degree of f. The algorithms have been implemented in a middleware called the Distributed k-ary System (DKS), which is briefly described. / QC 20100824

<p>Structured overlay networks form a major classof peer-to-peer systems, which are touted for their abilitiesto scale, tolerate failures, and self-manage. Any long livedInternet-scale distributed system is destined to facenetwork partitions. Although the problem of network partitionsand mergers is highly related to fault-tolerance andself-management in large-scale systems, it has hardly beenstudied in the context of structured peer-to-peer systems.These systems have mainly been studied under churn (frequentjoins/failures), which as a side effect solves the problemof network partitions, as it is similar to massive nodefailures. Yet, the crucial aspect of network mergers has beenignored. In fact, it has been claimed that ring-based structuredoverlay networks, which constitute the majority of thestructured overlays, are intrinsically ill-suited for mergingrings. In this thesis, we present a number of research papers representing our work on handling network partitions and mergers in structured overlay networks. The contribution of this thesis is threefold. First, we provide a solution for merging ring-based structured overlays. Our solution is tuneable, by a {\em fanout} parameter, to achieve a trade-off between message and time complexity. Second, we provide a network size estimation algorithm for ring-based structured overlays. We believe that an estimate of the current network size can be used for tuning overlay parameters that change according to the network size, for instance the fanout parameter in our merger solution.Third, we extend our work from fixing routing anomalies to achieving data consistency. We argue that decreasing lookup inconsistencies on the routing level aids in achieving data consistency in applications built on top of overlays. We study the frequency of occurence of lookup inconsistencies and discuss solutions to decrease the affect of lookup inconsistencies.</p>

Distributed applications built on top of Structured Overlay Networks (SONs) operate based on certain self-* behaviors of the underlying Peer-to-Peer network. Among those, self-organization and self-healing are the two most prominent and assumed properties. The operating environment of distributed systems continues to be more inhospitable with the advance and demand of new technologies; for example in case of mobile and ad hoc networks Churn (node turnover) can be extremely high due to node mobility, frequent disconnects/reconnects and configuration changes. Also, in such dynamic environments, the system may face high Churn (node turnover) and Network partition in a frequent manner. The situation becomes worse if the self-healing behavior of underlying SON is not complete and well defined. This implies the following non-trivial questions: Can the maintenance mechanism of a SON heal the damage to the structure due to harshness of the operating environment and reverse it back? What are the pre-conditions; in other words, what properties the healing mechanism should possess in order to achieve reversibility against stressful environments? Existing literature lacks such assessment and verification study of the self-healing property of a SON. In this thesis, we investigate both the behavior and design of a system that operate in inhospitable environments. This work is relevant to systems with both peaks of high stress (e.g. partitions, churn, network dynamicity etc.) and continuous high stress. We evaluate existing overlay maintenance strategies, namely Correction-on-Change, Correction-on-Use, Periodic Stabilization, and Ring Merge. We define the reversibility property of a system as its ability to repair itself to its original state. We propose a new strategy, called Knowledge Base, to improve conditions for reversibility against inhospitable environments. By means of simulations, we demonstrate reversibility for overlay networks with high levels of partition and churn. We make general conclusions about the ability of the maintenance strategies to achieve reversibility. Identification of Phase Transitions in a SON can provide useful information about the properties of each state of the system. Also, this enables to find the critical points in the operating space and parameters influencing them. The applications running on top of the SON can potentially utilize this knowledge to adapt its operation accordingly in different system states. In this thesis, a representative ring-based SON, namely Beernet is chosen and extended to achieve reversibility. The resulting overlay, Beernet++ exhibits reversible phase transitions under churn. We analyze the critical points observed during such transitions. We present the behavior of Beernet++ for high level of churn and network partitioning, along with their interaction. / <p>QC 20150929</p>

Structured overlay networks form a major classof peer-to-peer systems, which are touted for their abilitiesto scale, tolerate failures, and self-manage. Any long livedInternet-scale distributed system is destined to facenetwork partitions. Although the problem of network partitionsand mergers is highly related to fault-tolerance andself-management in large-scale systems, it has hardly beenstudied in the context of structured peer-to-peer systems.These systems have mainly been studied under churn (frequentjoins/failures), which as a side effect solves the problemof network partitions, as it is similar to massive nodefailures. Yet, the crucial aspect of network mergers has beenignored. In fact, it has been claimed that ring-based structuredoverlay networks, which constitute the majority of thestructured overlays, are intrinsically ill-suited for mergingrings. In this thesis, we present a number of research papers representing our work on handling network partitions and mergers in structured overlay networks. The contribution of this thesis is threefold. First, we provide a solution for merging ring-based structured overlays. Our solution is tuneable, by a {\em fanout} parameter, to achieve a trade-off between message and time complexity. Second, we provide a network size estimation algorithm for ring-based structured overlays. We believe that an estimate of the current network size can be used for tuning overlay parameters that change according to the network size, for instance the fanout parameter in our merger solution.Third, we extend our work from fixing routing anomalies to achieving data consistency. We argue that decreasing lookup inconsistencies on the routing level aids in achieving data consistency in applications built on top of overlays. We study the frequency of occurence of lookup inconsistencies and discuss solutions to decrease the affect of lookup inconsistencies.