NEO SPCC researcher Alexey Vanin has published an article discussing task distribution across nodes in BFT systems. The article discusses how tasks are divided up between nodes using NEO’s dBFT consensus mechanism, and proposes how the task pool size for each node could be reduced without compromising the executions of tasks.

BFT Task Distribution

In decentralized systems, nodes may split tasks (referring to various types of operation) by either randomly selecting a task for themselves, or by distributing them according to a consensus mechanism. In dBFT, consensus can be reached as long as less than ⅓ of the total consensus nodes are Byzantine (meaning compromised in some way).

To demonstrate, picture a system with three nodes (n) and three tasks (v) to be completed. If each node takes one task, you would need all three nodes behaving properly to have all tasks executed successfully. If one node was compromised, the task allocated to that node would not be completed.

To resolve this, a redundant approach is used, where v is executed by n/3 + 1 nodes. This gives each node a pool size with the number of tasks it would need to complete, in order to ensure all tasks in the system are executed properly.

In the same system, with three tasks and three nodes, each node completes two tasks instead of one. In this scenario, any one of the three nodes can be compromised without preventing any of the tasks from being completed.

With this approach, no matter how many tasks need to be processed, the pool size for each node tends towards the value of v/3, or one-third of all tasks. This indicates that the system will not scale properly as the load increases.

Minimizing the task pool

To increase scalability, the task pool for each node needs to be reduced, but this needs to be done without the risk of tasks not being executed. NEO SPCC built a simulation model with 1000 tasks, which attempts to find a task pool size where the probability of non-executed tasks is less than 0.00001 across different numbers of nodes.

The results of the simulation show that this probability falls between the minimum and maximum task pool sizes, and the required task pool size decreases as more nodes are added. The research could pave the way for improved scalability of NEO’s consensus nodes and NEO SPCC’s distributed file storage system.

It should be noted that this research did not include investigations into the probability of network nodes failing; it is assumed that the maximum number of nodes are compromised. For example, a network of three nodes is more likely to have one node fail than a network of 100 nodes having 33 nodes fail.

NEO SPCC has suggested that it may be possible to determine a ‘compromise probability’ which could allow further studies into potential efficiency improvements for consensus nodes.

Tags: