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.
Probabilistic approaches like ours have the advantage of better graph properties (e.g., a logarithmic expansion) compared to deterministic variants (e.g., @cite_17 ).
@cite_17
2061086123
In this paper we study the problem of designing searchable concurrent data structures with performance guarantees that can be used in a distributed environment where data elements are stored in a dynamically changing set of nodes. Searchable data structures are data structures that provide three basic operations: I NSERT , D ELETE , and S EARCH . In addition to searching for an exact match, we demand that for a data structure to be called "searchable", Search also has to be able to search for the closest successor or predecessor of a data item. Such a property has a tremendous advantage over just exact match, because it would allow to implement many data base applications.We are interested in finding a searchable concurrent data structure that has (1) a low degree, (2) requires a small amount of work for I NSERT and D ELETE operations, and (3) is able to handle concurrent search requests with low congestion and dilation.We present the first deterministic concurrent data structure, called Hyperring, that can fulfill all of these objectives in a polylogarithmic way. In fact, the Hyperring has a degree of O(log n), requires O(log3 n) work for I NSERT and D ELETE operations, and can handle concurrent search requests to random destinations, one request per node, with congestion and dilation O(log n) w.h.p.Most of the previous solutions for distributed environments are not searchable (in our sense) but only provide exact lookup, and those that are searchable do not have proofs about the congestion caused by concurrent search requests.