Patent ID: 7565433

Claim:
A method for selecting a value in a distributed computing system, the method comprising: transmitting, from a leader device in the distributed computing system to a first quorum of devices in the distributed computing system, a proposed value and a proof of safety, wherein the proposed value is proposed in a proposal having a proposal-identifying proposal number, and wherein the proposed value and the proof of safety are authenticated for the first quorum of devices; receiving, at the leader device in the distributed computing system from a second quorum of devices in the distributed computing system, a quorum of acceptance messages indicating an acceptance of the proposed value, wherein the acceptance messages are authenticated from the second quorum; and transmitting, from a leader device in the distributed computing system to a subset of the devices in the distributed computing system, a selection message, indicating that the proposed value was selected, and a proof of the selection, wherein the selection message and the proof of the selection are authenticated for the subset of the devices, wherein the leader device is in the distributed computing system, but is not part of either the first or the second quorums of devices in the distributed computing system, wherein the transmitting the proof of safety comprises forwarding, from the leader device in the distributed computing system, a received quorum of safe value messages, wherein the safe value messages are properly authenticated from a quorum of devices in the distributed computing system, and wherein the safe value messages contain a previously voted for value if the previously voted for value was previously voted for by at least one device in the distributed computing system.