Method and apparatus for selecting a proposed command structure in a distributed computer system based on generalized paxos algorithm

摘要

A distributed computing system can achieve a generalized consensus, enabling commands that commute to be selected in any order. A leader can learn of previously selected sequences of commands, and can propose a compatible sequence of commands. Devices can select a sequence of commands that is compatible with previously selected sequences. Additional commands can be selected by selecting a sequence of commands comprising a previously selected sequence and the additional commands. Further efficiencies can be realized if the devices receive proposals directly from clients. Two or more proposals arriving in varying orders at the various clients may be selected in varying orders. However, if those proposals commute, a generalized consensus nevertheless exists despite the variations, enabling the system to continue efficient operation. To conserve memory, a checkpoint command that does not commute with any other command can be used to secure a sequence of commands for archiving or deletion.