0
$\begingroup$

Link: https://dl.acm.org/doi/pdf/10.1145/3149.214121

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Apr 8, 2023 at 6:10
  • $\begingroup$ Can you articulate a more specific question? I'm having a hard time understanding what your question might be. $\endgroup$
    – D.W.
    Apr 8, 2023 at 6:11
  • $\begingroup$ 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. $\endgroup$ Apr 8, 2023 at 7:17
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Apr 8, 2023 at 8:26

2 Answers 2

0
$\begingroup$

I think the authors assume that the processes start with identical (or empty) internal storage. This seems a reasonable assumption: if the internal storage is arbitrary, a process that reads it could be correct by coincidence, or if it were random, then the process can succeed with a certain probability. And if the storage is a function of the input value, then the process might as well compute that function later.

$\endgroup$
0
$\begingroup$

My reading of

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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