Reliable map-reduce communications in a decentralized, self-organizing communication orbit of a distributed network

• US 10,649,870 B1
• Filed: 01/23/2018
• Issued: 05/12/2020
• Est. Priority Date: 04/24/2015
• Status: Active Grant

• Current Assignee: Tanium Inc.
• Original Assignee: Tanium Inc.
• Inventors: Lippincott, Lisa, Hindawi, David, Hindawi, Orion, Lincroft, Peter
• Primary Examiner(s): Bonzo, Bryce P
• Assistant Examiner(s): Arcos, Jeison C
• Application Number:
  US15/878,286
• Time in Patent Office: 840 Days
• CPC Class Codes: G06F 11/00 Error detection; Error correction; Monitoring error detection, correction or monitoring in information storage based on relative movement between record carrier and transducer G11B20/18; monitoring, i.e. supervising the progress of recording or reproducing G11B27/36; in static stores G11C29/00
• CPC Class Codes: G06F 11/0709 in a distributed system consisting of a plurality of standalone computer nodes, e.g. clusters, client-server systems
• CPC Class Codes: G06F 11/0757 by exceeding a time limit, i.e. time-out, e.g. watchdogs
• CPC Class Codes: G06F 11/30 Monitoring
• CPC Class Codes: H04L 43/0864 Round trip delays

Abstract

Method and system for providing message communications with failure detection and recovery are disclosed. At a respective node of a non-static collection of nodes forming a linear communication orbit: the node identifies, from among the non-static collection of nodes, a set of forward contacts distributed in a forward direction along the linear communication orbit; the node monitors a propagation state of a first query that has departed from the respective node to travel in the forward direction along the linear communication orbit; and upon detecting a propagation failure of the first query based on the monitoring, the node sends the first query directly to a first forward contact among the set of forward contacts to initiate a failure recovery process within at least part of a segment of the linear communication orbit between the respective node and the first forward contact of the respective node.

Claims

1. A method of providing message communications with failure detection and recovery in a linear communication orbit formed by a non-static collection of machines, the method comprising:

at a first machine of the non-static collection of machines forming the linear communication orbit, wherein the first machine has a set of direct contacts comprising a set of machines distributed along the linear communication orbit;

monitoring a current propagation state of a first query that has departed from the first machine to travel in a forward direction along the linear communication orbit;

detecting a propagation failure of the first query corresponding to the current propagation state of the first query, including detecting a failure to receive an acknowledgement of the first query from a first direct contact among the set of direct contacts within a predetermined timeout corresponding to the first direct contact, wherein the first direct contact is located in an unanswered range of the first query downstream of the first machine along the linear communication orbit, and wherein there is at least one machine located between the first machine and the first direct contact of the first machine along the linear communication orbit; and

in accordance with detection of the propagation failure of the first query corresponding to the current propagation state of the first query, sending the first query directly to the first direct contact of the first machine, wherein the first direct contact of the first machine is configured to initiate failure recovery within at least part of a respective segment of the linear communication orbit between the first machine and the first direct contact of the first machine.

2. The method of claim 1, including:

detecting that sending the first query directly to the first direct contact of the first machine has failed; and

in accordance with the failure to send the first query directly to the first direct contact of the first machine, sending the first query directly to a second direct contact among the set of direct contacts of the first machine that is located within the unanswered range of the first query downstream of the first machine along the linear communication orbit, wherein the second direct contact is located downstream of the first direct contact of the first machine along the linear communication orbit, and wherein the second direct contact is configured to initiate failure recovery within at least part of a respective segment of the linear communication orbit between the first machine and the second direct contact of the first machine.

3. The method of claim 2, including:

determining a respective responsibility tier of the first machine for the first query based on a predetermined responsibility hierarchy rule, wherein the predetermined responsibility hierarchy rule assigns machines in the non-static collection of machines into a respective responsibility hierarchy for the first query, and wherein the second direct contact of the first machine has a higher responsibility tier than the first direct contact of the first machine in the respective responsibility hierarchy for the first query.

4. The method of claim 3, including:

updating the current propagation state of the first query based on new known positions of the first query in the linear communication orbit; and

ceasing to monitor the current propagation state of the first query in accordance with a determination that the first query has reached a second machine downstream of the first machine along the linear communication orbit that has a higher responsibility tier than the first machine in the respective responsibility hierarchy for the first query.

5. The method of claim 1, including:

receiving a second query directly from a third direct contact among the set of direct contacts of the first machine, wherein the second query was propagating through the linear communication orbit in the forward direction prior to the first machine receiving the second query directly from the third direct contact, the third direct contact is located in an unanswered range of the second query upstream of the first machine along the linear communication orbit, and wherein there is at least one machine located between the first machine and the third direct contact of the first machine along the linear communication orbit; and

in response to receiving the second query directly from the third direct contact, sending the second query directly to a fourth direct contact among the set of direct contacts of the first machine to recover from a propagation failure of the second query between the first machine and the third direct contact of the first machine, wherein the second query resumes propagation in the forward direction within at least part of a respective segment of the linear communication orbit between the third direct contact of the first machine and the first machine.

6. The method of claim 5, including:

detecting that sending the second query directly to the fourth direct contact of the first machine has failed; and

in accordance with the failure to send the second query directly to the fourth direct contact of the first machine, sending the second query directly to a fifth direct contact among the set of direct contacts of the first machine that is located in the unanswered range of the second query downstream of the fourth direct contact of the first machine along the linear communication orbit, wherein the second query resumes propagation in the forward direction within at least part of a respective segment of the linear communication orbit between the fourth direct contact of the first machine and the first machine.

7. The method of claim 6, including:

determining a respective responsibility tier of the first machine for the second query based on a predetermined responsibility hierarchy rule, wherein the predetermined responsibility hierarchy rule assigns machines in the non-static collection of machines into a respective responsibility hierarchy for the second query, and wherein the fifth direct contact of the first machine has a lower responsibility tier than the fourth direct contact of the first machine in the respective responsibility hierarchies of the second query.

8. A non-transitory computer-readable medium, having instructions stored thereon, which when executed by one or more processors cause the processors to perform operations comprising:

at a first machine of a non-static collection of machines forming a linear communication orbit, wherein the first machine has a set of direct contacts comprising a set of machines distributed along the linear communication orbit;

monitoring a current propagation state of a first query that has departed from the first machine to travel in a forward direction along the linear communication orbit;

detecting a propagation failure of the first query corresponding to the current propagation state of the first query, including detecting a failure to receive an acknowledgement of the first query from a first direct contact among the set of direct contacts within a predetermined timeout corresponding to the first direct contact, wherein the first direct contact is located in an unanswered range of the first query downstream of the first machine along the linear communication orbit, and wherein there is at least one machine located between the first machine and the first direct contact of the first machine along the linear communication orbit; and

in accordance with detection of the propagation failure of the first query corresponding to the current propagation state of the first query, sending the first query directly to the first direct contact of the first machine, wherein the first direct contact of the first machine is configured to initiate failure recovery within at least part of a respective segment of the linear communication orbit between the first machine and the first direct contact of the first machine.

9. The non-transitory computer-readable medium of claim 8, wherein the operations include:

detecting that sending the first query directly to the first direct contact of the first machine has failed; and

in accordance with the failure to send the first query directly to the first direct contact of the first machine, sending the first query directly to a second direct contact among the set of direct contacts of the first machine that is located within the unanswered range of the first query downstream of the first machine along the linear communication orbit, wherein the second direct contact is located downstream of the first direct contact of the first machine along the linear communication orbit, and wherein the second direct contact is configured to initiate failure recovery within at least part of a respective segment of the linear communication orbit between the first machine and the second direct contact of the first machine.

10. The non-transitory computer-readable medium of claim 9, wherein the operations include:

determining a respective responsibility tier of the first machine for the first query based on a predetermined responsibility hierarchy rule, wherein the predetermined responsibility hierarchy rule assigns machines in the non-static collection of machines into a respective responsibility hierarchy for the first query, and wherein the second direct contact of the first machine has a higher responsibility tier than the first direct contact of the first machine in the respective responsibility hierarchy for the first query.

11. The non-transitory computer-readable medium of claim 10, wherein the operations include:

updating the current propagation state of the first query based on new known positions of the first query in the linear communication orbit; and

ceasing to monitor the current propagation state of the first query in accordance with a determination that the first query has reached a second machine downstream of the first machine along the linear communication orbit that has a higher responsibility tier than the first machine in the respective responsibility hierarchy for the first query.

12. The non-transitory computer-readable medium of claim 8, wherein the operations include:

receiving a second query directly from a third direct contact among the set of direct contacts of the first machine, wherein the second query was propagating through the linear communication orbit in the forward direction prior to the first machines receiving the second query directly from the third direct contact, the third direct contact is located in an unanswered range of the second query upstream of the first machine along the linear communication orbit, and wherein there is at least one machine located between the first machine and the third direct contact of the first machine along the linear communication orbit; and

in response to receiving the second query directly from the third direct contact, sending the second query directly to a fourth direct contact among the set of direct contacts of the first machine to recover from a propagation failure of the second query between the first machine and the third direct contact of the first machine, wherein the second query resumes propagation in the forward direction within at least part of a respective segment of the linear communication orbit between the third direct contact of the first machine and the first machine.

13. The non-transitory computer-readable medium of claim 12, wherein the operations include:

detecting that sending the second query directly to the fourth direct contact of the first machine has failed; and

in accordance with the failure to send the second query directly to the fourth direct contact of the first machine, sending the second query directly to a fifth direct contact among the set of direct contacts of the first machine that is located in the unanswered range of the second query downstream of the fourth direct contact of the first machine along the linear communication orbit, wherein the second query resumes propagation in the forward direction within at least part of a respective segment of the linear communication orbit between the fourth direct contact of the first machine and the first machine.

14. The non-transitory computer-readable medium of claim 13, wherein the operations include:

determining a respective responsibility tier of the first machine for the second query based on a predetermined responsibility hierarchy rule, wherein the predetermined responsibility hierarchy rule assigns machines in the non-static collection of machines into a respective responsibility hierarchy for the second query, and wherein the fifth direct contact of the first machine has a lower responsibility tier than the fourth direct contact of the first machine in the respective responsibility hierarchies of the second query.

15. A first machine, comprising:

one or more processors; and

memory having instructions stored thereon, which when executed by the one or more processors cause the processors to perform operations, wherein;

the first machine is among a non-static collection of machines forming a linear communication orbit,

the first machine has a set of direct contacts comprising a set of machines distributed along the linear communication orbit, and

the operations include;

monitoring a current propagation state of a first query that has departed from the first machine to travel in a forward direction along the linear communication orbit;

detecting a propagation failure of the first query corresponding to the current propagation state of the first query, including detecting a failure to receive an acknowledgement of the first query from a first direct contact among the set of direct contacts within a predetermined timeout corresponding to the first direct contact, wherein the first direct contact is located in an unanswered range of the first query downstream of the first machine along the linear communication orbit, and wherein there is at least one machine located between the first machine and the first direct contact of the first machine along the linear communication orbit; and

in accordance with detection of the propagation failure of the first query corresponding to the current propagation state of the first query, sending the first query directly to the first direct contact of the first machine, wherein the first direct contact of the first machine is configured to initiate failure recovery within at least part of a respective segment of the linear communication orbit between the first machine and the first direct contact of the first machine.

16. The first machine of claim 15, wherein the operations include:

detecting that sending the first query directly to the first direct contact of the first machine has failed; and

in accordance with the failure to send the first query directly to the first direct contact of the first machine, sending the first query directly to a second direct contact among the set of direct contacts of the first machine that is located within the unanswered range of the first query downstream of the first machine along the linear communication orbit, wherein the second direct contact is located downstream of the first direct contact of the first machine along the linear communication orbit, and wherein the second direct contact is configured to initiate failure recovery within at least part of a respective segment of the linear communication orbit between the first machine and the second direct contact of the first machine.

17. The first machine of claim 16, wherein the operations include:

determining a respective responsibility tier of the first machine for the first query based on a predetermined responsibility hierarchy rule, wherein the predetermined responsibility hierarchy rule assigns machines in the non-static collection of machines into a respective responsibility hierarchy for the first query, and wherein the second direct contact of the first machine has a higher responsibility tier than the first direct contact of the first machine in the respective responsibility hierarchy for the first query.

18. The first machine of claim 17, wherein the operations include:

updating the current propagation state of the first query based on new known positions of the first query in the linear communication orbit; and

ceasing to monitor the current propagation state of the first query in accordance with a determination that the first query has reached a second machine downstream of the first machine along the linear communication orbit that has a higher responsibility tier than the first machine in the respective responsibility hierarchy for the first query.

19. The first machine of claim 15, wherein the operations include:

receiving a second query directly from a third direct contact among the set of direct contacts of the first machine, wherein the second query was propagating through the linear communication orbit in the forward direction prior to the first machine receiving the second query directly from the third direct contact, the third direct contact is located in an unanswered range of the second query upstream of the first machine along the linear communication orbit, and wherein there is at least one machine located between the first machine and the third direct contact of the first machine along the linear communication orbit; and

in response to receiving the second query directly from the third direct contact, sending the second query directly to a fourth direct contact among the set of direct contacts of the first machine to recover from a propagation failure of the second query between the first machine and the third direct contact of the first machine, wherein the second query resumes propagation in the forward direction within at least part of a respective segment of the linear communication orbit between the third direct contact of the first machine and the first machine.

20. The first machine of claim 19, wherein the operations include:

detecting that sending the second query directly to the fourth direct contact of the first machine has failed; and

in accordance with the failure to send the second query directly to the fourth direct contact of the first machine, sending the second query directly to a fifth direct contact among the set of direct contacts of the first machine that is located in the unanswered range of the second query downstream of the fourth direct contact of the first machine along the linear communication orbit, wherein the second query resumes propagation in the forward direction within at least part of a respective segment of the linear communication orbit between the fourth direct contact of the first machine and the first machine.

21. The first machine of claim 20, wherein the operations include:

determining a respective responsibility tier of the first machine for the second query based on a predetermined responsibility hierarchy rule, wherein the predetermined responsibility hierarchy rule assigns machines in the non-static collection of machines into a respective responsibility hierarchy for the second query, and wherein the fifth direct contact of the first machine has a lower responsibility tier than the fourth direct contact of the first machine in the respective responsibility hierarchies of the second query.