0
$\begingroup$

Consider a t-resilient read-write shared memory system (0 < t < N) with initial failures only: faulty processes take no steps. How could one give a consensus algorithm in this system? I don't understand why the proof of the consensus impossibility doesn't work in this case?

$\endgroup$
0
$\begingroup$

There are two questions here. Let me start with the second: "I don't understand why the proof of the consensus impossibility doesn't work in this case?".

First, I do not know what proof you are talking about. I suppose you are referring to a proof that consensus is not solvable in a t-resilient SWMR system when $0<t<N$.

If $t<N-1$, the easiest way I know to prove this fact it to reduce t-resilient SWMR consensus to $(N-1)$-resilient consensus (i.e. wait-free consensus). This is done via the BG Simulation, which allows $t+1$ wait-free processors in a SWMR system to simulate a t-resilient SWMR system. The BG simulation does not work if failures are initial. Thus this is where the proof fails when $0<t<N-1$.

Now, let us consider $t=N-1$. In this case, one way to prove the impossibility of consensus is to use the critical-state argument. Let me explain why the critical-state argument does not apply if failures are initial only.

The key is that, in a wait-free SWMR algorithm, there are only finitely many executions given a fixed number of processors (this is a consequence of Koenig's lemma: infinite executions are not allowed and the execution tree is finitely branching, thus the execution tree is finite). In consequence, the set of continuations of an execution prefix is finite, and thus by repeatedly increasing the length of the prefix (and thus ruling out more and more continuations) we eventually arrive at a point at which all remaining continuation have the same consensus outcome. By removing one step from this prefix we have our critical state (assuming that the outcome was not predetermined by the inputs).

If we now assume that failures are initial only, we have to allow busy loops in which a processor reads until it sees a particular processor that it saw before, or otherwise we cannot take advantage of the fact that failures are initial only. Thus, for any n, we have executions that exceed length n (e.g. when a processors polls n times when busy-waiting for another). Thus we now have infinitely many executions, and the reasoning used above to justify the critical-state argument does not apply anymore.

Now, let me answer your first question: "How could one give a consensus algorithm in this system?"

One way to do it is to use a "doorway": take a MWMR register initialized to 0, called the doorway register, and have all processors (a) announce their participation, then (b) read the doorway register, then (c) close the doorway by setting the doorway register to 1, and then (d) announce whether they successfully entered the doorway (i.e. whether they read 0). Finally, a processor (e) takes a snapshot, (f) waits for all processors it sees are participating to announce whether they successfully entered the doorway (using a read loop), and (g) outputs the value of the processor that has the max identifier among those who entered the doorway (any other deterministic function can be used instead of max).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.