The Part-Time Parliament
Leslie Lamport

This paper describes an algorithm for "passing decrees" in a
distributed system with unreliable components and messages.  In
general Byzantine failure is not treated (see below).  As an aside, I
actually found the style of presentation pleasant.  I had little
difficulty evaluating the algorithm in a distributed-systems context,
largely because it was always clear that this would make a silly
algorithm for a real parliament.  Although I was able to figure it
out, it might have been made more clear that the ledger (including the
notes on the back) needs to be implemented as stable storage, while
the loose notes can be volatile (one thing I couldn't discern,
however, is whether they can be true soft-state, evicted at any time,
or if they may be lost only in the case of a failure, i.e. when a
legislator leaves the chamber).

One important thing to recognize in parsing the paper is that voting
in this context is less about expressing opinions about what the
decrees should be (since the Paxons were in principle always willing
to pass any decree), than it is about ensuring that there is a
consistent view of what happened.  

Perhaps the most important observation is that two majorities of any
set always contain at least one member in common.  This is the heart
of the definition of majority, and is why the weight-based rules were
just as effective as the count-based rules.  I would also point out
that this is exactly what is encoded by synod rule B2.

Turning the presentation around, we start by noticing that the
parliament problem (which is just the reliable event ordering problem)
can be broken down into a series of single-resolutions, as long as we
include a numbering in the statement of the resolution itself.  So the
algorithm that is described in detail works for only a single
resolution, such that, once it is adopted, everyone agrees on the text
of the resolution.  Besides consistency, we also want to show that
forward progress is made (or at least understand the necessary
conditions) so that some resolution is eventually reached.

This synod protocol itself involves a series of votes, where various
members propose possible resolutions and try to get a majority of the
other members to vote for their proposal.  There are three consistency
rules, but all the heavy lifting is done by the rather interesting
rule B3.

First though, the basic process.  The neat thing here is that we delay
as long as possible the determination both of what the value of a
resolution is and who will need to vote for it to pass it.  A member
who wants to propose a vote collects conflict information from the
other members, and then selects a proposal and a quorum that he
believes will be able to pass the proposed resolution.  If all the
members of the quorum agree, the resolution is adopted.

I might mention that B3 was not at all what I intuitively expected it
to be, and as a result it took me a while to properly understand it.
The basic purpose is to make sure that no member is ever asked to vote
for a resolution in conflict with earlier votes.  When combined with
the majority property above, we will be able to prove that we can
never have different members believe a different result was reached.

Formally, B3 states that, if any proposed quorum members have voted
for previous votes (note the difference between being in a quorum and
having voted for a measure), then the proposed resolution must match
the most recent of those earlier votes.  However, members who voted
for even earlier votes (not the most recent) are off the hook.

One interesting observation about rule B3:, if someone votes for a
ballot B, and then later is asked to vote for a ballot B' with a
different decree (asked to vote meaning is made part of the quorum),
then that informs that participant absolutely that ballot B failed.
This is directly tied to the argument that if multiple votes succeed,
then they must pass identical resolutions.


One thing that I enjoyed about the paper, particularly as it starts
discussing the complete parliament algorithm, is the extent to which
it hits on all the practical issues.  These include performance
enhancements such as selecting a president and conducting the
information-gathering steps of the synod algorithm only once for
multiple resolutions.  But also discussed are issues like selecting
and replacing members, and to some extent dealing with errors (mostly
just by periodically refreshing resolutions to self-stabilize the
system).  The final group of systems issues touch on effectively
disseminating resolution information to "the masses" who don't
participate in the parliament, and the natural extension to "fast
read" and "slow read" in a database system, where "slow reads" ensure
serialization and ordering for a few important external interactions,
and "fast reads" allow easy access for non-critical operations.


As a parting interesting note, I enjoyed the part where they talk
about what is known to the members, and what is known only to the
gods.  Thus in a theoretical sense we can talk about the instant that
a resolution is adopted, even though nobody in the system can tell
when that is, and in fact the notion isn't even well defined from the
members' point of view.  

I think that this is where the impossibility results crop up, because
the members can't ever know when (or if) everyone knows the truth.
But the point of the algorithm is only to create the truth (where
"truth" means, by definition, anything with the property that there
can never be two different "truths").


Andy