Distributed highly available search trees
Konrad Schlude, Eljas Soisalon-Soininen, Peter Widmayer · Repository for Publications and Research Data (ETH Zurich) · 2001
We propose a distributed dictionary that tolerates arbitrary single server crashes. The distinctive feature of our model is that the crash of a server cannot be detected. This is in contrast to all other proposals of distributed fault tolerant search structures presented thus far. It reflects the real situation in the internet more accurately, and is in general more suitable to complex overall conditions. This makes our solution fundamentally dierent from all previous ones, but also more complicated. We present in detail the algorithms for searching, insertion, and graceful recovery of crashed servers.