Conference paper

Updates in Highly Unreliable, Replicated Peer-to-Peer Systems

In this paper we study the problem of updates in truly decentralised and self-organising systems such as pure P2P systems. We assume low online probabilities of the peers (<30%) and that the peers do not have global knowledge, but act based on local information only. Though probable in real-world systems such highly unreliable distributed scenarios have not been addressed properly in either the database or distributed systems literature yet. Our update strategy which is based on a hybrid push/pull rumor spreading algorithm takes into account these requirements. The goal of the update algorithm is to devise a fully decentralised, efficient and robust communication scheme which provides probabilistic guarantees rather than ensuring strict consistency. For demonstrating its efficiency, we do not rely on simulation results as it is done traditionally for epidemic algorithms; instead we use a generic analytical model to investigate the utility of our hybrid update propagation scheme from the perspective of communication overhead. The major contribution of the work presented in this paper are the generic analytical model and the proposal of feed-forward epidemic rumor spreading schemes as an appropriate mechanism for update propagation. An important application of our update propagation method is consistency maintenance in distributed, scalable data access structures, as used for example in P2P systems, bulletin-board systems, or shared calendars. Full Document

Related material