Capturing the power of resiliency and set consensus in distributed systems

Abstract

In an asynchronous distributed system, the solvability of a task depends on the communication model and on the resiliency of the system to failures. Up to now, determining whether a given task is solvable or unsolvable in a system has been approached in an ad hoc manner and often has proven quite difficult. To address this problem, I completely characterize task solvability in read-write shared memory in the presence of failures under two distinct fault models: the model of t-resiliency in which no more than t processors of the system will fail, and the active resiliency model in which a function of the number of active processors in the system may fail. I also generalize the characterization to encompass communication models that use set consensus objects in addition to shared memory. An (n,k)-set consensus object can be used by n processors to restrict the number of inputs to at most k values. In fact, the power of a model to narrow the number of input values (through the resiliency and the communication primitives) is the determining factor in the characterization. Thus, I prove a trade-off between the communication model and the failure model with respect to the power of the given system to solve (i,k)-set consensus for all i and k. To achieve this characterization, I present a simplified model of read-write memory, a simplex agreement algorithm that may be used as a universal distributed algorithm and a simulation technique that allows the results results derived in one model to be used in another. The tools and the characterization contribute to the development of a framework for understanding distributed computation.