3
$\begingroup$

I try to get a better understanding about Failure Detectors in the field of Distributed Computing.

Let consider the algorithm for reaching consensus with Perfect Failure Detector, it's named as Perfect FDAgreement in the textbook Distributed Algorithms by Nancy A. Lynch on the page 679. In addition, it can be found in the following presentation Asynchronous Network Computing with Process Failures. Slide 16.

The basic idea of the algorithm is each process $P_i$ attempts to stabilize two pieces of data: a vector val, indexed by $\{1,2,...,n\}$, with values in $V \cup \{null\}$.$val(j) = v \in V$, it means that $P_i$ knows that $P_j$’s initial value is $v$. A set stopped of process indices. If $j \in stopped$, it means that $P_i$ knows that $P_j$ has stopped.

The question is as one of the step of the algorithm every process that receive a message ignores it from the processors it has already placed in stopped.

I don't understand why we need this, even we don't ignore the message from stopped process it won't broke anything. This case may occur when $P_j$ sends a message to $P_i$ and crashes, FailureDetector see the crash and informs the process $P_i$ that $P_j$ is stopped after that $P_j$'s message reaches $P_i$, but this message contains a correct data, and it doesn't change the state of $P_j$ in stopped set, because only INSERT (insert new values that previously was null) and COMPARE are allowed operations on the set.

If you see the real reason for ignoring messages from the crashed process please share it with us.

Addendum: Unfortunately I didn't find any use of the aforementioned fact (ignoring message from crashed node) in the algorithm (Perfect FDAgreement in the textbook Distributed Algorithms by Nancy A. Lynch).

In addition, in main papers Tushar Deepak Chandra and Sam Toueg. Unreliable failure detectors forasynchronous systems and Tushar Deepak Chandra, Vassos Hadzilacos, and Sam Toueg. The weakest failure detector for solving consensus slightly different algorithm can be found without ignoring messages from crashed nodes.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

It could be that the analysis works either way, or perhaps the analysis (or the algorithm) could be slightly modified to handle this change. I suggest you go over the correctness proof of the algorithm and see where this step is used (if at all).

Improve this answer
$\endgroup$
2
  • $\begingroup$ I tried, proof in the textbook doesn't mention the fact of ignoring, proof in relevant papers are slightly different but also don't use it. $\endgroup$
    – user16168
    Jul 8, 2013 at 7:25
  • $\begingroup$ If the proof works even without this step, then it's not needed. Try it out. $\endgroup$
    – Yuval Filmus
    Jul 8, 2013 at 15:50

Your Answer

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

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