Chandra-Toueg consensus in a content centric network

• US 10,257,271 B2
• Filed: 01/11/2016
• Issued: 04/09/2019
• Est. Priority Date: 01/11/2016
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Wood, Christopher A., Scott, Glenn C.
• Primary Examiner(s): Taylor, Nicholas R
• Assistant Examiner(s): Li, Michael
• Application Number:
  US14/992,883
• Publication Number:
  US 20170201577A1
• Time in Patent Office: 1,184 Days
• CPC Class Codes: H04L 63/08 for authentication of entities cryptographic mechanisms or cryptographic arrangements for entity authentication H04L9/32
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context
• CPC Class Codes: H04L 69/40 for recovering from a failure of a protocol instance or entity, e.g. service redundancy protocols, protocol state redundancy or protocol service redirection management of faults, events, alarms or notifications in data switching networks H04L41/06

Abstract

One embodiment provides a system that facilitates secure communication between computing entities. During operation, the system generates a first interest that indicates a vote for a value associated with a group prefix and a round number. In response to the first interest, the system receives a first content object that indicates an acknowledgment of the vote and has a payload that includes a nonce validator. In response to a second interest that indicates an acknowledgment of the first content object, the system receives a second content object that indicates a decision for the value and has a payload that includes a nonce which is used as a pre-image of the nonce validator. The system verifies the second content object based on the nonce and the nonce validator.

Claims

1. A computer system for facilitating synchronization via consensus between a plurality of nodes in a content centric network using interests and content objects to communicate between the plurality of nodes in the 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 a method, the method comprising;

generating a first interest that includes a name and a payload, wherein a name in the content centric network is a hierarchically structured variable length identifier comprising contiguous name components ordered from a most general level to a most specific level, wherein the name of the first interest indicates a vote and a round number, and wherein the payload of the first interest includes a value associated with a group prefix, wherein the plurality of nodes are associated with the group prefix for routing within the content centric network;

in response to the first interest, receiving a first content object that includes a name and a payload, wherein the name of the first content object indicates an acknowledgment of the vote, and wherein the payload of the first content object includes a nonce validator;

generating a second interest having a name that indicates an acknowledgment of the first content object, and wherein a payload of the second interest is empty;

in response to the second interest, receiving a second content object that includes a name and a payload, wherein the name of the second content object indicates a decision for the value, and wherein the payload of the second content object includes a nonce which is used as a pre-image of the nonce validator;

verifying the second content object based on the nonce and the nonce validator; and

based on the verifying, determining that the decision for the value associated with the group prefix of the plurality of nodes indicated by the vote is a valid decision-determined by consensus of the plurality of nodes, thereby achieving synchronization via consensus among the plurality of nodes in the content centric network.

2. The computer system of claim 1, wherein the method further comprises:

in response to not receiving the first content object before an expiration of the first interest, and in response to determining that a current round number is the round number;

re-transmitting the first interest.

3. The computer system of claim 1, wherein the method further comprises:

in response to not receiving the first content object before an expiration of the first interest, and in response to determining that a current round number is a next round number;

setting the current round number to the next round number; and

transmitting another interest that includes a name and a payload, wherein the name of the another interest indicates a vote and the current round number, and wherein the payload of the another interest includes a value associated with the group prefix.

4. The computer system of claim 1, wherein the method further comprises:

in response to not receiving the second content object before an expiration of the second interest, generating a third interest that indicates a negative acknowledgment of the second interest.

5. The computer system of claim 1, wherein the method further comprises:

in response to the first interest, receiving a marker content object that has a payload which includes a future name for a content object that will correspond to the first content object;

generating a fourth interest with a name that is the future name; and

in response to the fourth interest, receiving the first content object.

6. The computer system of claim 1, wherein the method further comprises:

in response to the second interest, receiving a marker content object that has a payload which includes a future name for a content object that will correspond to the second content object;

generating a fourth interest with a name that is the future name; and

in response to the fourth interest, receiving the second content object.

7. The computer system of claim 1, wherein the acknowledgment of the vote indicated in the first content object further indicates that a majority of the plurality of nodes with the group prefix has submitted a vote for a value that is the same as the value indicated in the first interest, and wherein the decision for the value indicated in the second content object further indicates that a majority of the plurality of nodes with the group prefix has submitted an acknowledgment of the first content object.

8. The computer system of claim 1, wherein verifying the second content object further comprises:

performing a hash on the nonce; and

determining that the hash matches the nonce validator.

16. The computer system of claim 1, wherein the plurality of nodes includes n number of nodes;

and

wherein consensus of the plurality of nodes is reached when a value receives at least n/2 votes.

17. The computer system of claim 1, wherein the plurality of nodes includes a plurality of voting nodes and a coordinator node.

18. The computer system of claim 17, wherein the coordinator node determines that the decision for the value associated with the group prefix of the plurality of nodes indicated by the vote is a valid decision determined by consensus of the plurality of nodes.

9. A computer-implemented method for facilitating synchronization via consensus between a plurality of nodes in a content centric network using interests and content objects to communicate between the plurality of nodes in the content centric network, the method comprising:

generating a first interest that includes a name and a payload, wherein a name in the content centric network is a hierarchically structured variable length identifier comprising contiguous name components ordered from a most general level to a most specific level, wherein the name of the first interest indicates a vote and a round number, and wherein the payload of the first interest includes a value associated with a group prefix, wherein the plurality of nodes are associated with the group prefix for routing within the content centric network;

in response to the first interest, receiving a first content object that includes a name and a payload, wherein the name of the first content object indicates an acknowledgment of the vote, and wherein the payload of the first content object includes a nonce validator;

generating a second interest having a name that indicates an acknowledgment of the first content object, and wherein a payload of the second interest is empty;

in response to the second interest, receiving a second content object that includes a name and a payload, wherein the name of the second content object indicates a decision for the value, and wherein the payload of the second content object includes a nonce which is used as a pre-image of the nonce validator;

verifying the second content object based on the nonce and the nonce validator; and

based on the verifying, determining that the decision for the value associated with the group prefix of the plurality of nodes indicated by the vote is a valid decision determined by consensus of the plurality of nodes, thereby achieving synchronization via consensus among the plurality of nodes in the content centric network.

10. The method of claim 9, further comprising:

in response to not receiving the first content object before an expiration of the first interest, and in response to determining that a current round number is the round number;

re-transmitting the first interest.

11. The method of claim 9, further comprising:

in response to not receiving the first content object before an expiration of the first interest, and in response to determining that a current round number is a next round number;

setting the current round number to the next round number; and

transmitting another interest that includes a name and a payload, wherein the name of the another interest indicates a vote and the current round number, and wherein the payload of the another interest includes a value associated with the group prefix.

12. The method of claim 9, further comprising:

in response to not receiving the second content object before an expiration of the second interest, generating a third interest that indicates a negative acknowledgment of the second interest.

13. The method of claim 9, further comprising:

in response to the first interest, receiving a first marker content object that has a payload which includes a future name for a content object that will correspond to the first content object;

generating a fourth interest with a name that is the future name;

in response to the fourth interest, receiving the first content object;

in response to the second interest, receiving a second marker content object that has a payload which includes a future name for a content object that will correspond to the second content object;

generating a fifth interest with a name that is the future name; and

in response to the fifth interest, receiving the second content object.

14. The method of claim 9, wherein the acknowledgment of the vote indicated in the first content object further indicates that a majority of a plurality of nodes with the group prefix has submitted a vote for a value that is the same as the value indicated in the first interest, and wherein the decision for the value indicated in the second content object further indicates that a majority of a plurality of nodes with the group prefix has submitted an acknowledgment of the first content object.

15. The method of claim 9, wherein verifying the second content object further comprises:

performing a hash on the nonce; and

determining that the hash matches the nonce validator.

19. The method of claim 9, wherein the plurality of nodes includes n number of nodes;

and

wherein consensus of the plurality of nodes is reached when a value receives at least n/2 votes.

20. The method of claim 9, wherein the plurality of nodes includes a plurality of voting nodes and a coordinator node;

and

wherein the coordinator node determines that the decision for the value associated with the group prefix of the plurality of nodes indicated by the vote is a valid decision determined by consensus of the plurality of nodes.