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.

An Automated Market Maker (AMM) is a smart contract created to allow the exchange of assets according to a mathematical function defined in the contract. As the exchanges occur, if they start to deplete one of the assets held by the contract, we would like to increase the relative price of the asset being depleted. On the other hand, when the balances of the assets are not too far from each other, we would like the relative price of the assets to stay as close to a constant as possible.

These two competing wishes were handled by creating a formula consisting of the weighted sum of two functions: one taking care of the neighborhood of the starting point and the other under the condition when the assets diverge significantly.

We propose an ultimate compromise: a straight line in the neighborhood, and the translated original function that treats all points on the function the same without a specific bias when the assets diverge.

We present in detail the case of two assets, and we propose (without analysis) a generalization of the construction to the multi-asset case.