Methods and systems for managing shared state within a distributed system with varying consistency and consensus semantics

• US 8,769,019 B2
• Filed: 05/04/2006
• Issued: 07/01/2014
• Est. Priority Date: 05/04/2006
• Status: Active Grant

• Current Assignee: GOTO Group Incorporated (LogMeIn, Inc.)
• Original Assignee: Citrix Systems, Inc. (Cloud Software Group)
• Inventors: Chalmers, Robert, Bryan, Todd
• Primary Examiner(s): DONAGHUE, LARRY D
• Application Number:
  US11/381,704
• Publication Number:
  US 20070260689A1
• Time in Patent Office: 2,980 Days
• Field of Search: 709204-206, 345/418, 345/419, 345/440, 345/473, 715/200, 715/201, 715/700, 715/716, 715/717, 715/730, 715/733
• US Class Current: 709/205
• CPC Class Codes: G06Q 10/10 Office automation; Time management
• CPC Class Codes: H04L 12/1822 Conducting the conference, e.g. admission, detection, selection or grouping of participants, correlating users to one or more conference sessions, prioritising transmission
• CPC Class Codes: H04L 12/1863 comprising mechanisms for improved reliability, e.g. status reports arrangements for detecting or preventing errors by carrying supervisory signal the return channel H04L1/16

Abstract

Methods and systems for managing shared state within a distributed system with varying consistency and consensus semantics are described. In one configuration, a computing device receives a first plurality of objects representing the state of a first item and a second plurality of objects representing the state of a second item. The computing device generates a composed view of the state of each of the first item and the second item. The resulting composed views are transmitted using a reliable multicast protocol.

Claims

1. A method of generating a composed view of a state of each of a plurality of items in a distributed computing system having a plurality of computing devices, the method comprising:

(a) receiving a first plurality of objects having a same number of fields, each of the first plurality of objects being received from a different one of the plurality of computing devices in the distributed computing system and each of the first plurality of objects representing a state of a first item in the distributed computing system to which access is controlled, each field of the first plurality of objects storing information that defines the state of the first item;

(b) operating, by a first composer module, on the first plurality of objects to generate a first composed view object of the state of the first item, the first composed view object having the same number of fields as each of the first plurality of objects, the fields of the first composed view object storing a combination of information selected from the fields of the first plurality of objects, the first composer module selected for use from amongst a first plurality of composer modules that are each configured to operate differently on the first plurality of objects and to thereby generate different first composed view objects;

(c) receiving a second plurality of objects having a same number of fields, each of the second plurality of objects being received from a different one of the plurality of computing devices in the distributed computing system and each of the second plurality of objects representing a state of a second item in the distributed computing system to which access is controlled, each field of the second plurality of objects storing information that defines the state of the second item;

(d) operating, by a second composer module, on the second plurality of objects to generate a second composed view object of the state of the second item, the second composed view object having the same number of fields as each of the second plurality of objects, the fields of the second composed view object storing a combination of information selected from the fields of the second plurality of objects, the second composer module selected for use from amongst a second plurality of composer modules that are each configured to operate differently on the second plurality of objects and to thereby generate different second composed view objects; and

(e) transmitting the first composed view object and the second composed view object using a reliable multicast protocol to at least some of the plurality of computing devices of the distributed computing system, the first composed view object and the second composed view object being used to achieve consistency and consensus about which computing devices within the distributed computing system can access which objects within the distributed computing system, the consistency and the consensus being achieved via one or more access control lists, the one or more access control lists being time-invariant and being defined in terms of one or more mutable groups, wherein the one or more mutable groups are not time-invariant.

2. The method of claim 1 wherein at least one of steps (a) and (c) comprises receiving a plurality of objects having the same number fields, each field storing information that defines the state of the object, the information stored in the field comprising one of the following data types:

static state, monotonically increasing state, versioned cyclic state transition, a monotonic set, and non-cyclic state transitions.

3. The method of claim 2 wherein the data type of at least one of the plurality of fields is different from at least some of the others of the plurality of fields.

4. The method of claim 1 wherein operating by the first composer comprises operating on the first plurality of objects to generate a consensus composed view, the consensus composed view representing a state of the first item that is agreed upon by all the computing devices in the distributed computing system.

5. The method of claim 1 wherein operating by the first composer comprises operating on the first plurality of objects to generate a consistency composed view, the consistency composed view representing a state of the first item that is the same as the state of the first item represented in a composed view object generated by at least one other computing device in the distributed computing system.

6. The method of claim 1 wherein operating by one of the first composer and the second composer comprises performing an intersection operation on at least one of the plurality of fields of the plurality of objects.

7. The method of claim 1 wherein operating by one of the first composer and the second composer comprises performing a union operation on at least one of the plurality of fields of the plurality of objects.

8. The method of claim 1 wherein operating by one of the first composer and the second composer comprises performing a maximum value determination on at least one of the plurality of fields of the plurality of objects.

9. The method of claim 1 wherein operating by one of the first composer and the second composer comprises performing a minimum value determination on at least one of the plurality of fields of the plurality of objects.

10. The method of claim 1 wherein operating by the first composer comprises performing a first operation on at least one of the plurality of fields of the first plurality of objects and performing a second operation, different from the first operation, on another one of the plurality of fields of the first plurality of objects.

11. A system for generating a composed view of the state of each of a plurality of items in a distributed computing system having a plurality of computing devices, the system comprising:

a receiver, in communication with a network using a reliable multi-cast protocol, receiving i) a first plurality of objects having a same number of fields, each of the first plurality of objects being received from a different one of the plurality of computing devices in the distributed computing system and each of the first plurality of objects representing a state of a first item in the distributed computing system to which access is controlled, each field of the first plurality of objects storing information that defines the state of the first item, and ii) a second plurality of objects having a same number of fields, each of the second plurality of objects being received from a different one of the plurality of computing devices in the distributed computing system and each of the second plurality of objects representing a state of a second item in the distributed computing system to which access is controlled, each field of the second plurality of objects storing information that defines the state of the second item;

a first composer in communication with the receiver and selected for use from amongst a first plurality of composers, the first composer operating on the first plurality of objects to generate a first composed view object of the state of the first item, the first composed view object having the same number of fields as each of the first plurality of objects, the fields of the first composed view object storing a combination of information selected from the fields of the first plurality of objects, the first plurality of composers each being configured to operate differently on the first plurality of objects and to thereby generate different first composed view objects;

a second composer in communication with the receiver and selected for use from amongst a second plurality of composers, the second composer operating on the second plurality of objects to generate a second composed view object of the state of the second item, the second composed view object having the same number of fields as each of the second plurality of objects, the fields of the second composed view object storing a combination of information selected from the fields of the second plurality of objects, the second plurality of composers each being configured to operate differently on the second plurality of objects and to thereby generate different second composed view objects; and

a transmitter in communication with the first and second composers and the network, the transmitter transmitting, using the reliable multi-cast protocol, the first composed view object and the second composed view object to at least some of the plurality of computing devices of the distributed computing system, the first composed view object and the second composed view object being used to achieve consistency and consensus about which computing devices within the distributed computing system can access which objects within the distributed computing system, the consistency and the consensus being achieved via one or more access control lists, the one or more access control lists being time-invariant and being defined in terms of one or more mutable groups, wherein the one or more mutable groups are not time-invariant.

12. The system of claim 11 wherein the information stored in the fields comprises one of the following data types:

static state, monotonically increasing state, versioned cyclic state transition, a monotonic set, and non-cyclic state transitions.

13. The system of claim 12 wherein the data type of at least one of the plurality of fields is different from at least some of the others of the plurality of fields.

14. The system of claim 11 wherein the first composer operates on the first plurality of objects and generates a consensus composed view, the consensus composed view representing a state of the first item that is agreed upon by all the computing devices in the distributed computing system.

15. The system of claim 11 wherein the first composer operates on the first plurality of objects and generates a consistency composed view, the consistency composed view representing a state of the first item that is the same as the state of the first item represented in a composed view object generated by at least one other computing device in the distributed computing system.

16. The system of claim 11 wherein one of the first composer and the second composer performs an intersection operation on at least one of the plurality of fields of the plurality of objects.

17. The system of claim 11 wherein one of the first composer and the second composer performs a union operation on at least one of the plurality of fields of the plurality of objects.