A Solution for the Consensus Problem in a Mobile Environment


Raimundo Macêdo
Laboratório de Sistemas Distribuídos(LaSiD) - CPD/UFBA



The consensus padadigm can be used as a building block for solving a number of practical agreement problems in distributed computing, such as Atomic Broadcast, Non-Blocking Atomic Commitment or View Synchrony. Unfortunately, the consensus problem has no deterministic solution in an asynchronous distributed system that is subject to even a single processcrash failure. Among the solutions proposed to circumvent this impossibility result, the concept of unreliable failure detectors proposed by Chandra and Toueg is particularly attractive. They defined a protocol that solves the consensus problem when the assumption that the underlying failure detector belongs to the class <>S holds true. Efficient solutions to practical agreement problems can be obtained by changing the validity property which characterized the original consensus problem. That is, the Chandra-Toueg's protocol can be extended to cope with new definitions of the validity property. In this talk we present an extension of their protocol allowing this fundamental agreement problem to be solved in a mobile environment. In such an environment, the problem is more challenging: based on their initial states, a set of mobile hosts must agree on a common decision despite disconnections, changes of location and failures of mobile/fixed hosts.