patternMinor
Is this simplified consensus problem easier than the original?
Viewed 0 times
thissimplifiedproblemtheoriginalthanconsensuseasier
Problem
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?
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?
Solution
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).
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).
Context
StackExchange Computer Science Q#12043, answer score: 4
Revisions (0)
No revisions yet.