- Only a single value can be chosen
- Only a value that has been proposed can be chosen
- A process can learn that a value is chosen only after it’s chosen
- Some proposed value is eventually chosen
- If a value is chosen, a process eventually learns it
- If you have a consenus algorithm, it’s pretty easy to apply it in order to create a reliable totally-ordered broadcasting algorithm
- Vice-versa, if you have a total-ordered algorithm then it’s easy to apply to a consensus algorithm
- The IS-IS algorithm has consensus
- https://medium.com/@etherpan/paxos-made-simple-for-real-aa221be7d91b
- https://lamport.azurewebsites.net/pubs/paxos-simple.pdf
- Proposer
- Acceptor
- Learner
unique ID = local serial counter + “.” + node ID
- Proposer sends a “propose” message to all Acceptors containing its proposed value and a unique proposal number.
- In response, each proposer replies to the proposer with an already accepted value and proposal number. If it doesn’t have a accepted value it sends back a special value “No accepted value”. The proposers should then receive a majority accepted value. If it doesn’t, it should resend the proposals.
- ( TOO MUCH TO WRITE. get it from epstein’s lecture notes )
Proposer sends message to acceptors Proposer sends accept message to acceptors -> Acceptors “promise” not to accept any proposals lower than the accepted value
- P1. An acceptor must accept the first proposal it receives
- P2. If a proposal with value V is chosen, then every higher-numbered proposal that is chosen has value V
- P2A. If a proposal with value V is chosen, then every higher-numbered proposal accepted by any acceptor has value V
- P2B. If a proposal with value V is chosen, then every higher-numbered proposal issued by any proposer has value V.