# US 2020/0401445 A1 · Graph data based task scheduling method, apparatus and storage medium thereof

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2020/0401445 A1
- Document ID: US20200401445A1
- Status: Published application
- Kind: A1
- Application number: 17/009,342
- Filed: 2020-09-01
- Published: 2020-12-24
- Earliest claimed: 2018-05-16
- Assignees: Tencent Technology (Shenzhen) Company Limited
- Applicants: Tencent Technology (Shenzhen) Company Limited
- Inventors: Bo ZHENG
- Web page: https://patentgrep.com/patent/US20200401445A1

## CPC

- G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues}
- G06F 9/5038: {considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration (scheduling strategies G06F9/4881 and subgroups)}
- G06F 9/485: {Task life-cycle, e.g. stopping, restarting, resuming execution (G06F9/4881 takes precedence)}
- G06F 9/5066: {Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs (mappping at compile time, see G06F8/451)}
- G06F 9/5088: {involving task migration}
- G06F 16/2379: {Updates performed during online database operations; commit processing}
- G06F 16/27: Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
- G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)}
- H04L 9/3239: {involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD}
- H04L 9/50: {using hash chains, e.g. blockchains or hash trees}
- G06F 2209/5017: Task decomposition
- G06F 2209/5022: Workload threshold
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

This disclosure relates to a graph-data-based task scheduling method, which includes: obtaining subgraph data divided from graph data to be processed by a computing node, performing a unit computing task for a graph node in the subgraph data, obtaining a first quantized value corresponding to a completed unit computing task in response to data corresponding to the completed unit computing task being formed into blockchain data, obtaining a second quantized value corresponding to the completed unit computing task in response to the data corresponding to the completed unit computing task being not formed into blockchain data, determining a third quantized value corresponding to an uncompleted unit computing task in the subgraph data, and exchanging the graph node and the first quantized value with another computing node in response to the second quantized value and the third quantized value failing to meet an equilibrium condition.

## Claims

### Claim 1

A graph data based task scheduling method, comprising:
obtaining subgraph data divided from graph data to be processed by a computing node;
performing a unit computing task for a graph node in the subgraph data;
obtaining a first quantized value, the first quantized value being a quantized value corresponding to a completed unit computing task in response to data corresponding to the completed unit computing task being formed into blockchain data;
obtaining a second quantized value, the second quantized value being a quantized value corresponding to the completed unit computing task in response to the data corresponding to the completed unit computing task being not formed into blockchain data;
determining a third quantized value corresponding to an uncompleted unit computing task in the subgraph data; and
exchanging the graph node and the first quantized value with another computing node in response to the second quantized value and the third quantized value failing to meet an equilibrium condition.

### Claim 2 (depends on 1)

The method of claim 1, wherein the obtaining the subgraph data divided from the graph data to be processed comprises:
obtaining task information corresponding to the graph data and broadcast in a blockchain network; and
reading, according to the task information, a task-executable file and the subgraph data divided from the graph data; and
the performing the unit computing task for the graph node in the subgraph data comprises:
performing the task-executable file according to the subgraph data, the task-executable file indicating the unit computing task for the graph node in the subgraph data.

### Claim 3 (depends on 1)

The method of claim 1, wherein the obtaining a first quantized value comprises:
writing global computing data corresponding to the completed unit computing task into a new block; and
after the new block being verified by a blockchain network,
adding the new block into the blockchain network to form blockchain data, and
generating the first quantized value corresponding to the completed unit computing task.

### Claim 4 (depends on 3)

The method of claim 3, wherein the obtaining a second quantized value comprises:
obtaining a historical second quantized value before the global computing data being written into the new block, the historical second quantized value corresponding to a completed unit computing task that does not form blockchain data; and
subtracting the first quantized value from the historical second quantized value to obtain the second quantized value.

### Claim 5 (depends on 1)

The method of claim 1, wherein the determining the third quantized value comprises:
obtaining latest global computing data from a blockchain network;
obtaining local computing data corresponding to the completed unit computing task; and
determining the third quantized value according to the subgraph data, a quantity of completed unit computing tasks, the latest global computing data, and the local computing data.

### Claim 6 (depends on 1)

The method of claim 1, wherein the method further comprises:
obtaining a first sum of current second quantized values of the subgraph data;
obtaining a second sum of current third quantized values of the subgraph data;
determining a contrast value of the second sum relative to the first sum; and
determining that the second quantized value and the third quantized value fail to meet the equilibrium condition in response to the contrast value being outside a specified range.

### Claim 7 (depends on 6)

The method of claim 6, wherein the determining the contrast value comprises:
calculating the contrast value using a formula:
log
a
m
+

∑
i
=
1
n


D
i
t

log
a
m
+

∑
i
=
1
n


C
i
t

,
wherein a and m are constants, a>0 and a≠1, m≥1, |Σi=1n Dit| represents the second sum, and |Σi=1n Cit| represents the first sum.

### Claim 8 (depends on 7)

The method of claim 7, wherein a minimum value μ(t) and a maximum value λ(t) of the specified range are both linear decreasing functions that vary with a time t, and μ(t)<λ(t).

### Claim 9 (depends on 6)

The method of claim 6, wherein the exchanging the graph node and the first quantized value with the another computing node comprises:
exchanging the first quantized value for a graph node of the another computing node in response to the contrast value being less than a minimum value of the specified range, the contrast value after the exchange falling within the specified range; and
exchanging the graph node for a first quantized value of the another computing node in response to the contrast value being greater than a maximum value of the specified range, the contrast value after the exchange falling within the specified range.

### Claim 10 (depends on 1)

The method of claim 1, wherein the exchanging the graph node and the first quantized value with the another computing node comprises:
selecting a first computing node providing a to-be-exchanged graph node and a second computing node exchanging for the to-be-exchanged graph node from the computing node and the another computing node;
determining a first estimated quantized value of the to-be-exchanged graph node estimated by the first computing node;
determining a second estimated quantized value of the to-be-exchanged graph node estimated by the second computing node;
determining, according to the first estimated quantized value and the second estimated quantized value, a determined first quantized value for exchanging for the to-be-exchanged graph node; and
exchanging the to-be-exchanged graph node and the determined first quantized value between the computing node and the another computing node.

### Claim 11 (depends on 10)

The method of claim 10, wherein the determining the first estimated quantized value of the to-be-exchanged graph node estimated by the first computing node comprises:
calculating the first estimated quantized value using a formula:
y
1

(
v
i
,
k
)
=
α


e
-
β

D
i
-
D
k
_
C
i
-
C
k
_
,
Wherein vi represents the to-be-exchanged graph node, k represents the first computing node, y1(vi,k) represents the first estimated quantized value, Di represents a third quantized value of the to-be-exchanged graph node, Ci represents a second quantized value of the to-be-exchanged graph node, Dk represents an average third quantized value of graph nodes in the first computing node k, Ck represents an average second quantized value of the graph nodes in the first computing node k, α and β are system parameters, and e is a natural constant.

### Claim 12 (depends on 10)

The method of claim 10, wherein the determining the second estimated quantized value of the to-be-exchanged graph node estimated by the second computing node comprises:
calculating the second estimated quantized value using a formula:
y
2

(
v
i
,
1
)
=
α


e
-
γ


D
i
+
Σ
j
∈
1

dist

(
i
,
j
)
,
wherein vi represents the to-be-exchanged graph node, l represents the second computing node, y2(vi,l) represents the second estimated quantized value, Di represents a third quantized value of the to-be-exchanged graph node, and Σj∈ldist(i,j) represents a sum of a communication distance between a graph node j in the second computing node l and the to-be-exchanged graph node i.

### Claim 13 (depends on 12)

The method of claim 12, further comprising:
calculating the communication distance using a formula:
dist


(
i
,
j
)

=
def

{
1
,
e
i
,
j
∈
E
0
,
e
i
,
j
∉
E
,
wherein dist(i,j) represents the communication distance between the graph node j and the to-be-exchanged graph node i, ei,j∈E represents that the graph node j is connected to the graph node i through an edge, and ei,j∉E represents that there is no edge between the graph node j and the graph node i.

### Claim 14

A graph-data-based task scheduling apparatus, comprising:
a memory operable to store program code; and
a processor operable to read the program code and configured to:
obtain subgraph data divided from graph data to be processed by a computing node;
perform a unit computing task for a graph node in the subgraph data;
obtain a first quantized value, the first quantized value being a quantized value corresponding to a completed unit computing task in response to data corresponding to the completed unit computing task being formed into blockchain data;
obtain a second quantized value, the second quantized value being a quantized value corresponding to the completed unit computing task in response to the data corresponding to the completed unit computing task being not formed into blockchain data;
determine a third quantized value corresponding to an uncompleted unit computing task in the subgraph data; and
exchange the graph node and the first quantized value with another computing node in response to the second quantized value and the third quantized value failing to meet an equilibrium condition.

### Claim 15 (depends on 14)

The apparatus of claim 14, wherein the processor is configured to:
obtain task information corresponding to the graph data and broadcast in a blockchain network;
read, according to the task information, a task-executable file and the subgraph data divided from the graph data; and
perform the task-executable file according to the subgraph data, the task-executable file indicating the unit computing task for the graph node in the subgraph data.

### Claim 16 (depends on 14)

The apparatus of claim 14, wherein the processor is configured to:
write global computing data corresponding to the completed unit computing task into a new block; and
after the new block being verified by a blockchain network,
add the new block into the blockchain network to form blockchain data, and
generate the first quantized value corresponding to the completed unit computing task.

### Claim 17 (depends on 16)

The apparatus of claim 16, wherein the processor is configured to:
obtain a historical second quantized value before the global computing data being written into the new block, the historical second quantized value corresponding to a completed unit computing task that does not form blockchain data; and
subtract the first quantized value from the historical second quantized value, to obtain the second quantized value.

### Claim 18 (depends on 14)

The apparatus of claim 14, wherein the processor is configured to:
obtain latest global computing data from a blockchain network;
obtain local computing data corresponding to the completed unit computing task; and
determine the third quantized value according to the subgraph data, a quantity of completed unit computing tasks, the latest global computing data, and the local computing data.

### Claim 19 (depends on 14)

The apparatus of claim 14, wherein the processor is configured to:
obtain a first sum of current second quantized values of the subgraph data;
obtain a second sum of current third quantized values of the subgraph data;
determine a contrast value of the second sum relative to the first sum; and
determine that the second quantized value and the third quantized value fail to meet the equilibrium condition in response to the contrast value being outside a specified range.

### Claim 20

A non-transitory machine-readable media, having processor executable instructions stored thereon for causing a processor to:
obtain subgraph data divided from graph data to be processed by a computing node;
perform a unit computing task for a graph node in the subgraph data;
obtain a first quantized value, the first quantized value being a quantized value corresponding to a completed unit computing task in response to data corresponding to the completed unit computing task being formed into blockchain data;
obtain a second quantized value, the second quantized value being a quantized value corresponding to the completed unit computing task in response to the data corresponding to the completed unit computing task being not formed into blockchain data;
determine a third quantized value corresponding to an uncompleted unit computing task in the subgraph data; and
exchange the graph node and the first quantized value with another computing node in response to the second quantized value and the third quantized value failing to meet an equilibrium condition.