Self-organizing distributed task coordination for ad-hoc computing environment

• US 10,448,454 B1
• Filed: 03/21/2016
• Issued: 10/15/2019
• Est. Priority Date: 03/21/2016
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Inventors: Tao, Simon, Cao, Yu, Guo, Xiaoyan, Dong, Zhe, Durazzo, Kenneth
• Primary Examiner(s): Patel, Chirag R
• Application Number:
  US15/076,069
• Time in Patent Office: 1,303 Days
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 9/48 Program initiating; Program switching, e.g. by interrupt
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: H04L 45/60 Router architectures
• 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/51 Discovery or management thereof, e.g. service location protocol [SLP] or web services
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

Processing nodes in a distributed ad-hoc computing environment are discovered, wherein each processing node is configured to discover other processing nodes. A set of candidate processing nodes is selected from the discovered processing nodes. Selection is based on each discovered processing node advertising its own capabilities to other processing nodes, and processing nodes are selected as candidates based on their advertised capabilities. A subset of processing nodes is formed from the set of candidate processing nodes. The subset of processing nodes forms a self-organized task coordination ensemble wherein each processing node in the task coordination ensemble executes the same consensus protocol. By way of example, the distributed ad-hoc computing environment comprises an IoT network and the processing nodes are IoT devices.

Claims

1. A method, comprising:

discovering processing nodes in a distributed ad-hoc wireless computing environment comprising an Internet of Things (IoT) network, wherein each processing node is configured to discover other processing nodes, wherein the processing nodes are IoT devices;

selecting a set of candidate processing nodes from the discovered processing nodes, wherein selection is based on each discovered potential-candidate processing node advertising its own capabilities to other potential-candidate processing nodes, and potential-candidate processing nodes being selected as candidates based on their advertised capabilities; and

forming a subset of processing nodes from the set of candidate processing nodes, wherein the subset of processing nodes form a self-organized task coordination ensemble wherein each processing node in the task coordination ensemble executes the same consensus protocol;

wherein the task coordination ensemble is leveraged to elect one of the processing nodes as a leader in the task coordination ensemble;

wherein the leader exclusively functions as a task assigner at a given time instance;

wherein each processing node in the task coordination ensemble is capable of serving as the leader during a given time period; and

wherein each processing node in the task coordination ensemble comprises a state machine such that the same state machine representation is replicated in each processing node and each processing node is thus able to perform the same task when one processing node in the ensemble fails.

2. The method of claim 1, further comprising the task coordination ensemble balancing a processing load across each processing node of the task coordination ensemble.

3. The method of claim 1, further comprising identifying processing nodes in the task coordination ensemble as at least one of a service provider and a service consumer.

4. The method of claim 3, wherein the processing nodes in the task coordination ensemble publish services they can provide and subscribe to services upon which they depend.

5. The method of claim 4, further comprising the task coordination ensemble maintaining a service and dependency registry based on the publishing and subscribing functions of the processing nodes of the task coordination ensemble.

6. The method of claim 1, further comprising adding a new processing node from the set of candidate processing nodes to the task coordination ensemble when one of the existing processing nodes in the task coordination ensemble fails.

7. The method of claim 1, wherein advertised capabilities used to select processing nodes as candidates comprise at least one of:

computing power, storage durability;

inter-processing node connection reliability; and

power supply capacity.

8. The method of claim 7, wherein processing nodes are selected as candidate processing nodes when they meet a predetermined minimum threshold for their advertised capabilities.

9. The method of claim 1, wherein the advertised capabilities used to select processing nodes as candidates are advertised via a REST-based interface.

10. The method of claim 1, wherein at least two of the processing nodes are different IoT devices having different capabilities, and include at least one of a smartphone, a sensor, an actuator, or an RFID tag.

11. A method, comprising:

a given processing node in a distributed ad-hoc wireless computing environment comprising an Internet of Things (IoT) network and participating in a discovery stage as a potential-candidate processing node by advertising its capabilities to other potential-candidate processing nodes in the distributed ad-hoc computing environment, wherein the given processing node is selected into a set of candidate processing nodes based on its own capabilities meeting a predetermined minimum threshold; and

the given processing node participating in a subset of processing nodes from the set of candidate processing nodes to form a self-organized task coordination ensemble, wherein each processing node in the task coordination ensemble executes the same consensus protocol and wherein the processing nodes are IoT devices;

wherein the task coordination ensemble is leveraged to elect one of the processing nodes as a leader in the task coordination ensemble;

wherein the leader exclusively functions as a task assigner at a given time instance;

wherein each processing node in the task coordination ensemble is capable of serving as the leader during a given time period; and

wherein each processing node in the task coordination ensemble comprises a state machine such that the same state machine representation is replicated in each processing node and each processing node is thus able to perform the same task when one processing node in the ensemble fails.

12. The method of claim 11, further comprising the processing node participating in a balancing of a processing load across each processing node of the task coordination ensemble.

13. The method of claim 11, further comprising identifying processing nodes in the task coordination ensemble as at least one of a service provider and a service consumer.

14. The method of claim 13, wherein the processing nodes in the task coordination ensemble publish services they can provide and subscribe to services upon which they depend.

15. The method of claim 11, further comprising adding a new processing node from the set of candidate processing nodes to the task coordination ensemble when one of the existing processing nodes in the task coordination ensemble fails.

16. The method of claim 11, wherein advertised capabilities used to select processing nodes as candidates comprise at least one of:

computing power, storage durability;

inter-processing node connection reliability; and

power supply capacity.

17. The method of claim 16, wherein processing nodes are selected as candidate processing nodes when they meet a predetermined minimum threshold for their advertised capabilities.

18. A system, comprising:

a set of physical processing devices; and

a set of processing nodes in a distributed wireless ad-hoc computing environment comprising an IoT network, the processing nodes being IoT devices and implemented on the set of physical processing devices, the set of processing nodes configured to form a self-organized task coordination ensemble, the task coordination ensemble being formed by;

discovering processing nodes in the distributed ad-hoc computing environment, wherein each processing node is configured to discover other processing nodes;

selecting a set of candidate processing nodes from the discovered processing nodes, wherein selection is based on each discovered potential-candidate processing node advertising its own capabilities to other potential-candidate processing nodes, and potential-candidate processing nodes being selected as candidates based on their advertised capabilities; and

forming a subset of processing nodes from the set of candidate processing nodes, wherein the subset of processing nodes form the self-organized task coordination ensemble, wherein each processing node in the task coordination ensemble executes the same consensus protocol;

wherein the task coordination ensemble is leveraged to elect one of the processing nodes as a leader in the task coordination ensemble;

wherein the leader exclusively functions as a task assigner at a given time instance;

wherein each processing node in the task coordination ensemble is capable of serving as the leader during a given time period; and

wherein each processing node in the task coordination ensemble comprises a state machine such that the same state machine representation is replicated in each processing node and each processing node is thus able to perform the same task when one processing node in the ensemble fails.

19. The system of claim 18, wherein a processing load is balanced across each of the processing nodes of the task coordination ensemble.

20. The system of claim 18, wherein at least two of the processing nodes are different IoT devices having different capabilities, and include at least one of a smartphone, a sensor, an actuator, or an RFID tag.