Dynamic & fault-tolerant P2P-topologies
Stefan Schmid · Repository for Publications and Research Data (ETH Zurich) · 2004
Until now, the analysis of fault tolerance of peer-to-peer (p2p) systems usually only covers random faults of some kind.Contrary to traditional algorithmic research, faults as well as joins and leaves occurring in a worst-case manner in p2p systems are hardly considered.Most fault tolerance analyzes are static in the sense that it is shown that a system tolerates a certain number of simultaneous faults.The much more realistic dynamic case where faults steadily occur has not found much attention.The goal of this thesis is to work towards a general understanding of fault tolerance especially for the case of dynamic and worst-case failures.The thesis introduces a simple dynamic model where a malicious adversary -controlling the arrivals and departures of the peers -and a repairing algorithm take turns.The insights gained from this model are then used to study the more realistic scenario where a repairing algorithm maintains certain properties of the topology against a concurrent adversary.Besides the comparison of different fault-tolerance models, the thesis presents a distributed hash table which maintains an efficient search structure as well as a low peer degree in spite of the worst-case failures.By a dynamic analysis we prove that no data item is lost by the system.