ADRC - 08 - Leader Election

In termine di message complexity, anche se tendenzialmente questo protocollo utilizza meno messaggi di quello precedente, nel caso peggiore i due protocolli sono asintoticamente equivalenti. Consideriamo infatti la seguente istanza

Notiamo che a seconda del verso seguito dai messaggi, possiamo avere o il caso peggiore o il caso migliore. In particolare,

• Se i messaggi seguono un verso antiorario, allora troviamo il caso peggiore, in quanto tutti i messaggi inviati possono essere scartati solo dal nodo con l'etichetta più piccola.

  

  In questo caso abbiamo una message complexity di

  \[n + (n-1) + \ldots + 2 + 1 = \frac{n(n+1)}{2}\]

  ---

• Se i messaggi invece seguono un verso orario, allora troviamo il caso migliore, in quanto tutte le etichette tranne quella minima vengono bloccate subito.

  

  In questo caso abbiamo una message complexity di

  \[n + (n-1) = 2n - 1\]

  ---

Possiamo quindi vedere come il protocollo appena descritto non è tanto migliore di quello precedente.

Notiamo che dopo un tempo finito il nodo con l'etichetta minima si deve necessariamente svegliare in un tempo finito. Una volta svegliato tale nodo, avendo l'etichetta minima, rispetterà la condizione descritta prima, ovvero ad un certo punto arriverà ad uno stage \(i^*\) in cui riceverà da una porta il messaggio che ha inviato dalla porta opposta. Tale stage \(i^*\) può essere calcolato. Infatti si ha che

\[i^* = \min_{i} \{\,\,2^{i-1} \leq n \,\,\} \iff i^* = \theta(\log_2{n})\]

Dunque il numero di stages necessari e sufficienti per far terminare il protocollo è \(\theta(\log_2{n})\). Dato che ogni stage dura un tempo finito, ne segue che il protocollo termina correttamente in un tempo finito.

---

Per quanto riguarda la message complexity, l'idea è quella di contare quanti messaggi vengono inviati in ogni fase del protocollo. A tale fine definiamo la seguente quantità

\[n_i := \text{numero di nodi che hanno superato la fase } i - 1\]

Osserviamo poi che per poter superare la fase \(i-1\) un nodo deve necessariamente "ammazzare" i nodi che si trovano ad una distanza massima di \(2^{i-2}\) da lui, considerando entrambi i lati. Da questo segue che in ogni gruppo di \(2^{i-2} + 1\) nodi, al massimo uno di questi ha una possibilità di sopravvivere lo stage \(i-1\).

Troviamo quindi il seguente upper bound

\[n_i \leq \frac{n}{2^{i-2} + 1}\]

Da questo segue che i nodi attivi hanno una decrescita esponenziale.

---

Sia quindi \(i > 1\), e consideriamo i vari messaggi inviati nello stage \(i\). Nel caso peggiore troviamo la seguente situazione:

• Forth messages: I messaggi di tipo "forth" inviati nello stage \(i\) percorrono una distanza di \(2^{i-1}\) passi in entrambe le direzioni. Dato che abbiamo \(n_i\) nodi inizialmente attivi, troviamo al più \(n_i \cdot 2 \cdot 2^{i-1}\) messaggi di tipo "forth".

• Feedback messages: Per ogni nodo che sopravvive lo stage abbiamo \(2 \cdot 2^{i-1}\) messaggi di tipo "feedback". Ogni nodo che non sopravvive lo stage \(i\) invece ne potrà ricevere al massimo \(1\) messaggio di feedback. In totale quindi troviamo al massimo

  \[n_{i+1} \cdot 2 \cdot 2^{i-1} + \underbrace{(n_i - n_{i+1})}_{\text{nodi uccisi nello stage } i} \cdot 2^{i-1}\]

  messaggi di tipo "feedback".

Dunque, per ogni stage \(i > 1\), abbiamo che il totale dei messaggi inviati può essere maggiorato da

\[\begin{split} n_i \cdot 2 \cdot 2^{i-1} + n_{i+1} \cdot 2 \cdot 2^{i-1} + (n_i - n_{i+1}) \cdot 2^{i-1} &= 2^{i-1} \cdot (3 \cdot n_i + n_{i+1}) \\ &\leq 2^{i-1} \cdot \Big( 3 \cdot \left\lfloor \frac{n}{2^{i-2} + 1}\right\rfloor + \left\lfloor \frac{n}{2^{i-1} + 1}\right\rfloor \Big) \\ &< \frac{3n \cdot 2^{i-1}}{2^{i-2} + 1} + \frac{n \cdot 2^{i-1}}{2^{i-1} + 1} \\ &< \frac{3n \cdot 2^{i-1}}{2^{i-2} + 1} + \frac{n \cdot \cancel{2^{i-1}}}{\cancel{2^{i-1}}} \\ &= 6n + n \\ &= 7n \end{split}\]

---

Per quanto riguarda il primo stage invece \((i = 1)\), il caso peggiore è quando tutti sono initiators. In questo caso si ha che

\[ n_2 \leq \frac{n}{2^0 + 1} = \frac{n}{2}\]

I nodi che sopravvivono hanno un costo individuale di

\[\begin{cases} 2 \text{ per msg "forth"} \\ 2 \text{ per msg "feedback"} \end{cases} \implies 4 \cdot n_2 \text{ messaggi totali}\]

Gli altri invece, quelli che non sopravvivono, hanno un costo individuale di

\[\begin{cases} 2 \text{ per msg "forth"} \\ 1 \text{ per msg "feedback"} \end{cases} \implies 3 \cdot (n - n_2) \text{ messaggi totali}\]

In totale quindi troviamo

\[4n_2 + 3n - 3n_2 = n_2 + 3n < 4n\]

mettendo tutto assieme il totale dei messaggi inviati è

\[\begin{split} M(\text{STAGE TECHNIQUE}) &\leq \sum_{i = 1}^{\log n} 7n + \theta(n) \\ &= 7n \cdot \log{n} + \theta(n) \\ &= \theta(n \cdot \log{n}) \end{split}\]

Dunque,

\[M(\text{STAGE TECHNIQUE}) = O(n \cdot \log{n})\]