HyperTree for selfstabilizing peertopeer system

Authors: Shlomi Dolev Ronen I Kat

Publish Date: 2007/08/15

Volume: 20, Issue: 5, Pages: 375-388

PDF Link

Abstract

Peertopeer systems are prone to faults Therefore it is extremely important to design peertopeer systems that automatically regain consistency or in other words are selfstabilizing 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 ie defines the next hop for the insert delete and search procedures of the peertopeer system Thus the consistency of the system is easily defined monitored verified and repaired We present the HyperTree distributed structure which supports the peertopeer procedures while ensuring that the outdegree and the indegree 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 selfstabilizing peerto peer distributed algorithm based on the HyperTree is presentedThis work was partially supported by IBM Faculty Award NSF Grant 0098305 the Israeli Ministry of Trade and Industry the Rita Altura Trust Chair in Computer Sciences and the Lynne and William Frankel Center for Computer Sciences The work was done while Ronen I Kat was a PhD student at BenGurion University of the Negev An preliminary version was published in the proceedings of the third IEEE International Symposium on Network Computing and Applications NCA’04

Keywords: