Deterministic Sharing of Distributed Resources

Abstract:

Deterministic performance is desirable for many distributed applications, from vehicle control systems to financial networks. The trouble is that infrastructure for these applications must incorporate multiple independent timing sources, because uniform distribution of timing signals is only possible at small scales, such as for integrated circuits. To formally reason about the behavior of concurrent computations in large distributed systems, the nondeterminism created by independent timing must be eliminated. This dissertation proposes metasynchronization, a technique to uniformly time division all resources in distributed systems that span multiple timing domains. This allows for deterministic execution of and interaction between distributed computations, analogous to the deterministic behavior of components in synchronous integrated circuits. Such determinism allows formal correctness verification of computations with strict performance requirements. It also allows perfect virtualization of distributed resources, meaning a system where computations are unable to determine if they are executing on raw physical resources or within a virtualized environment. Nondeterminism makes perfect virtualization impossible for conventional systems. Metasynchronization creates the necessary determinism, and this dissertation proposes an execution model called hierarchical provisioning, which incorporates perfect virtualization, and thereby allows distributed computations to share resources deterministically. Importantly, metasynchronization creates uniform timing without distributing a centralized timing signal. Instead, all timing domains reach agreement on shared time in a fully decentralized self-stabilizing manner that requires no communication overhead, but does depend on small buffers and simple ongoing numerical computations for each communication link. Because of its decentralization, metasynchronization is highly robust, tolerating multiple simultaneous malicious (Byzantine) failures under normal circumstances.