Deciding in Partitionable Networks

Abstract

Motivated by Chandra and Toueg's work, we study decision protocols in a model that closely approximates "real" distributed systems. Our results show how the weakest failure detector and associated consensus algorithm can be adapted to a network in which omission failures can occur during periods when processes suspect one-another as faulty. For protocols in which a majority subset of the participants can reach decisions on behalf of the system as a whole, we also characterize a series of stages that necessarily arise during execution. Jointly, these findings establish a direct relationship between an extended version of the three-phase commit protocol, which makes progress even when a traditional three-phase commit would block, and the consensus protocol of Chandra and Toueg. Although we do not explore the linkage here, our results should also be applicable to other agreement protocols for systems of this sort, such as leader election and dynamic group membership.