algorithmgraph-theorydistributed-computingtheoryconsensus

How to calculate a minimum exchange time among multiple nodes?


This is about developing a distributed consensus.

Let's assume we have N nodes
( N1, N2, ..., Nn ),
each of the nodes has a different value
( A1, A2, ..., An ).
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 N1 when I communicate with N2 and I find A2 < A1, then I will replace my value with A2

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.


Solution

  • Given the postulated properties, one of which is values An 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