# How to interpret the concept of adjacent initial states in the FLP impossibility paper?

In the proof for Lemma 2, the authors define two initial states to be adjacent if the only difference between them is the value in the input register $$x_p$$ for a single process $$p$$. Then, they claim that any two initial configurations can be joined by a chain of initial configurations, each adjacent to the next.

However, if two initial states differ in the internal storage of a single process $$p$$, then there is no way to make them adjacent. The definition of initial state seems to include the internal state as suggested from the following excerpt.

The values in the input and output registers, together with the program counter and internal storage, comprise the internal state. Initial states prescribe fixed starting values for all but the input register; in particular, the output register starts with value b.

I know this doesn't change the point of the Lemma, as the decision value cannot depend solely on the internal state of some process in an initial configuration, but I was wondering what the authors intended with the precise definition of adjacent initial configurations.

• Can you add a proper citation to the paper you're referring to, including title, authors, where published, and if possible a link to a freely available PDF? This will help others who are interested find this page by search. It will also help understand what paper you're referring to.
– D.W.
Apr 8 at 6:10
• Can you articulate a more specific question? I'm having a hard time understanding what your question might be.
– D.W.
Apr 8 at 6:11
• The claim that any two initial configurations can always be joined by a chain of adjacent initial configurations does not seem to follow from their definitions. My question is what is the interpretation likely intended by the authors so that it follows from their definitions. Apr 8 at 7:17
• I encourage you to add a full a reference. A single link is not a substitute for a full citation, as indicated above. Thank you.
– D.W.
Apr 8 at 8:26

Initial states prescribe fixed starting values for all but the input register; in particular, the output register starts with value $$b$$.
on page 376 is that, for any consensus protocol $$P$$ considered in the paper, the program counter and the internal storage of every process $$p$$ are uniquely determined. Otherwise the proof of Lemma 2 does indeed not work.