This is about developing a distributed consensus.

Let's assume we have N nodes
( N₁, N₂, ..., N_n ),
each of the nodes has a different value
( A₁, A₂, ..., A_n ).
These nodes can communicate with each other, and replace their value if it's bigger then the other node's value.

For example if I'm N₁ when I communicate with N₂ and I find A₂ < A₁, then I will replace my value with A₂

I need to find the least number of exchanges so that more than half of the nodes ( > n / 2 ) hold the smallest possible value.

An exchange is a single communication between two nodes that results may result in a change in one of the two involved node's value, if and only if the other one has different and smaller value.

CodePudding user response：

Given the postulated properties, one of which is values A_n were postulated to be initially different, the solution is derived from how large the requested strictly dominant majority MAJ actually is, thus setting the minimum (optimistic case supremum) of amount of exchanges .xg!-operations needed, which sets the [TIME]-domain complexity inductively alike this :

 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