Multi-leader distributed system

• US 7,260,611 B2
• Filed: 11/21/2002
• Issued: 08/21/2007
• Est. Priority Date: 11/21/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Hydrie, Aamer, Lamport, Leslie, Achlioptas, Demetrios
• Primary Examiner(s): Dinh; Khanh
• Assistant Examiner(s): PHILLIPS, HASSAN A
• Application Number:
  US10/302,572
• Publication Number:
  US 20040103138A1
• Time in Patent Office: 1,734 Days
• Field of Search: 709/208, 370/229, 370/230
• US Class Current: 709/208
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]

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.

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 first command sequence number and a value indicative of a command associated with the first 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 second command sequence number different from the first command sequence number of the other lead process and a value indicative of a command associated with the second command sequence;

each process in the plurality of processes programmed to receive the command sequence numbers and values indicative of the commands associated with the command sequences from the first lead process and the second lead process and to execute the commands in a predefined order.

2. The system as recited in claim 1, wherein one of the first and second lead processes is selected from the plurality of processes.

3. The system as recited in claim 1, wherein the first and second lead processes communicate commands associated with sequence numbers to the plurality of processes.

4. The system as recited in claim 1, wherein the plurality of processes receive commands and communicate the commands to one of the first lead process or the second lead process.

5. The system as recited in claim 4, wherein the first and second lead processes occasionally assign a command sequence number to a no-op command.

6. The system as recited in claim 4, wherein the occasion for assigning a command sequence to a no-op command is based on the lack of commands received from the plurality of processes for a predetermined period of time.

7. The system as recited in claim 1 wherein the plurality of processes are hosted by separate computer devices.

8. The system as recited in claim 1 wherein the command sequences are numbers.

9. The system as recited in claim 1 wherein the command sequences are time-based.

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 different command sequence numbers, than the command sequence numbers determined by the other lead processes, 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.

11. The method of claim 10 wherein the command comprises at least one computer-executable instruction.

12. The method of claim 10 wherein the command sequence numbers comprise an ordered set of numbers.

13. The method of claim 12 wherein the command sequence numbers used by one lead process are different from the command sequence numbers used by the other lead processes.

14. The method of claim 10 wherein the command sequence numbers comprises a time component.

15. The method of claim 10 further comprising sending sequenced commands to all of the connected processes.

16. The method of claim 10 further wherein the connected processes send receive commands to a lead process for assignment of a command sequence.

17. A computer-readable storage medium bearing computer readable instructions for assigning a command sequence in a network of connected computer processes, comprising:

a first process for 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 different command sequence numbers, than the command seauence numbers determined by the first process, 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 a plurality of the connected processes execute the commands in the same order.

18. The computer-readable medium of claim 17 wherein the command comprises at least one computer-executable instruction.

19. The computer-readable medium of claim 17 wherein the command sequences comprise an ordered set of numbers.

20. The computer-readable medium of claim 19 wherein the numbers are different from the numbers used by the other processes that is assigning command sequence numbers.

21. The computer-readable medium of claim 17 wherein the command sequences comprise a time component.

22. The computer-readable medium of claim 17, further comprising sending sequenced commands to all of the connected processes.

23. The computer-readable medium of claim 17 further comprising receiving commands from connected processes for assignment of a command sequence number.