Atomic Ring Maintenance for Distributed Hash Tables

Ghodsi, Ali and Haridi, Seif (2007) Atomic Ring Maintenance for Distributed Hash Tables. [SICS Report]



This paper provides algorithms to maintain a ring-structure for structured peer-to-peer systems. The algorithms guarantee consistent lookup results in the presence of joins and leaves, regardless of at which node the lookup is initiated. Every join and leave event appears as if it happened atomically, thus guaranteeing that lookup results will be the same as if no joins or leaves took place. The ring maintenance algorithms guarantee that no routing failures occur as nodes are joining and leaving. We also show that lookup consistency is impossible to provide given failure detector, and show how the algorithms can be extended to handle failures. The correctness of all the provided algorithms is proven. Previous approaches to this problem either assume a fault-free environment, or have no proof of correctness.

Item Type:SICS Report
ID Code:2582
Deposited By:Vicki Carleson
Deposited On:08 Nov 2007
Last Modified:18 Nov 2009 16:11

Repository Staff Only: item control page