Consensus With at most m Crash Faults
State of Network:
- Reliable communication medium
- Synchronous system
- Fully connected
- The receiver always knows the identity of the sender of a message
Steps:
- At least m+1 rounds are needed to come to a consensus in such an environment.
- In 1st round broadcast your own value, and from successive rounds broadcast any new value that the node has received in the last round.
- Failure of a node may occur in between when it is sharing values with the other nodes. So if at most m nodes might get failed then in worst-case scenario one node failed every time when we are trying to achieve a consensus.
- And if every node goes through m+1 rounds then we are sure that out of these m+1 there will surely be at least one round when no node has failed and everyone gets every value.
- So after m+1 rounds, every node will select the minimum.
Consensus Problem of Distributed Systems
Consensus is a general agreement on a decision made by the majority of those involved. For example, the problem may be as simple as friends trying to decide which restaurant has multiple options to choose from or complex as decisions on distributed systems.