ADRC - Lesson 03

THM se eseguiamo il protocollo trivial-flood sotto le assunzioni 1,2,3,4, esiste un tempo \(t \in \mathbb{R}^+\) tale che ogni nodo di \(G\) ha ricevuto il messaggio \(m\) almeno una volta, ovvero \[ \forall v \in V \;\; state(v) = \texttt{informed} \]

Proof: sia \(L_d\) l'insieme di nodi distanti esattamente \(d\) dalla sorgente \(s\). Si vuole dimostrare per induzione su \(d\) che esiste un tempo \(t_d\) tale che tutti i nodi in \(L_d\) hanno ricevuto almeno una volta il messaggio, ovvero che lo stato dei nodi al tempo \(t_d\) sia \(state_{t_d}(v) = \texttt{informed}\), per ogni \(v \in V\).

Per \(d = 0\) è banale in quanto \(L_0 := \lbrace s \rbrace\). Perciò come base prendiamo \(d = 1\). Per definizione avremo che \(L_1 \equiv N(s)\). Per come è descritto il protocollo, la srogente \(s\) a un certo punto invierà in maniera spontanea il messaggio a tutti in nodi in \(N(s)\), ergo in \(L_1\). Dato che stiamo sotto l'assunzione di total reliability siamo certi che non ci saranno failures durante al trasmissione, quindi per \(d=1\) certamente esisterà un istante \(t_1 \in \mathbb{R}^+\) entro il quale tutti i nodi in \(L_1\) verranno informati.

Supponiamo ora che l'ipotesi sia vera fino a un certo \(d-1\); si vuole dimostrare che sia vera anche per \(d\), ovvero che \[ \forall x \in L_d \implies \exists t_d \in \mathbb{R}^+ : state_{t_d}(x) = \texttt{informed} \] Consideriamo un qualsiasi nodo \(x \in L_d\), allora per definizione esisterà un nodo \(y \in L_{d-1}\) tale che \((y,x) \in E\) (sfruttando anche l'ipotesi di bidirectional links).

Se \(y \equiv s\) allora vuol dire che \(x \in L_1\), riconducendoci quindi al caso base. Se invece \(y \not\equiv s\), allora certamente \(y\) avrà ricevuto il messaggio mentre era nello stato SLEEPING, e per definizione del protocollo \(y\) avrà inviato il messaggio al suo vicinato \(N(y)\), compreso \(x\). Sfruttando ancora l'ipotesi di total reliability sappiamo che il messaggio arriverà in un tempo finito e intatto a \(x\) tramite \(y\).

Infine sfruttando l'ipotesi di connettività di \(G\) sappiamo che \(\forall v \in V \exists k \in \mathbb{N}\) con \(k \leq diam(G)\), tale che \(v \in L_k\) \(\square\).

Per come è stato descritto, il protocollo precedente porta a termine il suo task, però non termina mai. Inoltre, quando un nodo instrada un messaggio ricevuto a tutto il suo vicinato, esso rispedice una copia superflua anche al suo mittente (per via dei bidirectional link). Per ovviare a questo bastano le seguenti modifiche:

1. Se nodo ha ricevuto almeno una volta il messaggio passa in uno stato DONE, nel quale non ci sarà più bisogno che inoltri ulteriori messaggi (perchè è già stato fatto in precedenza)
2. Un nodo che riceve un messaggio non lo inoltra a chi glielo ha inviato. Sappiamo che un nodo può distinguere i nodi agli estremi dei suoi archi incidenti grazie all'assunzione di bidirectional links, ovvero \(\forall x \in V \left[\forall y \in N(x) \;\; \lambda_x(x,y) = \lambda_x(y,x) \right]\)

# protocollo trivial ottimizzato
if self.state == "INITIATOR":
    spontaneously:
	send(self.message) to N(self)
	self.state = "DONE"

elif self.state == "SLEEPING":
    receiving(m):
	send(m) to N(self) - { source }
	self.state = "DONE"

elif self.state == "DONE":
    None

Code 2:Pseudocodice python-like protocollo ottimizzato

Come già accennato in precedenza, non ha senso parlare di time complexity in un sistema che non è sincrono. Perciò analizzeremo la complessità del protocollo in termini di numero di messaggi trasmessi entro il completamento del task.

Verranno proposte due analisi abbastanza semplici sul protocollo ottimizzato², le quali porteranno ad un risultato asintoticamente uguale, ma con un livello di dettaglio differente.