Distributed algorithm for changing a shared value

Patent metadata

Field	Value
Publication number	US-9106629-B2
Application number	US-54332609-A
Country	US
Kind code	B2
Filing date	Aug 18, 2009
Priority date	Aug 18, 2009
Publication date	Aug 11, 2015
Grant date	Aug 11, 2015

Abstract

Each member of a group contributes to and calculates a new shared value. A distributed shared value algorithm is used to reach unanimous agreement on a shared value, such that every group member can use the new shared value as soon as it is changed. The distributed shared value agreement methodology operates without the selection of a leader. Each group member performs the distributed shared value agreement methodology and computes the new shared value using one or more of the contributions from the group members in such a way that no one member coerces the resulting shared value.

First claim

What is claimed is:

1. A method comprising:
determining each member computing device of a group to calculate a shared value used to enable access to functionality by each member computing device;
initiating calculating the shared value for the group, wherein one or more member computing devices contributes to the creation of the shared value; and
causing each member computing device of the group to:
execute a distributed shared value algorithm;
determine if one or more member computing devices of the group has generated a contribution;
calculate the shared value using only a portion of contributions from the group; and
store information relating to the contribution of each member computing device and a state variable using a data structure wherein the state variable indicates a state for changing the shared value for each member computing device.

2. The method of claim 1 , further comprising generating the data structure to include:
a date and time information about when a new shared value is to be in place;
a date and time information about when agreement on the new shared value starts;
an identifier of the group associated with the agreement; and
an array that includes an entry for each group member for changing the shared value.

3. The method of claim 1 , further comprising determining if membership of the group is changing and in response to the change delaying changing the shared value until the change in the membership of the group is complete.

4. The method of claim 1 , further comprising allowing a group membership change to take precedence during changing of the shared value to tolerate changes in the group membership while the shared value is in the process of being changed; and
in response to the change, stopping the change of the shared value and re-initiating the process of changing the shared value after the group membership change is complete.

5. The method of claim 1 , wherein calculating the shared value comprises selecting at least one of a shared value seed value and a sequencing value and each member computing device using the selected shared value seed value and the sequencing value to calculate the new shared value.

6. The method of claim 1 , wherein calculating the shared value comprises each member computing device calculating the shared value by computing a hash of each contribution by each of the members.

7. The method of claim 1 , further comprising creating the data structure for each member computing device that includes: a proposed shared value seed value; a randomly generated sequencing value for the proposed shared value seed value; and the state variable that indicates the state for changing the shared value for each member computing device.

8. The method of claim 7 , further comprising synchronizing each data structure of the group.

9. A computer-readable storage medium that is not a signal having computer-executable instructions configured for:
determining each member computing device of a group to calculate a shared value used to enable access to functionality by each member computing device;
causing each member computing device of the group to execute a distributed shared value algorithm;
generating a contribution to the shared value, wherein the contribution comprises a shared value seed value and a sequencing value;
providing the contribution to each member computing device of the group;
determining when each member computing device of the group has provided the contribution;
calculating the shared value using a portion of the provided contributions; and
storing information relating to the contribution of each member computing device and a state variable using a data structure wherein the state variable indicates a state for changing the shared value for each member computing device.

10. The computer-readable storage medium of claim 9 , further comprising attempting to authenticate the shared value after calculating the shared value, and when the shared value is not authenticated, initiating a shared value change operation and authenticating with a previous shared value.

11. The computer-readable storage medium of claim 9 , further comprising;
determining if membership of the group is changing; and
in response to the change, delaying changing the shared value until the change in the membership of the group is complete or stopping the change of the shared value and re-initiating the process of changing the shared value after the change in the membership of the group is complete.

12. The computer-readable storage medium of claim 9 , wherein calculating the shared value comprises selecting two or more contributions and using the selected contributions to calculate the new shared value.

13. The computer-readable storage medium of claim 9 , further comprising creating the data structure upon initiation of the shared value change operation that includes: a proposed shared value seed value; a randomly generated sequencing value for the proposed shared value seed value; and the state variable that indicates the state for changing the shared value for each member computing device.

14. The computer-readable storage medium of claim 13 , further comprising synchronizing each data structure of the group.

15. A system comprising:
an agreement manager executing on each member computing device; and configured to perform tasks, comprising:
determining each member computing device of a group to calculate a shared value used to enable access to functionality by each member computing device;
causing each member computing device of the group to execute a distributed shared value algorithm;
generating a contribution to the shared value, wherein the contribution comprises a shared value seed value and a sequencing value;
providing the contribution to each member computing device of the group;
determining if each member computing device of the group has provided the contribution;
calculating the shared value using a portion of the provided contributions; and
storing information relating to the contribution of each member computing device and a state variable using a data structure wherein the state variable indicates a state for changing the shared value for each member computing device.

16. The system of claim 15 , further comprising:
attempting to authenticate the shared value after calculating the shared value; and
if the shared value is not authenticated, initiating a shared value change operation and authenticating with a previous shared value that is stored with other previous shared values.

17. The system of claim 15 , further comprising:
determining if membership of the group is changing, and
in response to the change, delaying changing the shared value until the change in the membership of the group is complete or stopping the change of the shared value and re-initiating the process of changing the shared value after the change in the membership of the group is complete.

18. The system of claim 15 , wherein calculating the shared value comprises selecting each of the contributions and using the selected contributions to calculate the new shared value.

19. The system of claim 15 , further comprising creating the data structure upon initiation of the shared value change operation that includes: a proposed shared value seed value; a randomly generated sequencing value for the proposed shared value seed value; and the state variable that indicates the state for changing the shared value for each member computing device; wherein the data structure is removed after the shar

Assignees

• Ellison Carl M
• Zhu Larry
• Sundelin Tore L
• Kholodov Gleb
• Microsoft Technology Licensing Llc

Inventors

• Ellison Carl M
• Zhu Larry
• Sundelin Tore L
• Kholodov Gleb

Classifications

• H04L63/083

  using passwords (cryptographic mechanisms or cryptographic arrangements for entity authentication using a predetermined code H04L9/3226) · CPC title

• H04L67/10

  in which an application is distributed across nodes in the network (software deployment G06F8/60; multiprogramming arrangements G06F9/46) · CPC title

• G06F21/40

  by quorum, i.e. whereby two or more security principals are required · CPC title

• H04L63/061 Primary

  for key exchange, e.g. in peer-to-peer networks (cryptographic mechanisms or cryptographic arrangements for key agreement H04L9/0838) · CPC title

• H04L9/0891

  Revocation or update of secret information, e.g. encryption key update or rekeying · CPC title