Toward a Unified, Hierarchical Ontology of Consensus Proofs in Autonomous Distributed Computing

Abstract

Distributed systems studies the ways in which individual systems behave as a group and is often a result of convergent evolution in many fields of study which seek to understand consensus: how the behavior of systems within a group emerges into singular actions by the group.Practitioners in distributed computing (a subset of distributed systems) often try to integrate consensus mechanisms from other fields, seeking improvements in performance and security properties, but the wide variety of origins also makes these mechanisms difficult to compare. There are no existing works which attempt to reconcile the differences between such consensus mechanisms in a clear, communicable fashion without the requirement for additional tooling (e.g., formal methods)---a limitation which this work seeks to correct. Consensus theory across distributed systems relies on the idea that a collection of autonomous systems may, together, take possible actions with or without the involvement of all members.This idea captures the three primary properties to modern consensus in distributed computing: termination, validity, and agreement. The types of consensus algorithms in distributed computing are characterized by synchrony, permissions or privacy, and fault tolerance. The first portion of this thesis discusses the correlations of synchrony and termination, permissions and validity, and fault tolerance and agreement. The original intention for this work was to remedy the divisions in consensus by developing three hybrid consensus mechanisms which enabled multiple algorithms across the primary properties, respectively.While these hybrid consensus mechanisms would have helped establish a common language for the field, these mechanisms, ironically, could not be proven in the general case without a common language. As a result, the need for a common language could only be fulfilled by a basis for the foundational structure, which this work adapts from the philosophical field of metametaphysics. Therefore, the second portion of this work directly addresses the problem defined in its title by presenting a usable methodology. Finally, the latter portions provide the original intended works, then explain and describe usability of the adapted philosophy, along with potential next steps for formalized standardization.