ALPO stands for "ALPO is Like Paxos, except (hopefully) more Obvious". This is an experiment to try to define a protocol for managing a replicated log using distributed consensus, in a way that is easier to understand and more complete than Paxos.
Problems with Paxos
Paxos has existed for more than 20 years, is generally believed to be correct, and has been implemented numerous times. Thus it might seem silly to think about alternative algorithms. However, Paxos suffers from the following problems:
- In its purest form, as described by Lamport, it is incomplete. Basic Paxos guarantees safety, but (a) it does not deal with liveness issues (i.e. the algorithm may never terminate), (b) its data model consists of a single value, whereas real applications need to store a sequence of values, such as a log or state machine, and (c) it does not handle listeners (i.e., consensus may be reached but some of the parties may not realize that).
- Other people have extended Paxos to be more complete, but there seems to be no agreed-upon way to do this and the various descriptions are quite complicated and difficult to understand.
- Systems implementing Paxos all have reputations for being flaky or hard to use (though it's not clear whether this is because of Paxos).
- Even in its simplest form the algorithm is hard to understand; the extended versions are nearly impossible to understand, even for experts. There does not seem to exist a description of Paxos that is both complete and relatively easy for a wide audience to understand. For example, most graduate students are not capable of understanding the full Paxos algorithm as part of a graduate course in operating systems.