Distributed consensus in a content centric network

• US 10,447,805 B2
• Filed: 10/10/2016
• Issued: 10/15/2019
• Est. Priority Date: 10/10/2016
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Mosko, Marc E.
• Primary Examiner(s): Sison, June Y
• Assistant Examiner(s): Cooney, Adam A
• Application Number:
  US15/289,739
• Publication Number:
  US 20180103117A1
• Time in Patent Office: 1,100 Days
• Field of Search: 709201
• 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 67/60 Scheduling or organising the servicing of application requests, e.g. requests for application data transmissions using the analysis and optimisation of the required network resources admission control or resource allocation H04L47/70
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context

Abstract

One embodiment provides a system that facilitates distributed consensus in a content centric network. During operation, the system generates, by a coordinator for a plurality of nodes, a first interest that indicates a request to approve a proposed value for a variable. In response to receiving a positive acknowledgment of the first interest from a majority of the nodes, the coordinator generates a second interest that indicates a request to accept the proposed value. A name for the first interest and a name for the second interest include an identifier of the variable and a round number. A payload of the first interest and a payload of the second interest include the proposed value. In response to receiving a positive acknowledgement of the second interest from the majority of the nodes, the system generates a notification indicating that an agreed-upon value for the variable is the proposed value.

Claims

1. A computer system for facilitating distributed consensus in a content centric network, the computer system comprising:

a processor; and

a storage device storing instructions that when executed by the processor cause the processor to perform operations, the operations comprising;

generating a first interest indicating a request to approve a proposed value for a variable, wherein the computer system is a coordinator for a plurality of nodes;

in response to receiving a positive acknowledgment of the first interest from a majority of the nodes, generating a second interest indicating a request to accept the proposed value, wherein a name for the first interest and a name for the second interest include an identifier of the variable and a round number, and wherein a payload of the first interest and a payload of the second interest include the proposed value; and

in response to receiving a positive acknowledgement of the second interest from the majority of the nodes, generating a notification indicating that an agreed-upon value for the variable is the proposed value.

2. The computer system of claim 1, wherein the operations further comprise:

in response to receiving a third interest indicating a request to read the agreed-upon value for the variable, wherein a name for the third interest includes the variable identifier and the round number, generating a content object which indicates the round number and one or more of;

the agreed-upon value for the variable;

an iteration number corresponding to the round number;

a negative acknowledgment if the agreed-upon value for the variable is indeterminate; and

a no-operation indicator if no agreed-upon value for the variable exists.

3. The computer system of claim 2, wherein the positive acknowledgement of the second interest is transmitted to the coordinator by the majority of the nodes,

wherein the notification is generated by the majority of the nodes and further transmitted to a learning device, which transmits the notification as a fourth interest to one or more systems interested in the agreed-upon value for the variable.

4. The computer system of claim 3, wherein the name for the first interest, the name for the second interest, the name for the third interest, and the name for the fourth interest further include one or more of:

a routable prefix for one of the majority of the nodes;

an identifier for a consensus group to which the one of the majority of the nodes belongs, wherein the plurality of nodes belong to the consensus group;

an indicator of a logical program associated with the variable identifier; and

an iteration number corresponding to the round number.

5. The computer system of claim 3, wherein the name for the first interest indicates the request to approve the proposed value for the variable,

wherein the name for the second interest indicates the request to accept the proposed value,

wherein the name for the third interest indicates the request to read the agreed-upon value, and

wherein the name for the fourth interest indicates the notification to allow a receiving device to learn the agreed-upon value.

6. The computer system of claim 1, wherein the operations further comprise:

transmitting, by the coordinator, the first interest to a multicast group comprised of the majority of the nodes; and

transmitting, by the coordinator, the second interest to the multicast group,

wherein the name for the first interest and the name for the second interest further include one or more of;

an identifier for a consensus group to which the one of the majority of the nodes belongs, wherein the plurality of nodes belong to the consensus group, wherein the consensus group identifier is the most general level name component; and

an indicator of a group version to which the majority of the nodes belongs,

wherein the payload of the first interest further includes a routable prefix of the coordinator to be used by a node in response to the first interest, and

wherein the payload of the second interest further includes a routable prefix of a target to be used by a node in response to the second interest.

7. The computer system of claim 1, wherein the proposed value is one or more of:

a link to a piece of content which describes a current state of an algorithm;

a link to a manifest, which is a content object indicating a collection of other content objects; and

the manifest embedded in the proposed value.

8. The computer system of claim 1, wherein a response by one of the majority of the nodes to an interest is a content object with a same name as the name for the interest, wherein the content object has a lifetime set to a small or a zero value.

9. A computer system for facilitating distributed consensus in a content centric network, the system comprising:

a processor; and

a storage device storing instructions that when executed by the processor cause the processor to perform operations, the operations comprising;

receiving a first interest indicating a request to approve a proposed value for a variable, wherein the first interest is received from a coordinator for a plurality of nodes by a node;

in response to agreeing with the proposed value, transmitting a positive acknowledgement of the first interest to the coordinator;

receiving a second interest indicating a request to accept the proposed value, wherein a name for the first interest and a name for the second interest include an identifier of the variable and a round number, and wherein a payload of the first interest and a payload of the second interest include the proposed value; and

in response to accepting the proposed value, transmitting a positive acknowledgement of the second interest to the coordinator.

10. The computer system of claim 9, wherein in response to accepting the proposed value, the operations further comprise:

transmitting a notification indicating that an agreed-upon value for the variable is the proposed value to a learning device, which transmits the notification as a third interest to one or more systems interested in the agreed-upon value for the variable.

11. The computer system of claim 9, wherein the operations further comprise:

in response to not agreeing with the proposed value, transmitting a negative acknowledgment of the first interest to the coordinator, wherein the negative acknowledgment includes a previous value for the variable corresponding to a previous round number.

12. The computer system of claim 10, wherein the name for the first interest, the name for the second interest, and the name for the third interest further include one or more of:

a routable prefix for one of a majority of the nodes;

an identifier for a consensus group to which the one of a majority of the nodes belongs, wherein the plurality of nodes belong to the consensus group;

an indicator of a logical program associated with the variable identifier; and

an iteration number corresponding to the round number; and

wherein the name for the first interest indicates the request to approve the proposed value for the variable,

wherein the name for the second interest indicates the request to accept the proposed value, and

wherein the name for the third interest indicates the notification to allow a receiving device to learn the agreed-upon value.

13. A computer-implemented method for facilitating distributed consensus in a content centric network, the method comprising:

generating a first interest indicating a request to approve a proposed value for a variable, wherein a computer system is a coordinator for a plurality of nodes;

in response to receiving a positive acknowledgment of the first interest from a majority of the nodes, generating a second interest indicating a request to accept the proposed value, wherein a name for the first interest and a name for the second interest include an identifier of the variable and a round number, and wherein a payload of the first interest and a payload of the second interest include the proposed value; and

in response to receiving a positive acknowledgement of the second interest from the majority of the nodes, generating a notification indicating that an agreed-upon value for the variable is the proposed value.

14. The method of claim 13, further comprising:

in response to receiving a third interest indicating a request to read the agreed-upon value for the variable, wherein a name for the third interest includes the variable identifier and the round number, generating a content object which indicates the round number and one or more of;

the agreed-upon value for the variable;

an iteration number corresponding to the round number;

a negative acknowledgment if the agreed-upon value for the variable is indeterminate; and

a no-operation indicator if no agreed-upon value for the variable exists.

15. The method of claim 14, wherein the positive acknowledgement of the second interest is transmitted to the coordinator by the majority of the nodes,

wherein the notification is generated by the majority of the nodes and further transmitted to a learning device, which transmits the notification as a fourth interest to one or more systems interested in the agreed-upon value for the variable.

16. The method of claim 15, wherein the name for the first interest, the name for the second interest, the name for the third interest, and the name for the fourth interest further include one or more of:

a routable prefix for one of the majority of the nodes;

an identifier for a consensus group to which the one of the majority of the nodes belongs, wherein the plurality of nodes belong to the consensus group;

an indicator of a logical program associated with the variable identifier; and

an iteration number corresponding to the round number.

17. The method of claim 16, wherein the name for the first interest indicates the request to approve the proposed value for the variable,

wherein the name for the second interest indicates the request to accept the proposed value,

wherein the name for the third interest indicates the request to read the agreed-upon value, and

wherein the name for the fourth interest indicates the notification to allow a receiving device to learn the agreed-upon value.

18. The method of claim 13, further comprising:

transmitting, by the coordinator, the first interest to a multicast group comprised of the majority of the nodes; and

transmitting, by the coordinator, the second interest to the multicast group,

wherein the name for the first interest and the name for the second interest further include one or more of;

an identifier for a consensus group to which the one of the majority of the nodes belongs, wherein the plurality of nodes belong to the consensus group, wherein the consensus group identifier is the most general level name component; and

an indicator of a group version to which the majority of the nodes belongs,

wherein the payload of the first interest further includes a routable prefix of the coordinator to be used by a node in response to the first interest, and

wherein the payload of the second interest further includes a routable prefix of a target to be used by a node in response to the second interest.

19. The method of claim 13, wherein the proposed value is one or more of:

a link to a piece of content which describes a current state of an algorithm;

a link to a manifest, which is a content object indicating a collection of other content objects; and

the manifest embedded in the proposed value.

20. The method of claim 13, wherein a response by one of the majority of the nodes to an interest is a content object with a same name as the name for the interest, wherein the content object has a lifetime set to a small or a zero value.