Decentralized scheduler of computation jobs for unstable network of heterogenous nodes
A decentralized scheduler node for an unstable network of heterogenous nodes collects status information including a resource capacity of each of a network of nodes with which it is in communication. For each current computation job in its input queue, the scheduler node determines which connected nodes have suitable resource capacity to execute the current job and a reliability of each suitable node based on statistical evaluation of its historical availability for job deployment. From the set of suitably powerful and reliable candidate nodes, the scheduler node selects a candidate node of sufficient resource capacity for deployment of the current job based on the probability of a subsequent job appearing during the execution time of the current job, the subsequent job having an equivalent or greater resource requirement and thus at risk of waiting in the input queue if the selected node is required for executing the subsequent job.
1 . A scheduler node comprising:
one or more processors;
memory operatively coupled to the one or more processors,
the memory configured for storage of a list of one or more jobs for deployment to a network of nodes known to the scheduler node, each job associated with a job resources requirement and a job execution time; and
a communications interface operatively coupled to the one or more processors, the communications interface configured for transmission to, and reception from, the network of nodes;
the scheduler node configured to, for at least one current job of the list of one or more jobs:
collect status information from the network of nodes, the status information including, for each node, one or more of a node resource capacity or a node availability time, wherein:
each candidate node of a first subset of one or more candidate nodes within the network of nodes has a resource capacity greater than or equal to a sufficient resource capacity, wherein the sufficient resource capacity is based on the job resources requirement associated with the current job; and
each candidate node of a second subset of candidate nodes within the first subset has a reliability sufficient for execution of the current job, wherein the reliability is based on a probability that the candidate node in the second subset can execute the current job based on the job execution time and the node availability time of the candidate node; and
deploy the current job to a particular candidate node of the second subset for execution, wherein:
the particular candidate node executes the current job;
the particular candidate node is based on a local optimization of job deployments relative to other nodes in the network of nodes;
the local optimization is based on a sum of one or more probability distributions associated with one or more subsequent jobs and a threshold probability level for each of the candidate nodes in the second subset;
the threshold probability level is based on a probability that the candidate node of the second subset has at least one of a node resource capacity greater than or equal the job resources requirement of the one or more subsequent jobs or a reliability greater than or equal to a reliability sufficient for execution of the one or more subsequent jobs;
the one or more probability distributions are based on (i) at least one of the job resources requirement and the resource capacity of each of the second subset of candidate nodes, and (ii) one or more cumulative distribution functions associated with one or more subsequent jobs appearing in the list of one or more jobs during the job execution time; and
the one or more subsequent jobs are associated with a job resources requirement greater than the job resources requirement of the current job.
2 . The scheduler node of claim 1 , wherein the scheduler node is configured to collect, via the communications interface, the status information from at least one node of the network.
3 . The scheduler node of claim 1 , wherein:
the memory is configured for storage of historical status information associated with the at least one node of the network of nodes; and
the scheduler node is configured to collect the status information by retrieving the historical status information from the memory.
4 . The scheduler node of claim 1 , wherein the scheduler node is configured to modify the network of one or more nodes based on the collected status information by at least one of:
adding at least one node to the network; or
deleting at least one node from the network.
5 . The scheduler node of claim 1 , wherein at least one of the first subset of candidate nodes or the second subset of candidate nodes are ordered by node resource capacity.
6 . The scheduler node of claim 5 , wherein for each candidate node of the first subset, a node reliability is based at least on the execution time of the current job and the node availability time of the candidate node; and
the order of the second subset of candidate nodes is ordered primarily by node resource capacity and secondarily by node reliability.
7 . The scheduler node of claim 5 , wherein the scheduler node is configured to generate the second subset of candidate nodes by removing each candidate node of the first subset from the first subset having a node reliability insufficient for the execution time.
8 . The scheduler node of claim 5 , wherein the particular candidate node has the highest node resource capacity in the second subset of candidate nodes according to a descending order of node resource capacity of the second subset of candidate nodes, and wherein the probability of the subsequent job appearing in the list of one or more jobs does not exceed a threshold level.
9 . The scheduler node of claim 8 , wherein:
the probability of the subsequent job appearing in the list of one or more jobs exceeds the threshold level for each candidate node of the second subset; and
the particular candidate node has the least node resource capacity in the second subset of candidate nodes.
10 . The scheduler node of claim 1 , wherein the particular candidate node is a first node of the network, and the scheduler node is configured to:
receive a rejection of the deployed current job from the particular candidate node; and
redeploy the current job to a different second node of the network.
11 . A method comprising:
storing, via a memory of a scheduler node, a list of one or more jobs for execution by a network of nodes known to the scheduler node, each job associated with a resource requirement and an execution time;
collecting, via the scheduler node, status information from the network of nodes, the status information including, for each node, one or more of a node resource capacity or a node availability time, wherein:
each candidate node of a first subset of one or more candidate nodes within the network of nodes has a resource capacity greater than or equal to a sufficient resource capacity, wherein the sufficient resource capacity is based on the job resources requirement associated with the current job; and
each candidate node of a second subset of one or more candidate nodes within the first subset has a reliability sufficient for execution of the current job, wherein the reliability is based on a probability that the candidate node in the second subset can execute the current job based on the job execution time and the node availability time of the candidate node; and
deploying the current job to a particular candidate node of the second subset for execution, wherein:
the particular candidate node executes the current job;
the particular candidate node is based on a local optimization of job deployments relative to other nodes in the network of nodes;
the local optimization is based on a sum of one or more probability distributions associated with one or more subsequent jobs and a threshold probability level for each of the candidate nodes in the second subset;
the threshold probability level is based on a probability that the candidate node of the second subset has at least one of a node resource capacity greater than or equal the job resources requirement of the one or more subsequent jobs or a reliability greater than or equal to a reliability sufficient for execution of the one or more subsequent jobs;
the one or more probability distributions are based on (i) at least one of the job resources requirement and the resource capacity of each of the second subset of candidate nodes, and (ii) one or more cumulative distribution functions associated with one or more subsequent jobs appearing in the list of one or more jobs during the job execution time; and
the one or more subsequent jobs are associated with a job resources requirement greater than the job resources requirement of the current job.
12 . The method of claim 11 , wherein collecting, via a scheduler node, status information associated with a network of two or more nodes communicatively coupled to the scheduler node includes: collecting the status information from at least one node of the network.
13 . The method of claim 11 , wherein: storing, via a memory of a scheduler node, a list of one or more jobs for deployment to a network includes storing, via the memory, historical status information associated with the network of nodes; and wherein collecting, via the scheduler node, status information associated with the one or more nodes includes retrieving the historical status information from the memory.
14 . The method of claim 11 , wherein collecting, via the scheduler node, status information associated with the one or more nodes includes at least one of:
adding at least one node to the network based on the collected status information; or
deleting at least one node from the network based on the collected status information.
15 . The method of claim 11 , wherein at least one of the first subset or the second subset of one or more candidate nodes are ordered by node resource capacity.
16 . The method of claim 15 , wherein for each candidate node of the first subset, a node reliability is based at least on the node availability time of the candidate node; and
the ordering of the second subset of one or more candidate nodes is ordered primarily by node resource capacity and secondarily by node reliability.
17 . The method of claim 16 , further comprising:
removing, from the first subset, each candidate node of the first subset having a node reliability insufficient for the execution time.
18 . The method of claim 15 , wherein the particular candidate node has the highest node resource capacity in the second subset of candidate nodes according to a descending order of node resource capacity of the second subset of candidate nodes, and wherein the probability of the subsequent job appearing in the list of one or more jobs does not exceed a threshold level.
19 . The method of claim 18 , wherein the probability of the subsequent job appearing in the list of one or more jobs exceeds the threshold level for each candidate node of the second subset, and wherein the particular candidate node has the least node resource capacity in the second subset of candidate nodes.
20 . The method of claim 11 , wherein the particular candidate node is a first node of the network, the method further comprising:
receiving, via the scheduler node, a rejection of the current job from the particular candidate node; and
deploying, via the scheduler node, the current job to a different second node of the network.