UCLA

The field of distributed computability studies whether a task is solvable in a distributed system, as specified by communication channels, failure patterns, synchronization instructions, etc. Tasks are analogs of functions in distributed computing, which characterizes the coordination problems in a system with multiple processes. Processes start with an input value in a task and then communicate with others to decide an output value. Unlike classical computability theory, task solvability depends on the model of the system. Determining whether a task is solvable in a given model is usually argued on a case-by-case basis.

The celebrated asynchronous computability theorem (ACT) provides a topological characterization of task solvability in the wait-free model. Since the development of ACT, the topological method has achieved significant successes: ACT is generalized to models with additional synchronization objects and models of resiliency. The general theory of distributed computability, however, has still not been established. It is not clear whether ACT can be generalized for more general models.

In this dissertation, we study task computability in more general models. We show that every set-consensus collection model is equivalent to a vector-set-consensus model. For colorless task solvability, we derive ACT of the vector-set-consensus model. For colored tasks in the k-set-consensus model, we present an alternative formulation of ACT by introducing the notion of color-projection closed complex. For models specified by resiliency, we study the general adversary model and derive the “wait-atbeginning” ACT for colorless tasks. More specifically, we show that processes only need the full power of the adversary at the beginning of a colorless task protocol. We also present a sufficient topological condition to ensure that a task has a solution in the vector-set-consensus model. Specifically, we show that if the task output complex satisfies certain topological properties, it can be solved by the generalized convergence algorithm as a universal protocol.

Our generalizations of ACT show that many models are equivalent to “restricted” iterated immediate snapshot (IIS) models. Thus, this dissertation implies a potential general framework for distributed computing analogous to the “Church-Turing” thesis.