Distributed construction of peer-to-peer system with 2-lifts graph
Le, Anh N
MetadataShow full item record
Unstructured Peer-to-peer (P2P) systems often require that a random graph with some desirable properties should be constructed. The properties which the designers of protocols would like to ensure are connectivity, low degree and small diameter of the network. Although expander graphs which has these properties have been studied extensively, distributed construction and maintenance of expander networks remains a challenging problem. In this thesis, we first evaluate the different distributed construction of expander graph for unstructured P2P network. Then, we present a new distributed algorithm for construction and maintenance P2P networks topology using "2-lift" operations. The basic idea is to construct and maintain a expander network which includes a capable and stable peers as a core backbone. Then, peers are added and/or removed from the core backbone so that it is still a expander graph with an arbitrary large number of nodes. Using simulation, we show that our approach achieves substantial improvement in load balance, very reliability and very low cost overhead.