3
$\begingroup$

There is a famous Consensus Problem in Distributed Computing.

Let's consider and try to find the best possible algorithm for a simplified version of the consensus problem.

Assumptions: a process may undergo only crash failure (process abruptly stops and does not resume), process represent a complete graph.

Simplification: a crash failure may occur only between round, so there no a case when a process succeeds in sending some message and fails to send other message during the same round.

The algorithm for the general case FloodSet when a process may crash during the round is described in Distributed algorithms - Nancy Ann Lynch. By the analysis it was shown that $f+1$ rounds is enough to reach a consensus.

Intuitively, it looks like that the simplification completely changes the approach to the solution. It is may be enough just one round, every processes send an input message to every other processes and agree on the minimal value.

What is the simplest possible algorithms for simplified problem ?

What can we do in the case of general graph?

$\endgroup$
4
$\begingroup$

What you're describing as simplified problem is usually called consensus with clean crashes. You can just compute the maximum of all received messages once. To see that this is sufficient, observe that everyone receives the exact same messages after the first round. Thus everyone agrees on the same maximum value and all nodes decide correctly.

To solve crash-fault consensus on a general graph you need to assume $(f+1)$-connectivity. Then you could simulate each round of the FloodSet algorithm by flooding through the entire graph (taking $D$ rounds), yielding $D(f+1)$ rounds in total. I would be surprised if there's a more efficient way to do this (without additional assumptions on the graph, .e.g., high expansion).

$\endgroup$
1
  • $\begingroup$ Thank you very much for the answer! You are right. intuitively, it seems like there is no deterministic algorithm in the case of general graph. Can you suggest where I can take a look for proof (of non-existence of deterministic algorithm)? $\endgroup$
    – com
    May 17 '13 at 8:21

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.