分布式互斥：小圈子形成

Question

我一直在研究基于Quorums概念的分布式互斥算法。

引用： Coterie C 被定义为一组集合，其中每个集合 g ∈ C 称为群体。

以下属性适用于小圈子中的法定人数：

1）交集性质：对于每个群体g，h ∈ C，g ∩ h= ∅。 例如，集合 {1,2,3}、{2,5,7} 和 {5,7,9} 不能是集合中的法定人数 小圈子，因为第一组和第三组没有共同元素。

2) 极小性：在小圈 C 中不应存在法定人数 g、h，例如 即 g s h。例如，集合 {1,2,3} 和 {1,3} 不能是集合中的法定人数 小圈子，因为第一组是第二组的超集。

我想知道，给定分布式系统中的一组节点，这些节点是如何形成这样的小圈子或一组仲裁的？ 有哪些算法或技术可以做到这一点？

更新： 换句话说，问题是—— “给定‘N’个节点，形成‘K’个群体的最佳方式是什么，使得其中任意两个节点有‘J’个公共节点？”

Answer 1

读取或写入的简单算法是，您必须从仲裁中的每个节点读取并向仲裁中的每个节点写入。这样您就可以确保系统中的所有其他方都会阅读最新的书面项目。

由于您的标题是关于互斥的，因此系统中的对等方可以向仲裁中的每个节点请求资源锁定。由于第一条规则，任何其他对等方都无法从整个仲裁中获得锁定。

据我所知，您在实践中接触随机节点并用作法定人数

n/2 + 1

，但正如您所看到的，您还可以定义更复杂的分布，这允许您拥有更小的法定人数，这再次提高了性能。

更新：

具有 9 台服务器的此类仲裁的示例如下：

• 2 个法定人数：服务器 1-5 是一个法定人数，5-9 是另一个法定人数（简单多数）
• 3 个法定人数：服务器 1、2、3、4； 4,5,6,7; 7,8,9,1 可以是 3 个不同的法定人数
• 更多法定人数：服务器 1、2、3； 3,4,5; 5,6,1； 6,7,3; 8,3,1； 9,3,1；可以是 6 个不同的法定人数。然而，在这里您可以看到服务器 1 和 3 分别属于 4 个仲裁，因此需要处理更多流量。
• 您还可以创建像 1,2 这样的法定人数； 1,3; 1,4; 1,5; 1,6; 1,7; 1,8; 1,9;但这与只有服务器 1 是一样的。

Answer 2

以下论文的第 4 节描述了部分枚举（非支配）群的算法：

H。 Garcia-Molina 和 D. Barbara，“如何在分布式系统中分配选票”，J. ACM，卷。 32、没有。 4，第 841–860 页，1985 年 10 月，doi：10.1145/4221.4223。

在结论中，作者指出

对于五个以上的节点，小圈子的数量是巨大的。事实上，光是部分枚举算法生成的圈数就非常大了。因此，我们需要启发式方法来减少选择的数量......