For more up-to-date notes see http://www.cs.yale.edu/homes/aspnes/classes/465/notes.pdf.

Basic idea of an indistinguishability proof:

• Execution A is indistinguishable from execution B for some process p if p sees the same things (messages or operation results) in both executions.

• If A is indistinguishable from B for p, then p does the same thing in both executions.

So far, pretty dull. But now let's consider a chain of executions A = A₀ A₁ ... A_k = B, where A_i is indistinguishable from A_i+1 for some process p_i. Suppose also that we are trying to solve an agreement task, where every process must output the same value. Then since p_i outputs the same value in A_i and A_i+1, every process outputs the same value in A_i and A_i+1. By induction on k, every process outputs the same value in A and B, even though A and B may be very different executions.

This gives us a tool for proving impossibility results for agreement: show that there is a path of indistinguishable executions between two executions that are supposed to produce different output. Another way to picture this: consider a graph whose nodes are all possible executions with an edge between any two indistinguishable executions; then the set of output-0 executions can't be adjacent to the set of output-1 executions. If we prove the graph is connected, we prove the output is the same for all executions.

1. Coordinated attack

(See also LynchBook §5.1.)

This is a formalized (i.e. working) version of the TwoGenerals problem. We now have n >= 2 generals in a synchronous system with unreliable channels—the set of messages received in round i+1 is always a subset of the set sent in round i, but it may be a proper subset (even the empty set). Each general starts with an input 0 (retreat) or 1 (attack) and must output 0 or 1 after some bounded number of rounds. The requirements for the protocol are that, in all executions:

Agreement

all processes output the same decision (0 or 1).

Validity

If all processes have input 0, all processes produce output 0; if all processes have input 1 and no messages are lost, then all processes output 1. (In intermediate cases, processes can output 0 or 1 as long as they all agree.)

Termination

all processes terminate in a bounded number of rounds. (This can be relaxed to finite, since if every possible execution is finite in length there are only finitely many possible executions by König's lemma. The distinction is that "bounded" means there is a fixed upper bound on the length of any execution, while "finite but unbounded" means that any individual execution is finite, but there is no upper bound on all of them.)

Real-life motivation: distributed database commit: 0 input means I screwed up somehow and need to abort the transaction, 1 means I can go ahead with commit. It's better to abort than commit if the transaction may have failed, so we only require commit if nothing bad happens. Note that we could strengthen Validity to demand 0 output if there is any 0 input, but for a lower bound it's best to use the weakest restrictions on the algorithm we can.

It can be shown that no protocol satisfies all of Agreement, Validity, and Termination using an indistinguishability argument. The key idea is to construct a path between the all-0 input and the all-1 input with no message loss via intermediate executions that are indistinguishable to at least one process.

Let's start with A = A₀ being an execution in which all inputs are 1 and all messages are delivered. We'll build executions A₁, A₂ etc. by pruning messages. Consider A_i and let m some message that is delivered in the last round in which any message is delivered. Construct A_i+1 by not delivering m. Observe that while A_i is distinguishable from A_i+1 by the recipient of m, on the assumption that n >= 2 there is some other process that can't tell whether m was delivered or not (the recipient can't tell it, because no subsequent message it sends are delivered in either execution). Continue until we reach an execution A_k in which all inputs are 1 and no messages are sent. For the final steps, let A_k+1 through A_k+n be obtained by changing one input at a time from 1 to 0; each such execution is indistinguishable from its predecessor by any process whose input didn't change. It follows that if Agreement holds, then the common output in A₀ is the same as in A_k+n. But Validity requires that A₀ output 1 and A_k+n output 0: so Validity is violated.

2. Consensus with crash failures

Now let's look at a more complicated indistinguishability proof that doesn't require tossing out all messages. This proof is modeled on the one in LynchBook §6.7 and works backwards from the final state; for a proof of the same reslt that works in the opposite direction, see AttiyaWelch §5.1.4.

Consider the problem of synchronous consensus with crash failures (see SynchronousAgreement). Again we have inputs 0 and 1 and outputs 0 and 1 for each process.

A crash failure at process i means that (a) in some round r, some or all of the messages sent by i are not delivered, and (b) in subsequent rounds, no messages sent by i are delivered. The intuition is that i keels over dead in the middle of generating its outgoing messages for a round. Otherwise i behaves perfectly correctly. We will show that if up to f processes can crash, and we have at least f+2 processes total, then at least f+1 rounds are needed (in some execution) to achieve consensus. A process that crashes at some point during an execution is called faulty.

The requirements for consensus are

Agreement

All non-faulty processes output the same decision (0 or 1).

Validity

There exist failure-free executions A and B that produce different outputs.

Termination

All processes terminate in a finite number of rounds.

The Validity condition we will use is very weak; in practice, one might want something stronger like "if all processes have the same input x, all processes produce input x." But it's good enough to get the indistinguishability proof going. What we will show is that if all executions run in f or fewer rounds, then the indistinguishability graph is connected ⇒ Validity doesn't hold. (It's actually possible to weaken Validity still further to get rid of the requirement that A and B are failure-free, but we'll keep things simple.)

Now for the proof. To simplify the argument, let's assume that all executions terminate in exactly f rounds (we can always have processes send pointless chitchat to pad out short executions) and that every processes sends a message to every other process in every round where it has not crashed (more pointless chitchat). Formally, this means we have a sequence of rounds 0, 1, 2, ..., f-1 where each process sends a message to every other process (assuming no crashes), and a final round f where all processes decide on a value (without sending any additional messages).

We now want to take any two executions A and B and show that both produce the same output. To do this, we'll transform A's input into B's input one bit at a time, crashing processes to hide the changes. The problem is that just crashing the process whose input changed might change the decision value—so we have to crash later witnesses carefully to maintain indistinguishability all the way across the chain.

Let's say that a process p crashes fully in round r if it crashes in round r and no round-r messages from p are delivered. The communication pattern of an execution describes which messages are delivered between processes without considering their contents—in particular, it tells us which processes crash and what other processes they manage to talk to in the round in which they crash.

Lemma

For any f-round protocol permitting up to f crash failures, any process p, any execution A in which at most one processes crashes per round in rounds 1..r-1, p crashes fully in round r+1, and no other processes crash, there is a sequence of executions A = A₀ A₁ ... A_k such that each A_i is indistinguishable from A_i+1 by some process, each A_i has at most one crash per round, and the communication pattern in A_k is identical to A except that p crashes fully in round r.

Proof

By induction on f-r. If r = f, we just crash p in round r and nobody else notices. For r < f, first crash p in round r instead of r+1, but deliver all of its round-r messages anyway (this is needed to make space for some other process to crash in round r). Then choose some message m sent by p in round r, and let p' be the recipient of m. By the induction hypothesis, there is a sequence of executions starting with A and ending with p' crashing fully in round r+1 such that each execution is indistinguishable from its predecessor etc. Now construct the sequence A → (A with p' crashing fully in r+1) → (A with p' crashing fully in r+1 and m lost) → (A with m lost and p' not crashing). The first and last step apply the induction hypothesis; the middle one yields indistinguishable executions since only p' can tell the difference between m arriving or not and its lips are sealed. Now paste together n-1 such sequences (one per message) to prove the Lemma.

The rest of the proof: crash some process in round 0 and then change its input. Repeat until all inputs are changed.

---

CategoryDistributedComputingNotes