Generalized paxos

A method for selecting a proposed command structure in a distributed computing system, wherein a command structure represents all equivalent sequences of functions, and wherein a prefix of a larger command structure is a smaller command structure such that one or more functions can be appended to the smaller command structure to obtain the larger command structure, the method comprising:

• receiving a request from a client to perform a requested function;
• appending the requested function to a previously accepted command structure to form a proposed command structure;
• associating the proposed command structure with a proposal number, wherein the proposal number signifies use of a generalized reduced message delay fault tolerant consensus algorithm;
• accepting the proposed command structure if no previously responded to proposal number is higher than the proposal number;
• and
• transmitting an acceptance message identifying the proposed command structure if the proposed command structure was accepted.

A computer-readable medium having computer-executable instructions for selecting a proposed command structure in a distributed computing system, wherein a command structure represents all equivalent sequences of functions, and wherein a prefix of a larger command structure is a smaller command structure such that one or more functions can be appended to the smaller command structure to obtain the larger command structure, the computer executable instructions performing steps comprising:

• transmitting, to a first quorum of devices in the distributed computing system, the proposed command structure, wherein the proposed command structure is associated with a proposal number;
• receiving acceptance messages indicating an acceptance of the proposed command structure, wherein an accepting device can send an acceptance message if it has not responded to a suggested proposal number higher than the proposal number and if it has previously voted for some prefix of the proposed command structure that was proposed using the proposal number or if it has not previously voted for any command structure proposed using the proposal number;
• and
• determining that the proposed command structure has been selected by the distributed computing system if the acceptance messages are received from a second quorum of devices.

A computer-readable medium having computer-executable instructions for selecting a proposed command structure in a distributed computing system, wherein a command structure represents all equivalent sequences of functions, and wherein a prefix of a larger command structure is a smaller command structure such that one or more functions can be appended to the smaller command structure to obtain the larger command structure, the computer executable instructions performing steps comprising:

• receiving a request from a client to perform a requested function;
• appending the requested function to a previously accepted command structure to form a proposed command structure;
• associating the proposed command structure with a proposal number, wherein the proposal number signifies use of a generalized reduced message delay fault tolerant consensus algorithm;
• accepting the proposed command structure if no previously responded to proposal number is higher than the proposal number;
• and
• transmitting an acceptance message identifying the proposed command structure if the proposed command structure was accepted.

A computing device in a distributed computing system comprising:

• a network interface for performing steps comprising:
• transmitting, to a first quorum of devices in the distributed computing system, a proposed command structure, wherein the proposed command structure is associated with a proposal number, and wherein further a command structure represents all equivalent sequences of functions, and a prefix of a larger command structure is a smaller command structure such that one or more functions can be appended to the smaller command structure to obtain the larger command structure;
• and
• receiving acceptance messages indicating an acceptance of the proposed command structure, wherein an accepting device can send an acceptance message if it has not responded to a suggested proposal number higher than the proposal number and if it has previously voted for some prefix of the proposed command structure that was proposed using the proposal number or if it has not previously voted for any command structure proposed using the proposal number;
• and
• a processing unit for performing steps comprising:
• determining that the proposed command structure has been selected by the distributed computing system if the acceptance messages are received from a second quorum of devices.

A computing device in a distributed computing system comprising:

• a network interface for performing steps comprising:
• receiving a request from a client to perform a requested function;
• appending the requested function to a previously accepted command structure to form a proposed command structure, wherein a command structure represents all equivalent sequences of functions, and wherein a prefix of a larger command structure is a smaller command structure such that one or more functions can be appended to the smaller command structure to obtain the larger command structure;
• and
• transmitting an acceptance message identifying the proposed command structure if the proposed command structure was accepted;
• and
• a processing unit for performing steps comprising:
• associating the proposed command structure with a proposal number, wherein the proposal number signifies use of a generalized reduced message delay fault tolerant consensus algorithm;
• and
• accepting the proposed command structure if no previously responded to proposal number is higher than the proposal number.