HyperTree for self-stabilizing peer-to-peer systems

Abstract

Peer-to-peer systems are prone to faults; Therefore, it is extremely important to design peer-to-peer systems that automatically regain consistency or, in other words, are self-stabilizing. In order to achieve the above, we present a deterministic structure that defines the entire (IP) pointers structure among the machines, for every n machines; i.e., defines 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 supports the peer-to-peer procedures while ensuring that the out-degree and the in-degree (the number of outgoing/ incoming pointers) are b log b n where n is the actual number of machines and b is an integer parameter greater than 1. Moreover, the HyperTree ensures that the maximal number of hops involved in each procedure is bounded by log b n. A self-stabilizing peer-to- peer distributed algorithm based on the HyperTree is presented. © 2007 Springer-Verlag.