ADRC - 06 - Depth First Traversal

Notiamo che nel protocollo appena descritto abbiamo tre tipologie di messaggi, che sono:

• Token messages: Utilizzati per scambiare il token.

• Back-edge messages: Utilizzati per indicare che un nodo ha già ricevuto il token, e che quindi non ne ha bisogno.

• Return messages: Utilizzati per ritornare il token dopo averlo ricevuto per la prima volta.

Notiamo che su un dato arco \((x, y) \in E\) possiamo avere una tra le due seguenti possibilità

ma allora in ogni arco passano esattamente due messaggi. Troviamo quindi la seguente message complexity

\[M(\text{BACK}) = 2 \cdot m = O(m)\]

Osservazione: Notiamo che \(\Omega(m)\) è un lower bound anche per il problema della DFT. Infatti, risolvendo la DFT stiamo anche risolvendo il Broadcast, e quindi il lower bound del Broadcast si riflette anche nel lower bound del DFT. Questo significa che in termini di message complexity il protocollo \(\text{BACK}\) risulta essere asintoticamente ottimo.

Notiamo che nel protocolo \(\text{BACK}\) ogni nodo esplora in modo sequenziale tutti i suoi vicini. Questo significa che otteniamo la seguente ideal time complexity

\[T(\text{BACK}) = \theta(m)\]

Notiamo però che in termini di ideal time complexity il problema \(DFT\) ha un lower bound di \(\Omega(n)\). Abbiamo quindi un gap abbastanza significativo tra il lower bound e la ideal time complexity del protocollo discusso. L'esplorazione di questo gap ci porta alla definizione di un nuovo protocollo.

Questa volta abbiamo quattro tipi di messaggi, che sono: \(\text{TOKEN}, \text{RETURN}, \text{VISITED}, \text{ACK}\).

Iniziamo la nostra analisi notando che tutti i nodi tranne l'initiator ricevono un solo messaggio \(\text{TOKEN}\) e inviano un solo messaggio \(\text{RETURN}\). L'initiator poi non riceve nessun messaggio \(\text{TOKEN}\), e non invia nessun messaggio \(\text{RETURN}\). Questo ci permette di dire che abbiamo esattamente \(2 \cdot (n-1)\) messaggi che sono di tipo \(\text{RETURN}\) o \(\text{TOKEN}\).

Continuando, ogni nodo invia un messaggio \(\text{VISITED}\) a tutti i nodi a lui adiacenti, tranne il nodo da cui ha ricevuto il messaggio. Il totale dei messaggi di tipo \(\text{VISITED}\) è quindi dato da

\[|N(s)| + \sum\limits_{x \neq s} |N(x)| - 1 = 2m - (n-1)\]

Infine, notando che ad ogni messaggio \(\text{VISITED}\) corrisponde un messaggio \(\text{ACK}\), abbiamo che il numero totale di messaggi è dato da

\[M(\text{BACK+}) = \,\,\underbrace{2 \cdot \big[ 2m - (n-1) \big]}_{\text{messaggi di tipo} \\ \text{VISITED e ACK}} \,\,\, + \,\,\, \underbrace{2(n-1)}_{\text{messaggi di tipo} \\ \text{TOKEN e RETURN}} = \,\,\,\, 4m\]

Per quanto riguarda la ideal time complexity, lavorando in un sistema sincrono con un delay di \(\Delta=1\) abbiamo che:

• I messaggi \(\text{TOKEN}\) e \(\text{RETURN}\) sono inviati in modo sequenziale, pagando un tempo di \(2(n-1)\).

• I messaggi \(\text{VISITED}\) e \(\text{ACK}\) sono inviati in modo parallelo. In particolare ogni nodo spende \(2\) unità di tempo per queste operazioni. Il tempo totale speso tra l'invio e la ricezione di questi messaggi è quindi dato da \(2n\).

In totale troviamo

\[T(\text{BACK+}) = 2 \cdot (n-1) + 2n = 4n - 2\]

il che risulta essere asintoticamente ottimale.

L'idea è quella di eliminare i messaggi \(\text{ACK}\) per diminuire la message complexity.

Notiamo che facendo questa scelta quando un nodo \(x\) invia il messaggio \(\text{VISITED}\) ai suoi vicini non aspetta più la ricezione dei messaggi \(\text{ACK}\) e invia subito il token ad un suo vicino. Questo fatto rende possibile il seguente scenario: consideriamo due nodi \(y\) e \(z\) adiacenti a \(x\). Può succedere che passando da \(y\) il nodo \(z\) riceve il token prima di essere avvisato del fatto che \(x\) ha già avuto il token. In questo caso quindi il nodo \(z\) invierà il token a \(x\), anche se \(x\) lo ha già ricevuto. Graficamente la situazione è descritta come segue,

L'idea quindi è che eliminando i messaggi \(\text{ACKs}\) può succedere di inviare più messaggi \(\text{TOKEN}\) di quelli strettamente necessari. Notiamo che al massimo possiamo avere due "errori" per ogni back-edge. In totale quindi possiamo avere al più \(2(m-n+1)\) errori, il che ci fa ottenere una message complexity limitata da

\[\begin{split} M(\text{BACK++}) &\leq M(\text{BACK+}) -\big(2m - (n-1)\big) + 2(m-n+1) \\ &= 4m -\big(2m - (n-1)\big) + 2(m-n+1) \\ &= 4m -n +1 \end{split}\]

Per quanto riguarda l'ideal time complexity, abbiamo che ogni nodo non deve più aspettare due unità di tempo, ma solo una unità di tempo per inviare il messaggio \(\text{VISITED}\). Questo significa anche che può inviare il token (o il messaggio \(\text{RETURN}\) se non ha vicini da visitare) in modo sincrono all'inivio del messaggio \(\text{VISITED}\).

Infine, considerando il fatto che per definizione in un sistema asincrono non ci possono essere ritardi, non ci possono neppure essere errori. Troviamo dunque il seguente risultato

\[T(\text{BACK++}) = 2\cdot(n-1) = 2n - 2\]

Come ultima modifica che possiamo fare al protocollo per diminuire ulteriormente la message complexity l'idea è quella di eliminare i messaggi \(\text{VISITED}\), e utilizzare i messaggi \(\text{TOKEN}\) per dire in modo implicito che il nodo è stato già visitato.

Notiamo che questo salvataggio di messaggi avviene solamente per i nodi che, quando ricevono il token, hanno dei vicini che devono essere ancora visitati. Indichiamo con \(f_{*}\) il numero di questi nodi. Segue che il numero di messaggi che salviamo è dato da \(n - f_{*}\).

In totale quindi, con questa ulteriore modifica, riusciamo ad avere una message complexity di

\[M(\text{Back}_*) = 4m -n + 1 - (n - f_*) = 4m -2n + f_* + 1\]

Osservazione: Notiamo che il valore di \(f_*\), a differenza dei valori di \(m\) ed \(n\), non è un parametro del sistema, ma dipende dalla particolare esecuzione che si sta analizzando. In generale quando abbiamo a che fare con valori che cambiano a seconda della particolare esecuzione, indicheremo tali valori con il subscript \(*\).