A first node determines that a health of a second node that is the accepted leader is invalid and calculates a third proposal number for a proposal of an election for a leader. The first node sends first messages with the third proposal number to nodes to propose the election and determines that a first quorum for a third variable is reached indicating the election for the leader is accepted. The first node sends second messages with a fourth proposal number based on the first proposal number and an identifier for a proposed leader to the nodes to propose the proposed leader as the leader of the nodes. The second messages reject the proposed leader when the proposed leader is equal to the fourth variable. The first node determines that a second quorum is reached from a set of second responses that include the fourth proposal number for the second variable.