Byzantine Geoconsensus
Byzantine Geoconsensus
复制标题
拜占庭地理共识
DOI：
10.1007/978-3-030-91014-3_2
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Nesterenko, Mikhail
中科院分区：
文献类型：
--
作者：
Oglio, Joseph;Hood, Kendric;Sharma, Gokarna;Nesterenko, Mikhail
我们定义并研究了嵌入在三维平面中的N个过程的一致性，我们称之为地一致性问题。这些进程具有独特的坐标，可以通过口头消息相互交流。故障过程被有限大小的凸断层区F所覆盖。正确的进程知道故障区域的大小，但不知道它的位置。在构造性方面，对于直径为D的任意形状的断裂区，我们给出了一个可以容忍拜占庭过程的一致算法BASIC，只要它们之间存在两两距离较大的过程。我们提出了另一种共识算法GENERIC，它提高了这一距离要求。对于带边的正方形，GENERIC容忍拜占庭过程，因为所有过程都被至少22个相同大小的最大对齐的正方形所覆盖。对于直径为F的圆，如果所有过程都被至少85M个圆覆盖，则GENERIC容忍拜占庭过程。然后，我们估计了对于不同大小的断层和非断层区域的组合以及ASD维过程嵌入的GENERIC容差，其中。
We define and investigate consensus for a set ofNprocesses embedded in thed-dimensional plane,, which we call theGeoconsensus Problem. The processes have unique coordinates and can communicate with each other through oral messages. Faulty processes are covered by a finite-size convex fault areaF. The correct processes know the fault area size but not its location. We prove that the geoconsensus is impossible if all processes may be covered by at most three areas the size of the fault area.On the constructive side, forfault areasFof arbitrary shape with diameterD, we present a consensus algorithmBASICthat toleratesByzantine processes provided that there areprocesses with pairwise distance between them greater thanD. We present another consensus algorithmGENERICthat lifts this distance requirement. For squareFwith side,GENERICtoleratesByzantine processes given that all processes are covered by at least 22Maxis aligned squares of the same size asF. For a circularFof diameter,GENERICtoleratesByzantine processes if all processes are covered by at least 85Mcircles. We then estimate the tolerance ofGENERICfor various size combinations of fault and non-fault areas as well asd-dimensional process embeddings, where.