Multi-leader distributed system
First Claim
1. A distributed computer system, comprising:
- a plurality of processes each having an associated set of data;
a first lead process in communication with the plurality of processes wherein the first lead process communicates a command sequence number and a number indicative of a command associated with the command sequence to the plurality of processes;
a second lead process in communication with the plurality of processes wherein the second lead process communicates a command sequence number different from the command sequence number of the other lead process and a value indicative of a command associated with the command sequence;
each process programmed to receive the command sequence numbers and values indicative of a command associated with the command sequences and to execute the command in a predefined order.
2 Assignments
0 Petitions
Accused Products
Abstract
New information is introduced to a distributed system at many places. The information impacts data that is replicated throughout the system. The replicas of the data must be synchronized so that changes to the system are accurately reflected. One solution to the synchronized replica problem is a state machine approach. In such an approach, the computers of the network each maintain their own data, which is kept in the same state as the data of the other computers by processing the identical commands in the identical order. To ensure that all commands are executed in the same order, a lead process is given the task of assigning command sequence numbers. However, using a single lead process introduces a bottleneck in the distributed system by requiring that all commands to change data go through the lead process to be assigned an execution order. The invention divides the command ordering among multiple lead processes. Each lead process assigns command sequence numbers that are ordered with respect to other lead process but which do not conflict with the command sequence numbers assigned by the other leader processes.
-
Citations
23 Claims
-
1. A distributed computer system, comprising:
-
a plurality of processes each having an associated set of data;
a first lead process in communication with the plurality of processes wherein the first lead process communicates a command sequence number and a number indicative of a command associated with the command sequence to the plurality of processes;
a second lead process in communication with the plurality of processes wherein the second lead process communicates a command sequence number different from the command sequence number of the other lead process and a value indicative of a command associated with the command sequence;
each process programmed to receive the command sequence numbers and values indicative of a command associated with the command sequences and to execute the command in a predefined order. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. A method for assigning a command sequence in a network of connected computer processes, comprising:
-
providing at least two processes from a network of connected processes to serve as lead processes;
each lead process determining command sequence numbers to assign to commands to be executed by the connected processes;
wherein the command sequence numbers place a deterministic execution order on a set of commands to be executed by the connected processes; and
distributing the command sequence numbers to the connected processes as an indication of the execution or of the set of commands, whereby all of the connected processes execute the commands in the same order. - View Dependent Claims (11, 12, 13, 14, 15, 16)
-
-
17. A computer-readable medium bearing computer readable instructions for assigning a command sequence in a network of connected computer processes, comprising:
-
determining command sequence numbers to assign to commands to be executed by connected processes in a system wherein the command sequence numbers place a deterministic execution order on a set of commands to be executed by the connected processes and wherein at least one other process assigns command sequence numbers to commands to be executed;
distributing the command sequence numbers to the connected processes as an indication of the execution order of the set of commands, whereby all of the connected processes execute the commands in the same order. - View Dependent Claims (18, 19, 20, 21, 22, 23)
-
Specification