Systems and methods for implementing distributed scheduling capabilities for computing clusters

1 . A method of distributing scheduling of a task within a plurality of nodes of a distributed computing system having no central scheduler controller, the method comprising:

(a) providing a plurality of interconnected nodes, each respective interconnected node comprising a distributed state scheduler and accessing its own respective node database storing performance data comprising historical success rates about other nodes in the plurality of nodes based on prior task execution requests,

(b) determining, at a first node in the plurality of interconnected nodes, a first task to be run for the first node by a predetermined time deadline, wherein the first task is configured to be run by a node other than the first node;

(c) selecting, based on a penalty-based cost function, a first set of worker nodes from the plurality of interconnected nodes, wherein the first node selects each respective worker node in the first set based on respective performance data that the first node accesses about the respective worker node, the performance data including a probability of successful completion calculated from the historical success rates;

(d) sending, from the first node to each node in the first set of worker nodes, a request to execute the first task;

(e) communicating, if the first node receives an indication that execution of the first task was completed by a second node in the first set before the predetermined time deadline, a notification to the first set of worker nodes that the first task is complete;

(f) stopping, by worker nodes that have started executing the first task, their instances of the first task responsive to receiving the notification;

(g) associating, based on the penalty-based cost function, a first penalty at the first node, if the first node does not receive an indication that execution of the first task was completed before the predetermined time deadline, the penalty-based cost function is determined as EPj=Vj(1−|Cj|), where Vj is a job value and |Cj| is a probability that the first task j will be completed in time; and

(h) updating performance data for each worker node in the first set of worker nodes, the updating indicative of whether or not the respective worker node succeeded in executing the first task by the predetermined time deadline, the updating modifies the probability of successful completion used in subsequent worker node selections.

2 . The method of claim 1 , further comprising:

(i) selecting a second set of worker nodes from the plurality of interconnected nodes, wherein the first node selects each respective worker node in the first set so that the second set of worker nodes comprises at least one worker node that was not in the first set; and

(i) repeating (d) through (h) using the second set of worker nodes.

3 . The method of claim 1 , wherein the first node is configured to run a mission comprising a plurality of tasks and is further configured to repeat (b) through (e) for each of the plurality of tasks.

4 . The method of claim 1 , further comprising: (i) updating performance data, accessed by the first node, for each respective worker node in the first set of worker nodes, the updating indicative of whether or not any one or more of the respective worker nodes have spare computing resources.

5 . The method of claim 1 further comprising: (i) configuring each respective worker node in the first set that received a notification that the first task is complete, to stop any instances of the first task running at that node.

6 . The method of claim 1 , wherein the method is implemented within a Kubernetes system.

7 . The method of claim 1 , wherein the performance data comprises data specifying computing resource capability information for each of the other respective nodes in the plurality of interconnected nodes.

8 . The method of claim 1 , wherein the performance data comprises data specifying, for each of the other respective nodes in the plurality of interconnected nodes, a set of historical data about each other respective node's responses to at least one past task execution request from the respective interconnected node that accesses the node database.

9 . The method of claim 1 , wherein the penalty-based cost function EPj expresses a likelihood that a penalty is incurred if the first node attempts to run the first task, and wherein when the first task is attempted on a group of peer nodes denoted by indices k=1, 2, . . . n, each having a different rate of success for the first task denoted by |Cjk|, an expected penalty is given by:

EPj

=

Vj

·

(

1

-

❘

"\[LeftBracketingBar]"

⋃

k

=

1

n

Cjk

❘

"\[RightBracketingBar]"

)

where the probability of success Cjk is computed by the first node based on its historical record of interacting with node k.

10 . The method of claim 1 , wherein updating performance data comprises calculating a current success rate C for a worker node as a finite approximation of a definite integral of an exponential decay function over n results, according to:

C

=

FN

⁡

(

K

,

n

)

·

∑

i

=

1

n

(

t

i

-

t

i

-

1

)

·

(

min

⁡

(

w

i

⁢

y

i

,

w

0

⁢

y

0

)

+

abs

(

w

i

⁢

y

i

-

w

i

-

1

⁢

y

i

-

1

)

/

2

where i=n is a most recent result, t i is a time an i-th request was sent, y i is an outcome of the i-th request encoded as 0 or 1, w i is a value of a decay function at time t i , and FN is a normalization function.

11 . The method of claim 1 , wherein selecting the first set of worker nodes comprises:

defining a computation space for each candidate worker node having an area that denotes a total computation capacity of the candidate worker node, wherein dimensions of the computation space are measured in units of computation (UoC);

defining the first task in terms of a total first UoC that the first task requires, wherein the first task is representable as a first shape having dimensions corresponding to a minimum degree of parallelism and a maximum degree of parallelism; and

determining whether the candidate worker node can run the first task based on whether the first shape fits entirely within the area of the computation space of the candidate worker node.

12 . The method of claim 1 , further comprising:

calculating a job speed-up metric (Jsu) to estimate performance of the distributed computing system, wherein:

a reference speed per core (Sb) is defined for a known node;

performance data is received for the second node comprising: a speed Sn of a CPU at the second node, a number of processing cores (CPUs) used to perform the first task, and a total actual time Tn a second node took to perform the first task;

an expected time Tj is determined that the second node was expected to perform the first task based on: Tj=t*(Sn/Sb)*(CPUs/1000); and

the job speed-up metric is determined as: Jsu=Tj/Tn.

13 . A distributed computing system for distributing scheduling of a task within a plurality of nodes without a centralized scheduler controller, the system comprising:

a plurality of heterogeneous interconnected nodes forming a cluster, each respective interconnected node comprising:

a distributed state scheduler, and

a respective node database storing performance data about other nodes in the plurality, wherein the performance data comprises historical success rates from prior task execution requests;

a first node of the plurality of interconnected nodes comprising a processor and memory, the memory storing instructions executable on the processor, the instructions causing the processor to:

determine, at the first node in the plurality of interconnected nodes, a first task to be run for the first node by a predetermined time deadline, the first task is configured to be run by a node other than the first node;

calculate a probability of successful completion for candidate worker nodes based on the historical success rates stored in the node database at the first node;

select a first set of worker nodes from the plurality of interconnected nodes using a penalty-based cost function, the first node selects each respective worker node in the first set based on the calculated probability of successful completion for the respective worker node;

send, from the first node to each node in the first set of worker nodes, a request to execute the first task;

notify, if the first node receives an indication that execution of the first task was completed by a second node in the first set before the predetermined time deadline, the first set of worker nodes that the first task is complete thereby causing worker nodes that have started executing the first task to stop their instances;

calculate and associate a first penalty at the first node if the first node does not receive an indication that execution of the first task was completed before the predetermined time deadline, the penalty is calculated as EPj=Vj(1−|Cj|), where Vj is a task value and |Cj| is the probability that the first task j will be completed in time; and

update performance data in the node database at the first node for each worker node in the first set of worker nodes, the updating modifying the historical success rates based on whether or not the respective worker node succeeded in executing the first task by the predetermined time deadline.

14 . The system of claim 13 , wherein the memory is further configured for storing instructions executable on the processor, the instructions causing the processor to update performance data, accessed by the first node, for each respective worker node in the first set of worker nodes, the updating indicative of whether or not any one or more of the respective worker nodes have spare computing resources.

15 . The system of claim 13 , wherein the memory is further configured for storing instructions executable on the processor, the instructions causing the processor to configure each respective worker node in the first set that received a notification that the first task is complete, to stop any instances of the first task running at that node.

16 . The system of claim 13 , wherein the system comprises a Kubernetes system.

17 . The system of claim 13 , wherein the performance data comprises data specifying computing resource capability information, for each of the other respective nodes in the plurality of interconnected nodes.

18 . The system of claim 13 , wherein the performance data comprises data specifying, for each of the other respective nodes in the plurality of interconnected nodes, a set of historical data about the other respective node's responses to at least one past task execution request from the respective interconnected node that accesses the node database.

19 . The system of claim 13 , wherein the system comprises a modified Kubernetes orchestration system, wherein a standard Kubernetes kube-scheduler includes a modification to support the distributed state scheduler at each node, and wherein the modification enables peer-to-peer scheduling capability while maintaining compatibility with Kubernetes application programming interface (API).