I am reading the classic paper by Fisher, Lynch, Merritt "Easy impossibility proofs for distributed consensus problems", and cannot understand the model they are using. It seems it was already standard at that time and therefore the authors didn't describe it in detail. And because I don't understand the model, I also don't understand the proofs. In particular, I was reading the impossibility proof for byzantine agreement for the case $n=3$ and $m=1$ (Section 3.1), and while I understand the individual steps of the proof, and don't see the overall structure of the proof. Why compare the scenarios of $S$ with the scenarios of $G$? The following phrase seems to be key: "We argue that each of these scenarios is identical to a scenario in a correct behavior of $G$". However, I cannot see its role in the proof.

In summary, I have the following questions:

  1. Where is the model used in the paper described in more detail? (online resources would be appreciated)

  2. What is a node/edge behavior? (This notion is not defined in the paper.)

  3. It is said that a system has a single behavior. Why is that? (In my view, the behavior also depends on the scheduling of messages, which is not modeled by the system.)

  4. What is the intuitive meaning of a graph covering in the context of distributed computations?

  5. What is the structure of the proof in Section 3.1 and the intuition behind it?

  • $\begingroup$ The model in the paper seems pretty clear to me. Maybe your problem is that you do not see how it relates to concrete models that you have in mind, like asynchronous message-passing. I was also confused, not by the description of the model, which is clear, but by what real system it is supposed to model. Maybe you could think of it as modeling a synchronous system (which has a single behavior given fixed inputs). Btw. both Lynch and also Attiya and Welch have some variants of this proof in their books. $\endgroup$ – nano Dec 9 '18 at 9:54

Your Answer

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

Browse other questions tagged or ask your own question.