Acropolis: aggregated client request ordering by Paxos

Abstract

The consensus problem is one of the most central problems in distributed system. Paxos, an algorithm that solves this problem, can be used to im- plement replicated state machines (RSMs). By running Paxos for each of the commands received by each of the state machines, the replicas making up the system will maintain the same state. This architecture allows us to create fault-tolerant systems. This thesis introduces Acropolis, which takes its inspiration from the Paxos algorithm and is used to create an RSM. In Acropolis, the clients are responsible for disseminating the request content, while Acropolis itself operates only on content metadata – making it a good candidate in WAN situations. Acropolis also pushes the proposers in Paxos out to the clients, removing some of the leader bottleneck associated with some Paxos-variants. Initial results show that Acropolis provides good time to execution latency – the time from a replica receiving a request to just before it gets executed – an indicator that it will perform well in situations where the replicas are spread over large distances.