Implementing ♢P with Bounded Messages on a Network of ADD Channels
Abstract
We present an implementation of the eventually perfect failure detector (♢P) from the original hierarchy of the Chandra-Toueg [3] oracles on an arbitrary partitionable network composed of unreliable channels that can lose and reorder messages. Prior implementations of ♢P have assumed different partially synchronous models ranging from bounded point-to-point message delay and reliable communication to unbounded message size and known network topologies. We implement ♢P under very weak assumptions on an arbitrary, partitionable network composed of Average Delayed/Dropped (ADD) channels [11] to model unreliable communication. Unlike older implementations, our failure detection algorithm uses bounded-sized messages to eventually detect all nodes that are unreachable (crashed or disconnected) from it.