ADRC - 10 - Majority Consensus I
1 Lecture Info
Data:
Il problema di trovare un agreement tra i nodi di una rete distribuita è uno dei problemi più importanti nei sistemi distribuiti moderni. In questa lezione abbiamo iniziato la trattazione di questo problema, noto come majority consensus problem, analizzando il protocollo h-majority dynamics nei casi \(h=1, 2\).
2 Majority Consensus Problem
Consideriamo un grafo completo di \(n\) nodi in cui ogni nodo si può trovare in due stati \(0\) o \(1\). Informalmente il problema del majority consensus ci richiede di partire da una configurazione "sbilanciata" della rete rispetto alla distribuzione degli stati nei vari nodi, e trovare un protocollo per convergere in un tempo finito ad una configurazione in cui tutti i nodi hanno lo stesso stato.
Formalizzando, il problema viene affrontato in un sistema sincrono a tempo discreto. La configurazione del sistema è quindi descritta da un vettore di elementi
\[\overline{X}_t \in \{0, 1\}^n = (0, 1, 0, 1, 1, \ldots, 0, 1)\]
A partire dalla configurazione \(\overline{X}_t\) si definiscono poi le seguenti quantità di interesse:
\(b(\overline{X}_t) := \text{ numero di nodi nella configurazione } \overline{X}_t \text{ nello stato } 1\)
\(a(\overline{X}_t) := \text{ numero di nodi nella configurazione } \overline{X}_t \text{ nello stato } 0\)
Per formalizzare il concetto di "sbilanciamento" invece si utilizza la seguente quantità
\[Bias(\overline{X}_t) = S(\overline{X}) := \displaystyle{\frac{|b(\overline{X}) - a(\overline{X}) | }{2}}\]
Il problema del majority consesus consiste quindi nel passare da uno stato iniziale in cui lo sbilanciamento è almeno \(S(\overline{X}) \geq c \cdot \sqrt{n \cdot \log{n}}\), con \(b(\overline{X}) > a(\overline{X})\), per arrivare al tempo \(T \in \mathbb{N}\) in uno stato finale tale che \(\overline{X}_T = (1, 1, 1, \ldots, 1) = \overline{1}\).
Osservazione: Lo sbilanciamento \(S(\overline{X})\) assume valori tra \(0\) e \(n/2\). Se \(S(\overline{X}) = 0\) tutti i nodi hanno lo stesso stato, mentre se \(S(\overline{X}) = n/2\) la metà dei nodi si trova in uno stato e la metà nell'altro stato.
2.1 Cosa Vogliamo?
Osserviamo che se un nodo riuscisse a contattare tutti i nodi nello stesso istante, allora lui e tutti gli altri nodi sfruttando la maggioranza già presente potrebbero calcolare un agreement in un singolo round. Questa soluzione però ha i seguenti costi:
Una Message complexity di \(O(n^2)\).
Una memoria per nodo di \(O(n)\)
L'utilizzo di tutti gli archi della rete.
La terza condizione in particolare può risultare problematica quando abbiamo una rete fisica sparsa che simula, attraverso i cammini, una rete virtuale completa. Un esempio di rete del genere è proprio Internet.
Da un protocollo che risolve il problema del majority consesus quindi vogliamo le seguenti cose:
Lavoro per nodo: \(\theta(\log n)\)
Archi attivi per round: \(\theta(n)\)
Tempo di convergenza: \(\theta(n \cdot \log n)\)
Queste richieste sonoo molto ambiziose. Per dare una idea di questo, basta considerare il fatto che per ottenere un sample significativo in un modello centralizzato in cui abbiamo \(\theta(n/2 + \sqrt{n \cdot \log n})\) in uno stato e il restante nell'altro necessitiamo di \(\Omega(\sqrt{n})\) samples.
Lavorando in modo distribuito invece ci possiamo aspettare un sampling di \(\theta(\log n)\) per nodo dal fatto che lo stato del nodo \(v\) al tempo \(t\) è ottenuto in funzione di tutti i nodi che al tempo \(t\) potenzialmente potrebbero raggiungere \(v\). In questo modo ogni nodo, dopo \(\log n\) passi, ha avuto nella sua storia un sample random lineare in \(n\). Questo è un esempio di self-organized behavior.
3 h-Majority Dynamics
Il protcollo h-majority dynamics è diviso in rounds.
Ad ogni round, ogni nodo sceglie in modo uniforme e indipendente \(h\) nodi a lui adiacenti, e cambia il proprio stato a seconda della maggioranza calcolata tra i nodi scelti. Eventuali ties vengono gestite in modo arbitrario. Quando si effettua la scelta degli \(h\) nodi non c'è estrazione dei nodi, nel senso che se un nodo \(v\) potrebbe sceglie un altro nodo \(w\) più volte.
Andiamo adesso ad analizzare il protocollo in due casi distinti, a seconda del valore di \(h \in \{1, 2\}\). Nella prossima lezione invece andiamo ad analizzare il caso \(h=3\). Prima di iniziare però facciamo alcune considerazioni generali.
3.1 Analisi Dinamica
Il processo considerato è un processo markoviano, intendendo con ciò che la configurazione al tempo \(t\) dipende solamente da quella al tempo \(t-1\). Supponiamo quindi di fissare la configurazione del sistema al tempo \(t-1\). Tale configurazione è rappresentata dalla seguente coppia di valori
\[\overline{X} = \Big(a(\overline{X}), \,\,\,b(\overline{X}) \Big)\]
L'obiettivo delle successive analisi è il calcolo del valore atteso della v.a. \(a' := a(\overline{X}_t)\) che indica il nuovo numero di nodi che si trovano nello stato \(0\).
A tale fine definiamo le seguenti v.a.
\[\forall v \in V: \,\,\,\, Y_t^v := \begin{cases} 1 \,\,\,&,\,\,\, \text{ se } X_t(v) = 0 \\ 0 \,\,\,&,\,\,\, \text{ altrimenti } \end{cases}\]
in questo modo possiamo esprimere \(a'\) come somma di v.a. nel seguente modo
\[a' = a(\overline{X}_t) = \sum\limits_{v \in V} Y_t^v\]
dunque, dalla linearità della media,
\[\mathbb{E}[a'] = \mathbb{E}\Big[\sum\limits_{v \in V} Y_t^v\Big] = \sum_{v \in V} \mathbb{E}\Big[Y_t^v \Big] = \sum_{v \in V} Pr[Y_t^v = 1 \,\,\, | \,\,\, \overline{X}_{t-1} = \overline{X}]\]
L'unica cosa che cambia nei diversi casi analizzati è quindi la probabilità che un particolare nodo passi allo stato \(0\) fissata la configurazione al tempo \(t-1\). Per calcolare tale probabilità però in entrambi i casi dobbiamo ricordare il fatto che stiamo lavorando in un grafo completo, e che le scelte vengono effettuate con probabilità uniforme. Da queste due cose ne segue che non ci interessa quali sono i particolari nodi nello stato \(0\) o nello stato \(1\), ma ci interessano solamente quanti sono, ovvero ci interessano solamente i valori \(a(\overline{X}), b(\overline{X})\).
3.1.1 Caso \(h=1\)
Sia \(v \in V\). Dato che \(h = 1\), il nodo \(v\) ad ogni tempo \(t\) per scegliere il suo nuovo stato si basa solamente su un altro nodo, che pesca in modo uniforme. Troviamo quindi
\[Pr[Y_t^v = 1 \,\,\, | \,\,\, \overline{X}_{t-1} = \overline{X}] = \frac{a(\overline{X})}{n} = \frac{a}{n}\]
Il valore atteso di \(a'\) risulta dunque essere
\[\mathbb{E}[a'] = \sum_{v \in V} Pr[Y_t^v = 1 \,\,\, | \,\,\, \overline{X}_{t-1} = \overline{X}] = \sum_{v \in V} \frac{a}{n} = n \cdot \frac{a}{n} = a\]
Osserviamo a questo punto che anche se lo spazio totale delle possibili configurazioni è formato da \(2^n\) elementi, a noi interessano solamente le macro-configurazioni in cui \(a(\overline{X})\) e \(b(\overline{X})\) differiscono.
Nel caso \(h=1\) quindi il protocollo, in media, non cambia lo sbilanciamento del sistema, anche se può cambiare lo stato locale dei singoli nodi. La dinamica h-majority con \(h=1\) è quindi molto lenta, e sbaglia con una probabilità costante di errore, il che non è ideale.
L'idea è quindi quella di aumentare il valore del parametro \(h\) e vedere cosa cambia.
3.1.2 Caso \(h=2\)
Sia \(v \in V\), e supponiamo che gli eventuali ties vengono gestiti tramite il lancio di una moneta equilibrata.
Dato che \(h=2\), il nodo \(v\) ha due modi diversi per cambiare il proprio stato e assumere lo stato \(0\). Può infatti o pescare in modo uniforme due nodi che si trovavano già nello stato \(0\), oppure può pescare in modo uniforme un nodo nello stato \(1\) e uno nello stato \(0\), e ottenere testa nel lancio della moneta (assumiamo che testa favorisca \(0\) e croce \(1\)). Troviamo quindi
\[Pr[Y_t^v = 1 \,\,\, | \,\,\, \overline{X}_{t-1} = \overline{X}] = \Bigg(\frac{a(\overline{X})}{n}\Bigg)^2 + 2 \cdot \Big[ \frac{a(\overline{X})}{n} \cdot \frac{b(\overline{X})}{n} \cdot \frac12 \Big]\]
per semplificare poi utilizziamo il seguente fatto
\[a(\overline{X}) + b(\overline{X}) = n \iff b(\overline{X}) = n - a(\overline{X})\]
Troviamo quindi
\[\begin{split} Pr[Y_t^v = 1 \,\,\,|\,\,\, \overline{X}_{t-1} = \overline{X}] &= \Bigg(\frac{a(\overline{X})}{n}\Bigg)^2 + 2 \cdot \Big[ \frac{a(\overline{X})}{n} \cdot \frac{(n - a(\overline{X}))}{n} \cdot \frac12 \Big] \\ &= \frac{a(\overline{X})^2}{n^2} + \frac{a(\overline{X})}{n} - \frac{a(\overline{X})^2}{n^2} \\ &= \frac{a(\overline{X})}{n} \\ \end{split}\]
Anche in questo caso troviamo quindi che la dinamica risulta essere troppo lenta. Infatti,
\[\mathbb{E}[a'] = \sum_{v \in V} Pr[Y_t^v = 1 \,\,\, | \,\,\, \overline{X}_{t-1} = \overline{X}] = \sum_{v \in V} \frac{a}{n} = n \cdot \frac{a}{n} = a\]
Nella prossima lezione andremo ad analizzare il caso \(h=3\).