Patent ID: 7797457
Filing Date: 2010-09-14
Classification: G06F,H04L

Abstract:
1. A method of providing for a virtual leader for consensus in a distributed computing system, wherein the system comprises servers and clients, the method comprising: executing at least one virtual leader agreement algorithm in each server of a plurality of servers in the distributed computing system; determining at each server of the plurality of servers in the distributed system what message a leader in an asynchronous consensus algorithm should propose as the leader message; sending by each server of the plurality of servers in the distributed system the message proposed as the leader message to each of the other plurality of servers in the distributed system; combining the proposed leader messages at each server of the plurality of servers in the distributed system to generate a plurality of proposals; sending the plurality of proposals to the virtual leader agreement algorithm in each server of the plurality of servers in the distributed system; receiving the plurality of proposals at each virtual leader agreement algorithm in each server of the plurality of servers in the distributed system from each of the other plurality of servers in the distributed system; determining the leader message from the received plurality of proposals; and each server behaving as if it received the leader message from the leader, wherein determining the leader message from the received proposals comprises determining that no leader message should be sent if fewer than a threshold number of servers have proposed a particular leader message, and wherein the threshold number is greater than a number of malicious servers that the distributed computing system can tolerate.