如何计算多个节点之间的最小交换时间？

Question

这是关于开发分布式共识。

假设我们有 N 个节点
( N₁, N₂, ..., N_n ),
每个节点都有不同的值
( A₁, A₂, ..., A_n ).
这些节点可以相互通信，如果它的值大于另一个节点的值，则替换它们。

例如，如果我是 N₁，当我与 N₂ 通信时，我发现 A₂ < A₁，那我就把我的值换成A₂

我需要找到最少的交换次数，以便超过一半的节点 ( > n / 2 ) 保持尽可能小的值。

交换是两个节点之间的单一通信，导致可能导致两个相关节点之一的值发生变化，当且仅当另一个具有不同且更小的值。

Answer 1

鉴于假定的属性，其中一个是值 A_n 被假定为最初不同，解决方案是从所要求的严格占主导地位的多数中得出的MAJ 实际上是，因此设置交换量的最小值（最乐观的情况）.xg!-所需的操作，它以归纳方式设置 [TIME]-域复杂度，如下所示：


 n  == 2
 MAJ ~ 2        _(1)_----->----(2).xg! _1_
 xg! = 1                          


                        (3)
                        / \
                       /   \
                      /     \
                     /       \
                    /         \
 n  == 3           /           \
 MAJ ~ 2        _(1)_----->----(2).xg! _1_
 xg! = 1
 
                   
          .xg!_1_(4)-----------(3)
                  |.         .  |
                  |  .     .    |
                  |    . .      |
                  ^    . .      |
                  |  .     .    |
 n  == 4          |.         ,  |
 MAJ ~ 3        _(1)_----->----(2).xg! _1_
 xg! = 2
 
 ________________________________________________________
 n  ==  5 |  6 |  7 |  8 |  9| 10 | 11 | ... |     n
 MAJ ~  3 |  4 |  4 |  5 |  5|  6 |  6 | ... | 1 + n // 2
 xg! =  2 |  3 |  3 |  4 |  4|  5 |  5 | ... |     n // 2

如何计算多个节点之间的最小交换时间？

How to calculate a minimum exchange time among multiple nodes?

algorithm

graph-theory

distributed-computing

theory

consensus