任何计算机系统都有监控操作，可能发送心跳信息、校验和查询、哈希请求等。在本文中，这些操作统称为任务。在集中式系统中，通常有一个经过认证的节点或一组节点来完成任务。分散式系统可以将任务分配到各个节点，从而灵活扩展，所以效率明显更高，但这也引出了相应的问题3354:如何在选择的节点之间分配任务。我们可以通过蓑衣网小编2022以下两种方式来解决这个问题：

节点随机选择任务来做

节点使用dBFT等共识算法来分配任务

本文将探讨第二种方法。

拜占庭容错任务分配

假设系统中有V个任务和N个节点可以随时工作。每个任务和节点都有一个唯一的标识符。因此，每个节点可以使用HRW [2]来选择任务，并使用预设的算法来执行任务。事实上，任务分配共识确认了所有任务都在无技术故障的情况下完成。

使用dBFT算法，即使网络中多达1/3的节点[1]做出妥协，也能达成共识。比如一个系统n=v=3:

系统有三个任务，三个节点，其中一个是欺诈性的。

这些任务均匀分布在节点中：如果每个节点承担一个任务，最坏的情况下，可能有一个任务无法执行。所以我们用冗余来保证所有的任务都能执行。v任务必须由n/3 1个节点执行。在这种情况下，节点任务池的大小可以通过以下公式计算。

蓑衣网小编2022

在这种情况下，P(3，3)=2

无论哪个节点做出妥协，所有任务仍然可以正确执行。

图1不同任务数下的最大任务池大小

图1表明该公式的值趋于v/3，这意味着在任何情况下每个节点的任务池中的任务都占所有任务的1/3。当负载增加时，系统可能无法正常扩展。

减小任务池大小

如果系统中n=3 v=4，则任务池大小为P(3，4)=2.3 3。每个节点的任务池的大小可以减少到2:

。因此，每个任务被执行的概率达到66%。因此，只要保证一定的精度，任务池的规模是可以缩小的。

为了研究的目的，我们建立了一个仿真模型进行实验，参数为v=1000。我们试图找到在不同的N个条件下，任务不能被执行的概率小于0.00001的任务池的大小。该模型已经在github中开源[3]。结果如图2所示：

图2V=1000

时的任务池容量实验上图表明，该模型的实验数据实际上是在最大和最小任务池容量的范围内。因此，当n增加时，任务池的所需容量将减少。利用公式R(x)(位于y1轴上，取0到1之间的任意值)可以得到任务池的最大容量与实蓑衣网小编2022验值之差作为近似值。那么任务池容量可以通过下面的公式得到。

深入研究

本文不考虑网络节点失效的可能性，所有实验都是在最坏的假设下进行的，妥协节点的数量也达到最大。很明显，100个节点中33个被攻破节点的比例小于3个节点中1个被攻破节点的概率。所以“妥协概率”的等式可以定义为Q(x)，那么任务池的大小就可以计算为P(n，v)？R(n)？问(名词).然而，当妥协节点数小于n/3时，R(x)的行为需要进一步研究。

参考文献

docs.neo.org/en-us/basic的拜占庭容错算法区块链张正文…

一致哈希(最高随机权重):en.wikipedia.org/wiki/Rendez…

仿真模型库：github.com/AlexVanin/b…

原文翻译自：medium.com/@neospcc/ta…

作者：阿列克谢瓦宁