ADRC - Lesson 07

Il protocollo Shout è molto simile al protocollo Flood, con l'aggiunta di messaggi di feedback YES/NO. Dato che siamo sotto l'assunzione che \(G\) è connesso, allora certamente ogni nodo \(x\) (eccetto la sorgente) riceverà almeno una richiesta Q di diventare figlio. Perciò ogni nodo nello stato IDLE passerà allo stato ACTIVE, con il proprio contatore pari a 1. Per ogni richiesta ricevuta tutti i nodi risponderanno YES o NO. Dato che prima di entrare nello stato DONE un nodo deve ricevere una risposta da tutti i vicini, e dato che per costruizione tutti rispondono alle richieste allora prima o poi tutti i nodi passerranno dallo stato ACTIVE allo stato DONE, terminando localmente il proprio task.

Si vuole dimostrare che l'unione di tutti i \(\texttt{tree-neig}(x)\) è uno spanning tree per la rete \(G\).

Per prima cosa bisogna dimostrare le coerenza degli insiemi \(\texttt{tree-neig}(x)\), ovvero che \(x\) ha come vicino \(y\) nello spanning tree (\(y \in \texttt{tree-neig}(x)\)) allora anche \(x\) deve risultare essere vicino di \(y\) (\(x \in \texttt{tree-neig}(y)\)). Questo è facilmente verificabile: certamente uno tra \(x\) e \(y\) deve necessariamente essere il nodo padre, supponiamo \(x\) senza perdita di generalità. Dato che \(y \in \texttt{tree-neig}(x)\), e dato che stiamo assumendo che \(y\) è figlio di \(x\), allora vuol dire che \(y\) avrà risposto YES alla proposta di \(x\), e per costruzione del protocollo \(x\) che è nello stato ACTIVE aggiungerà \(y\) nel suo vicinato. Contrariamente se \(y\) ha risposto YES vuol dire che era nello stato IDLE, e che la prima richiesta ricevuta è stata quella di \(x\). Per costruzione del protocollo, \(y\) contra \(x\) come nodo padre, e lo aggiungerà nel suo vicinato.

A questo punto è necessario dimostrare che l'unione di tutti i \(\texttt{tree-neig}(x)\) è connesso. Anche questo è banalmente verificabile dal fatto che ogni nodo \(x\) (eccetto la sorgente) è collegato al proprio genitore tramite una sequenza di YES-links che risale fino alla sorgente. Perciò data una qualsiasi coppia di nodi \(x,y\), essi saranno connessi dal cammino \(x \leadsto s \leadsto y\), dove \(s\) è il nodo sorgente.

Infine non resta che dimostrare che il grafo risultante dal protocollo è aciclico. Questo si può inferire dal fatto che ogni nodo (eccetto la sorgente) invia una sola risposta YES, la quale permetterà al nodo di "appendersi" all'albero. Supponiamo quindi per assurdo che da nodo \(x\) esistano due cammini semplici distinti fino alla sorgente \(s\) che formano un ciclo. Anche se i dui cammini possono iniziare "scendendo" di livello, dato che entrambi i cammini risalgono alla sorgente allora certamente da un certo punto in poi passeranno per un arco che parte da un nodo figlio verso un nodo padre salendo di livello. Consideriamo solo uno dei due lati del ciclo (tanto il ragionamento è simmetrico). Supponiamo che il primo arco del cammino che risale di livello è un certo \((a,b)\), dove \(b\) è genitore di \(a\). Dato \((a,b)\) è il primo arco risalente, vuol dire che prima di prendere \((a,b)\) si è scesi di livello con tutti archi del tipo PADRE->FIGLIO. Però sappiamo che ogni nodo ha un singolo nodo padre, perciò per arrivare ad \(a\) certamente si sarà preso l'arco \((b,a)\). Questo però non può accadere in quanto nei cammini semplici non si può ripercorrere due volte uno stesso arco, perciò entrambi i lati dell'ipotetico ciclo devono necessariamente partire \(x\) a risalire. Ma dato che x ha un solo padre allora esiste un solo cammino (risalente) da \(x\) alla sorgente \(s\).

Come accennato in precedenza il protocollo Shout è una sorta di protocollo Flood con l'aggiunta di messaggi di feedback. Perciò si può intuire che la message complexity del protocollo Shout è due volte quella del protocollo Flood. \[ MSG(\texttt{SHOUT}) = 2 \cdot MSG(\texttt{FLOOD}) \] Andiamo però a fare un'analisi più dettagliata per verificare l'intuizione.

Consideriamo che i messaggi che passano sugli archi sono del tipo Q, di richiesta di diventare figlio, e di tipo R, di risposta, il quale a sua volta può essere di tipo YES o NO. Si vuole quindi contare per ogni tipologia di messaggi Q, YES, NO quanti ne vengono trasmessi per ogni arco.

Iniziamo però considerando quali situazioni è possibbile che accadano e quali no:

È possibile abbattere il fattore \(4\) dalla complessità del protocollo Shout semplicemente facendo la seguente osservazione: lo scambio di messaggi di tipo NO sono in realtà superflui, se un nodo \(x\) riceve una proposta Q da un nodo \(y\) allora certamente \(y\) è nello stato ACTIVE, e quindi avrà già un nodo padre, perciò è inutile che \(x\) mandi una proposta ad \(y\). Perciò ricevere un messaggio Q può essere interpretato come la ricezione di un messaggio NO dalla stessa porta.

if self.state == "INIT":
    spontaneusly:
	self.root = True
	self.tree_neig = {}
	send(Q) to self.neighbors
	self.counter = 0
	self.state = "ACTIVE"

if self.state == "IDLE":
    receiving(Q):
	self.root = False
	self.parent = Q.sender
	self.tree_neig = {Q.sender}
	send("YES") to Q.sender
	self.counter = 1

	if self.counter == len(self.neighbors):
	    self.state = "DONE"
	else:
	    send(Q) to self.neighbors - {Q.sender}
	    self.state = "ACTIVE"

if self.state == "ACTIVE":
    receiving(Q):
	self.counter += 1
	if self.counter == len(self.neighbors):
		self.state == "DONE"

    receiving("YES"):
	self.tree_neig = self.tree_neig + {R.sender}
	self.counter += 1  
	if self.counter == len(self.neighbors):
		self.state == "DONE"

if self.stat == "DONE":
    None

Code 2: Pseudocodice python-like del protocollo Shout+

Per quanto riguarda la message complexity del nuovo protocollo ottimizzato basta osservare che non può mai accadere la situazione NO-NO, ovvero quando su un arco verrà trasmesso due volte il messaggio NO. Perciò la message complexity del protocollo Shout+ sarà \[ MSG(\texttt{SHOUT+}) = MSG(\texttt{SHOUT}) - 2(m - (n - 1)) = 2m \]

Riguardo invece la terminazione locale del protocollo, ogni nodo sa che il suo compito è terminato nel momento in cui passa allo stato DONE. Sarebbe interessante sapere se un nodo è in grado di capire quando il processo termina globalmente. Certamente se la sorgente \(s\) è in grado di sapere quando lo spanning tree è completato, allora potrebbe mandare una notifica in broadcast per avvertire tutti gli altri. Il problema è che non ogni nodo ha solamente una visione locale della rete in cui si trova, perciò a meno che non ci sia un nodo che riesca ad osservare lo stato della rete dall'alto non è possibile sapere solo col protocollo Shout se il processo di costruzione dello spanning tree è terminato.

OSS.1 si può ottimizzare ulteriormente il protocollo in modo da abbattere il fattore \(\Omega(m)\)? La risposta è no. Semplicemente perché per costruire uno spanning tree bisogna informare in broadcast tutti i nodi della rete quantomeno che il protocollo è iniziato. Se fosse possibile farlo, allora avremmo trovato anche un protocollo di broadcast che esegue il suo task in tempo \(< m\), e sappiamo che non è possibile sotto tali assunzioni (BL, UI, C, TR).

THM l'esecuzione del protocollo di broadcast genera uno spanning tree entrante¹ della rete.
Proof: basta semplicemente che ogni nodo \(x\) conservi come variabile \(father(x)\) il nodo dal quale per primo ha ricevuto l'informazione.

OSS.2 Si può osservare che lo spanning tree costruito con il protocollo Shout (o con la sua versione ottimizzata) dipende fortemente dalla singola esecuzione e non dal protocollo, in quanto i ritardi di trasmissione variano ogni volta. Ciò implica che maneggiando adeguatamente i ritardi di trasmissione potrebbe accadere che \(diam(\texttt{SPT}) >> diam(G)\).

In base a quest'ultima osservazione si potrebbe voler cercare di costruire uno spanning tree con diametro non troppo maggiore del diametro dell'intera rete.

Osservare che esistono tre tipologie di messaggi:

1. token quando un nodo inoltre il token per procedere con la visita.
2. back quando un nodo già visitato restituisce il token al mittente.
3. return quando un nodo termina la propria visita è restituisce indietro il token al padre.

inoltre su ogni arco può passare solamente uno tra i messaggi back e return, mentre il messaggio di tipo token passa esattamente una volta su tutti gli archi. Perciò la message complexity è esattamente \(2m \in \Theta(m)\). Ricordiamo sempre che esiste un teorema che dimostra che, sotto le assunzioni in questione, non è possibile eseguire il broadcasting di una informazione in meno di \(m\) messaggi, e dato che in questo caso sostanzialmente si sta facendo il broadcast del token, un lowerbound alla message complexity rimane \(\Omega(m)\).

Anche se il protocollo è asincrono ha senso parlare di time complexity, in quanto lo scambio di messaggi avviene in maniera totalmente sequenziale². Perciò la time complexity è proporzionale alla message complexity.

Osserviamo che in grafi molto densi una larga quantità di messaggi risolverà in messaggi di tipo back. Perciò sarebbe ideale cercare di evitare che questo accada.

Un'idea è quella di far inviare una notifica a tutto il vicinato di \(x\) qual'ora \(x\) riceva il token per la prima volta (eccetto che al nodo padre, ovviamente). Così facendo, tutti i vicini sapranno che \(x\) è già stato informato e non ci sarà più bisogno in futuro di ritrasmettergli il token, evitando così i messaggi di tipo back.

Il grosso vantaggio, dal punto di vista temporale, è che \(x\) può mandare la notifica ai suoi vicini in maniera parallela.

Prima di proseguire all'inoltro del token, è necessario però che \(x\) riceva un ACK³ dal suo vicinato, in quanto disponendo in modo adeguato i ritardi di trasmissione, potrebbe capitare che un suo vicino \(y\) riceva il token prima del messaggio di notifica, reinviando così nuovamente il token a \(x\). In tale situazione non avremmo risolto nulla, in quanto \(x\) dovrebbe rispedire il token ad \(y\) con un messaggio di back.