Any two processes that decide must decide on the same value.
All processes eventually decide.
A number of solutions to the consensus problem exist. All initialized and non-failed processes eventually decide. It is a complex algorithm which uses a sophisticated shared coin-flipping protocol. Achieving polynomial expected time depends in an essential way on ensuring that the probability that all non-failed processes draw the same value is above an appropriate bound. Many of the correctness requirements are non-probabilistic, and can be discharged with a conventional model checker.