25th IEEE Symposium on Reliable Distributed Systems (SRDS'06)
Decentralized Local Failure Detection in Dynamic Distributed Systems
Leeds, United Kingdom
October 02-October 04
ISBN: 0-7695-2677-2
A failure detector is an important building block when constructing fault-tolerant distributed systems. In asynchronous distributed systems, failed processes are often indistinguishable from slow processes. A failure detector is an oracle that can intelligently suspect processes to have failed. Different classes of failure detectors have been proposed to solve different kinds of problems. Almost all of this work is focussed on global failure detection, and moreover, in systems that do not contain mobile nodes or include dynamic topologies. In this paper, we present 3Pm a local failure detector that can tolerate mobility and topology changes. This means that 3Pm can distinguish between a failed process and a process that has moved away from its original location. We also establish an upper bound on the duration for which a process wrongly suspects a node that has moved away from its neighborhood. We support our theoretical results with experimental findings from an implementation of this algorithm for sensor networks.