Every paper on Byzantine fault tolerance introduces a new kind
of data consistency. This new type of consistency will have an
ostensibly straightforward yet practically inscrutable name
like “leap year triple-writer dirty-mirror asynchronous semiconsistency.”
In Section 3.2 (“An Intuitive Overview”), the
authors will provide some plainspoken, spiritually appealing
arguments about why their system prevents triple-conflicted
write hazards in the presence of malicious servers and unexpected
outbreaks of the bubonic plague. “Intuitively, a malicious
server cannot lie to a client because each message is an encrypted,
nested, signed, mutually-attested log entry with pointers to
other encrypted and nested (but not signed) log entries.”
Interestingly, these kinds of intuitive arguments are not intuitive.
A successful intuitive explanation must invoke experiences
that I have in real life. I have never had a real-life experience
that resembled a Byzantine fault tolerant protocol. For example,
suppose that I am at work, and I want to go to lunch with some of
my co-workers. Here is what that experience would look like if it
resembled a Byzantine fault tolerant protocol:
JAMES: I announce my desire to go to lunch.
BRYAN: I verify that I heard that you want to go to lunch.
RICH: I also verify that I heard that you want to go to lunch.
CHRIS: YOU DO NOT WANT TO GO TO LUNCH.
JAMES: OH NO. LET ME TELL YOU AGAIN THAT I WANT
TO GO TO LUNCH.
CHRIS: YOU DO NOT WANT TO GO TO LUNCH.
Figure 2: Our new protocol is clearly better.
 | MAY 2013 | WWW.usenix.org PAGE 4
The Saddest Moment
BRYAN: CHRIS IS FAULTY.
CHRIS: CHRIS IS NOT FAULTY.
RICH: I VERIFY THAT BRYAN SAYS THAT CHRIS IS
FAULTY.
BRYAN: I VERIFY MY VERIFICATION OF MY CLAIM THAT
RICH CLAIMS THAT I KNOW CHRIS.
JAMES: I AM SO HUNGRY.
CHRIS: YOU ARE NOT HUNGRY.
RICH: I DECLARE CHRIS TO BE FAULTY.
CHRIS: I DECLARE RICH TO BE FAULTY.
JAMES: I DECLARE JAMES TO BE SLIPPING INTO A
DIABETIC COMA.
RICH: I have already left for the cafeteria.