ADRC - 13 - Gossip Protocols

Consideriamo un grafo \(G = (V, E)\) e una sorgente \(s \in V\).

Al tempo \(t = 0\) la sorgente è l'unico nodo nello stato \(\text{INFORMED}\), mentre tutti gli altri nodi \(v \in V \setminus \{s\}\) si trovano nello stato \(\text{UNKNOWN}\).

Quando il protocollo parte \(\forall t \geq 1\), ogni nodo \(v \in V\) che non è ancora stato informato, e quindi che si trova nello stato \(\text{UNKNOWN}\) effettua la seguente operazione, chiamata operazione di pull:

\(v\) sceglie un suo vicino \(w\) in modo uniforme. Se \(w\) è informato, \(v\) riceve da \(w\) l'informazione e diventa informato a sua volta.

Il protocollo PUSH è analogo a quello PULL per quanto riguarda l'input e lo stato del sistema al tempo \(t = 0\). Quello che cambia è la dinamica del protocollo.

In particolare, per ogni round \(t \geq 1\), questa volta sono i nodi \(v \in V\) che sono già informati ad effettuare la seguente operazione, detta operazione di push.

\(v\) sceglie un suo vicino \(w\) in modo uniforme. Se \(w\) non è ancora stato informato, allora \(v\) invia a \(w\) il messaggio e \(w\) diventa informato.

Utilizzando il protocollo PULL nel grafo completo abbiamo che in media ad ogni passo il numero di nodi informati aumenta almeno di \(1\). Infatti,

\[Pr[ \text{al tempo sds } t = 1 \text{ almeno un nodo sceglie } s] = \frac{n-1}{n} \approx 1\]

Detto questo, non è possibile ottenere dei risultati di concentrazione quando la media dei nodi informati è molto piccola rispetto a \(\log n\). In altre paprole, c'è una probabilità costante che in un turno non abbiamo nessun nuovo nodo informato.

---

La più grande differenza tra i due protocolli appena visti è che in generale il protocollo PULL è mlto più "selvaggio" del protocollo PUSH. Infatti utilizzando la dinamica PULL in alcuni round il numero di nodi informati potrebbe aumentare di molto. Con il protocollo PUSH invece anche nella migliore delle ipotesi il numero di nodi informati può solamente raddoppiare da un turno al successivo, il che ci permette di avere un bound deterministico di \(2^t\) al numero di nodi informati al tempo \(t\).

Supponiamo di essere in grado di dare un bound alla time complexity del protocollo \(\text{PULL}\).

\[\text{Time}(\text{PULL}(G = (V, E), s)) = T\]

Dato che il numero di messaggi inviati ad ogni round è al massimo \(2n\): \(n\) per le pull requests effettuati da ogni nodo e altri \(n\) contenenti l'informazione da condividere, abbiamo in totale una message complexity di

\[\text{Msg}(\text{PULL}(G, s)) = 2n \cdot T\]

Troviamo quindi un work per node di \(\theta(T)\), che è molto diverso dal work per node del protocollo flooding, che è di \(\theta(\Delta)\), e dunque che dipende dal grado dei nodi del grafo.

La restante parte dell'analisi consisterà nella dimostrazione del seguente risultato

Teorema: Se \(G(V,E)\) è un grafo \(\Delta\) regolare e \(\alpha \Delta\) expander, allora con alta probabilità vale che

\[\text{Time}(\text{PULL}(G = (V, E), s)) = O(\log n)\]

Dimostrazione: Iniziamo definendo i seguenti insiemi

\[\forall t \geq 0: \,\,\, I_t := \{v \in V: v \text{ è informato al round } t\}\]

Notiamo che

• \(I_0 = \{s\}\)

• \(I_t \subseteq I_{t+1}, \,\, \forall t \geq 0\)

Sia quindi \(m_t := |I_t|\), ovvero \(m_t\) è il numero di nodi informati al tempo \(t\). Fissiamo il valore di \(m_t\) e andiamo a calcolare il numero medio di nodi informati al tempo \(t+1\). A tale fine notiamo che

\[m_{t+1} = m_t + \gamma^{(t+1)}\]

dove \(\gamma^{(t+1)}\) è la variabile aleatoria che conta il numero di nodi che vengono informati nel round \(t+1\). Per trattare \(\gamma^{(t+1)}\) definiamo le seguenti v.a.

\[\forall v \in V \setminus I_t: \,\, Y_v^{(t+1)} := \begin{cases} 1 \,\,&,\,\, v \text{ viene informato al passo } t + 1 \\ 0 \,\,&,\,\, \text{ altrimenti } \end{cases}\]

Consideriamo ora \(v \in V \setminus I_t\). Notiamo che se \(v \not \in N(I_t)\), allora sicuramente \(v\) non potrà essere informato al passo \(t+1\). Troviamo quindi che \(\forall v \in V \setminus I_t\)

\[\begin{align} v \in N(I_t) &\implies Pr[Y_v^{(t)} = 1] \geq 0 \\ v \not \in N(I_t) &\implies Pr[Y_v^{(t)} = 1] = 0 \\ \end{align}\]

Dal fatto che \(G\) è \(\Delta\) regolare poi segue che

\[\forall v \in N(I_t): \,\, Pr[Y_v^{(t+1)} = 1] \geq \frac{1}{\Delta}\]

Siamo quindi in grado di calcolare la media di \(\gamma^{(t+1)}\) come segue

\[\begin{split} \mathbb{E}[\gamma^{(t+1)}] = \mathbb{E}[\sum\limits_{v \in N(I_t)} Y_v^{(t+1)} &= \sum\limits_{v \in N(I_t)} \mathbb{E}[Y_v^{(t+1)}] \\ &= \sum\limits_{v \in N(I_t)} Pr[Y_v^{(t+1)} = 1] \\ &\geq |N(I_t)| \cdot \frac{1}{\Delta} \\ \end{split}\]

Rispetto a \(m_{t+1}\) troviamo quindi

\[\mathbb{E}[m_{t+1}] = m_t + \mathbb{E}[\gamma^{(t+1)}] \geq m_t + \frac{|N(I_t)|}{\Delta}\]

Infine, utilizzando il fatto che il grafo \(G\) è un \(\alpha \Delta\) expander otteniamo

\[\begin{split} \mathbb{E}[m_{t+1}] &\geq m_T + \frac{|N(I_t)|}{\Delta} \\ &\geq m_t + \frac{\alpha \Delta |I_t|}{\Delta} \\ &\geq (1 + \alpha) m_t \\ \end{split}\]

Quanto appena dimostrato vale solamente in media quando \(|I_t| \leq n/2\). Quando \(|I_t| > n/2\) l'idea è quella di concentrarci sull'insieme dei nodi non informati. È infatti possibile dimostrare che se \(|I_t| > n/2\) il numero medio di nodi non informati decresce in modo esponenziale.

Infine, è possibile dimostrare utilizzando i chernoff bounds che il comportamento in media vale anche con alta probabilità per vari valori di \(m_t\).