Toward Robust High Performance Distributed Services

This thesis presents steps towards simplifying the implementation of robust high performance distributed services. First, we investigate consensus algorithms in the context of fault tolerant systems. Consensus algorithms, often a critical part of fault tolerant systems, are notoriously difficult to implement. We present a skeleton consensus algorithm that can be instantiated into several well-known consensus protocols, providing insight into the structure of consensus algorithms as well as the differences and performance tradeoffs between different algorithms. We investigate onestep Byzantine agreement algorithms which exploit contention-free situations to provide low latency performance. We present definitions of one-step algorithms and prove a lower bound on the number of processors required for such algorithms, thereby showing that our algorithm is optimal. We then generalize our investigation to k-set agreement. Second, we present RPC chains, a communication primitive that improves the performance of geodistributed enterprise applications. Distributed enterprise applications are often built as a composition of more basic services. Currently, such compositions are built using remote procedure calls (RPCs). This results in a rigid and inefficient communication pattern. RPC chains is a new ion that applies two well-known ideas, function shipping and continuations, to allow an improvement in the latency performance and reduction in the overall bandwidth usage of such geodistributed systems