In this paper we present and analyze HSkip+, a self-stabilizing overlay network for nodes with arbitrary heterogeneous bandwidths. HSkip+ has the same topology as the Skip+ graph proposed by [1] but its self-stabilization mechanism significantly outperforms the self-stabilization mechanism proposed for Skip+. Also, the nodes are now ordered according to their bandwidths and not according to their identifiers. Various other solutions have already been proposed for overlay networks with heterogeneous bandwidths, but they are not self-stabilizing. In addition to HSkip+ being self-stabilizing, its performance is on par with the best previous bounds on the time and work for joining or leaving a network of peers of logarithmic diameter and degree and arbitrary bandwidths. Also, the dilation and congestion for routing messages is on par with the best previous bounds for such networks, so that HSkip+ combines the advantages of both worlds. Our theoretical investigations are backed by simulations demonstrating that HSkip+ is indeed performing much better than Skip+ and working correctly under high churn rates.
Topological self-stabilization has recently attracted a lot of attention. Various topologies have been considered such as simple line and ring networks (e.g., @cite_14 @cite_7 ), skip lists and skip graphs (e.g., @cite_19 @cite_0 ), expanders @cite_13 , the Delaunay graph @cite_9 , the hypertree @cite_5 , and Chord @cite_8 . Also a universal protocol for topological self-stabilization has been proposed @cite_22 . However, none of these works consider nodes with heterogeneous bandwidths.
@cite_14 @cite_22 @cite_7 @cite_8 @cite_9 @cite_0 @cite_19 @cite_5 @cite_13
2164639586 153242498 2118184224 1992206081 2163818815 2009821304 1580692781 2021142034
We propose a self-stabilizing and modeless peer-to-peer (P2P) network construction and maintenance protocol, called the Ring Network (RN) protocol. The RN protocol, when started on a network of peers that are in an arbitrary state, will cause the network to converge to a structured P2P system with a directed ring topology, where peers are ordered according to their identifiers. Furthermore, the RN protocol maintains this structure in the face of peer joins and departures. The RN protocol is a distributed and asynchronous message-passing protocol, which fits well the autonomous behavior of peers in a P2P system. The RN protocol requires only the existence of a bootstrapping system which is weakly connected. Peers do not need to be informed of any global network state, nor do they need to assist in repairing the network topology when they leave. We provide a proof of the self-stabilizing nature of the protocol, and experimentally measure the average cost (in time and number of messages) to achieve convergence. Overlay networks are expected to operate in hostile environments, where node and link failures are commonplace. One way to make overlay networks robust is to design self-stabilizing overlay networks, i.e., overlay networks that can handle node and link failures without any external supervision. In this paper, we first describe a simple framework, which we call the Transitive Closure Framework (TCF), for the selfstabilizing construction of an extensive class of overlay networks. Like previous self-stabilizing overlay networks, TCF permits node degrees to grow to Ω(n), independent of the maximum degree of the target overlay network. However, TCF has several advantages over previous work in this area: (i) it is a "framework" and can be used for the construction of a variety of overlay networks, not just a particular network, (ii) it runs in an optimal number of rounds for a variety of overlay networks, and (iii) it can easily be composed with other non-self-stabilizing protocols that can recover from specific bad initial states in a memory-efficient fashion. We demonstrate the power of our framework by deriving from TCF a simple self-stabilizing protocol for constructing Skip+ graphs (, PODC 2009) which presents optimal convergence time from any configuration, and requires only a O(1) factor of extra memory for handling node Joins. Topological self-stabilization is an important concept to build robust open distributed systems (such as peer-to-peer systems) where nodes can organize themselves into meaningful network topologies. The goal is to devise distributed algorithms that converge quickly to such a desirable topology, independently of the initial network state. This paper proposes a new model to study the parallel convergence time. Our model sheds light on the achievable parallelism by avoiding bottlenecks of existing models that can yield a distorted picture. As a case study, we consider local graph linearization—i.e., how to build a sorted list of the nodes of a connected graph in a distributed and self-stabilizing manner. We propose two variants of a simple algorithm, and provide an extensive formal analysis of their worst-case and best-case parallel time complexities, as well as their performance under a greedy selection of the actions to be executed. The Chord peer-to-peer system is considered, together with CAN, Tapestry and Pastry, as one of the pioneering works on peer-to-peer distributed hash tables (DHT) that inspired a large volume of papers and projects on DHTs as well as peer-to-peer systems in general. Chord, in particular, has been studied thoroughly, and many variants of Chord have been presented that optimize various criteria. Also, several implementations of Chord are available on various platforms. Though Chord is known to be very efficient and scalable and it can handle churn quite well, no protocol is known yet that guarantees that Chord is self-stabilizing, i.e., the Chord network can be recovered from any initial state in which the network is still weakly connected. This is not too surprising since it is known that in the Chord network it is not locally checkable whether its current topology matches the correct topology. We present a slight extension of the Chord network, called Re-Chord (reactive Chord), that turns out to be locally checkable, and we present a self-stabilizing distributed protocol for it that can recover the Re-Chord network from any initial state, in which the n peers are weakly connected, in O(n log n) communication rounds. We also show that our protocol allows a new peer to join or an old peer to leave an already stable Re-Chord network so that within O((log n)2) communication rounds the Re-Chord network is stable again. This article studies the construction of self-stabilizing topologies for distributed systems. While recent research has focused on chain topologies where nodes need to be linearized with respect to their identifiers, we explore a natural and relevant 2-dimensional generalization. In particular, we present a local self-stabilizing algorithm DStab which is based on the concept of ''local Delaunay graphs'' and which forwards temporary edges in greedy fashion reminiscent of compass routing. DStab constructs a Delaunay graph from any initial connected topology and in a distributed manner in time O(n^3) in the worst-case; if the initial network contains the Delaunay graph, the convergence time is only O(n) rounds. DStab also ensures that individual node joins and leaves affect a small part of the network only. Such self-stabilizing Delaunay networks have interesting applications and our construction gives insights into the necessary geometric reasoning that is required for higher-dimensional linearization problems. We present Corona, a deterministic self-stabilizing algorithm for skip list construction in structured overlay networks. Corona operates in the low-atomicity message-passing asynchronous system model. Corona requires constant process memory space for its operation and, therefore, scales well. We prove the general necessary conditions limiting the initial states from which a self-stabilizing structured overlay network in a message-passing system can be constructed. The conditions require that initial state information has to form a weakly connected graph and it should only contain identifiers that are present in the system. We formally describe Corona and rigorously prove that it stabilizes from an arbitrary initial state subject to the necessary conditions. We extend Corona to construct a skip graph. Peer-to-peer systems are prone to faults, thus it is vitally important to design peer-to-peer systems to automatically regain consistency, namely to be self-stabilizing. Toward this goal, we present a deterministic structure that defines for every n the entire (IP) pointers structure among the n machines. Namely, the next hop for the insert, delete and search procedures of the peer-to-peer system. Thus, the consistency of the system is easily defined, monitored, verified and repaired. We present the HyperTree (distributed) structure which support the peer-to-peer procedures while ensuring that the out-degree and in-degree (the number of outgoing incoming pointers) are b log sub b N where N in the maximal number of machines and b is an integer parameter greater than 1. In addition the HyperTree ensures that the maximal number of hops involved in each procedure is bounded by log sub b N. A self-stabilizing peer-to-peer system based on the HyperTree is presented. Self-stabilizing distributed construction of expanders by the use of short random walks. We consider self-stabilizing and self-organizing distributed construction of a spanner that forms an expander. We advocate the importance of designing systems to be self-stabilizing and self-organizing, as designers cannot predict and address all fault scenarios and should address unexpected faults in the fastest possible way. We use folklore results to randomly define an expander graph. Given the randomized nature of our algorithms, a monitoring technique is presented for ensuring the desired results. The monitoring is based on the fact that expanders have a rapid mixing time and the possibility of examining the rapid mixing time by O(nlogn) short (O(log^4n) length) random walks even for non-regular expanders. We then use our results to construct a hierarchical sequence of spanders, each being an expander spanning the previous spander. Such a sequence of spanders may be used to achieve different quality of service (QoS) assurances in different applications. Several snap-stabilizing algorithms that are used for monitoring are presented, including: (i) Snap-stabilizing data-link, (ii) Snap-stabilizing message passing reset, and (iii) Snap-stabilizing token tracing.