ADRC - Lesson 05

In questa sezione verrà studiato il problema del broadcasting su ipercubi e verrà mostrato come l'aggiunta della conoscenza della rete da parte dei nodi, combintata alla simmetria della rete stessa, può portare alla creazione protocolli asintoticamente migliori del Flooding.

Generalmente in un contesto reale si vuole costruire reti che abbiano le seguenti proprietà:

1. un diametro piccolo (\(O(1)\) o \(\texttt{poly-log}\)), in modo tale da ridurre i tempi di comunicazione tra i nodi.
2. il grafo deve essere sparso, risparmiando in termini di risorse per la creazione di link.

Si osservi che riducendo il grado massimo di un grafo, come conseguenza si otterrà la sua sparsificazione⁴. Un'altro vantaggio di un grafo sparso è la sua scalabilità, ovvero la capacità di non comportare eccessivi costi nel caso di aggiunta di nuovo nodo. Per esempio, una clique non è molto scalabile, in quanto ogni volta che viene aggiunto un nuovo nodo bisogna creare \(n - 1\) nuovi links. Invece l'aggiunta di un nodo su un grafo a forma di lista comporta l'aggiunta di un solo arco.

Non è tutto oro ciò che luccica: anche se un grafo a lista è estremamente scalabile e sparso, esso comporta alcuni cruciali svantaggi. Il primo è che ha come diametro il valore massimo che si può presentare (\(n - 1\)). Il secondo è la sua poca resistenza, infatti se si rompe anche solo un link il grafo si disconnette. Contrariamente, una clique ha diametro minimo (ovvero 1) risultando in tempi di comunicazione ottimali. In oltre prima di "rompersi" bisgona rimuovere almeno \(n - 1\) archi.

Una struttura più equilibrata rispetto alle precedenti è la struttura a griglia bidimensionale. In griglia di \(n\) nodi composta da \(\sqrt{n}\) righe e colonne, il grado massimo è 4, mentre il diametro è \(2 \sqrt{n}\). Inoltre è abbastanza scalabile, infatti si possono collegare tra di loro più griglie semplicemento affiancandole e aggiungendo \(\sqrt{n}\) archi. Anche se \(O(\sqrt{n})\) è un buon miglioramento rispetto a \(n\), si può ottenere di meglio.

La struttura che offre un buon compromesso in termini di grado massimo, densità, resistenza, diamtero e scalabilità è l'ipercubo. È già noto che in un ipercubo \(d\)-dimensionale il numero di nodi è esattamente \(n = 2^d\), e di conseguenza \(d = \log_2{n}\). Inoltre ogni nodo ha grado esattamente \(d\), quindi il numero complessivo di archi è \(m = \frac{nd}{2} = \frac{n\log_2{n}}{2}\).

Consideriamo il problema del broadcasting su un ipercubo: oltre alle solite restrizioni già viste (unique initiator, total reliability, bidirectional links e connectivity), in questa variante si assume che ogni nodo sa di essere in un labeled hypercube \(d\)-dimensionale.

In questa particlare rete i link e i nodi sono etichettati come segue:

1. ogni nodo è univocamente eithcettato con una stringa in \(\lbrace 0, 1 \rbrace^d\). Inoltre ogni nodo ha come vicino i nodi le quali etichette differiscono di un solo bit.
2. Ogni arco è etichettato con un numero nell'intervallo \(\left[ d \right]\), in modo che tale etichetta rappresenta l'indice del bit per il quale i due nodi estremi differiscono (partendo a contare per esempio dal bit meno significativo).

Si osservi che applicando semplicemente il protocollo Flood su questa rete la message complexity sarà \(O(n\log{n})\).

Di seguito alcune definizioni utili

DEF: (distanza di Hamming) date due stringhe \(\overline{x},\overline{y} \in \lbrace 0,1 \rbrace^d\), esse si dicono a distanza di Hamming \(d_{Ham}(\overline{x},\overline{y}) = k\) se le due stringhe differiscono esattamente di \(k\) simboli.

DEF: (Labeled Hypercube) un ipercubo etichettato \(d\)-dimensionale \(H_d = (V, E)\) è un grafo il cui insieme dei nodi è l'insieme \(V \equiv \lbrace \overline{x} \mid \overline{x} \in \lbrace 0,1 \rbrace^d \rbrace\), mentre l'insieme degli archi è \(E \equiv \lbrace (\overline{x},\overline{y}) \in V^2 \mid d_{Ham}(\overline{x},\overline{y}) = 1 \rbrace\).

Fact 1: un ipercubo etichettato \(d\)-dimensionale \(H_d\) ha diametro esattamente \(d = \log_2{n}\).
Proof: per dimostrare il fatto 1 è necessario dimostrare che per ogni coppia di nodi \(\overline{x},\overline{y} \in V\) esiste un percorso \(P = \overline{x} \rightsquigarrow \overline{y}\) tale che la sua lunghezza \(|P|\) è minore uguale di \(d\).

Consideriamo quindi due differenti nodi \(\overline{x} = \langle x_1, x_2, ..., x_j, ..., x_d \rangle\) e \(\overline{y} = \langle y_1, y_2, ..., y_j, ..., y_d \rangle\).

Scorrendo in parallelo i caratteri delle due stringhe, prima o poi si arriverà a un indice \(j_1\) tale che \(x_{j_1} \neq y_{j_1}\) (perchè abbiamo assunto che \(\overline{x}\) e \(\overline{y}\) sono differenti).

A questo punto, per costruzione dell'ipercubo etichettato, esisterà un suo vicino \(\overline{x}'\) tale che \(x'_{j_1} = y_{j_1}\). Tale vicino sicurmanete esiste, dato che \(\overline{x}\) e \(\overline{x}'\) sono a distanza di Hamming 1. Consideriamo quindi l'arco \((\overline{x}, \overline{x}')\) come primo arco del cammino \(P\).

A questo punto, \(\forall i \leq j_1\) avremo che \(x'_i = y_i\), quindi partendo dall'indice \(j_1 + 1\) continuiamo a scorrere in parallelo le due stringhe \(\overline{x}'\) e \(\overline{y}\). Se arrivati all'indice \(d\) non si sono incontrati caratteri differenti, allora \(\overline{x}' = \overline{y}\), e quindi il cammino è concluso. Se invece \(\overline{x}' \neq \overline{y}\) certamente esisterà un indice \(j_1 < j_2 \leq d\) tale che \(x'_{j_2} \neq y_{j_2}\).

Come prima, esisterà per forza un nodo \(\overline{x}''\) vicino di \(\overline{x}'\) tale che \(x''_{j_2} = y_{j_2}\). Appendiamo quindi l'arco \((\overline{x}', \overline{x}'')\) al cammino.

Proseguendo in questa maniera, prima o poi si arriverà ad un nodo \(\overline{x}^{\star} = \overline{y}\). Nel cammino vengono considerati nodi a distanza di Hamming 1 l'uno dall'altro, e ad ogni arco preso ci si "avvicina" di 1 alla destinazione. Dato che al più \(\overline{x}\) è distnte \(d\) da \(\overline{y}\), allora il cammino costruito con il precedente metodo può essere lungo al più \(d\) \(\square\).

Un'altra caratteristica importante dell'ipercubo è la sua scalabilità. Infatti si può estendere un ipercubo di dimensione \(d\) con un altro ipercubo di dimensione \(d\), semplicemente aggiungendo un arco tra i nodi analoghi dei due ipercubi.

Inoltre l'ipercubo è una struttura abbastanza stabile, in quanto per essere disconnessa è necessario rimuovere almeno \(d\) archi.

Di seguito un confornto tra le figure precedentemente descritte.

Grafo	Diametro	Grado
Clique	\(\Theta(1)\)	\(\Theta(n)\)
Lista	\(\Theta(n)\)	\(\Theta(1)\)
Griglia	\(\Theta(\sqrt{n})\)	\(\Theta(1)\)
Ipercubo	\(\Theta(\log{n})\)	\(\Theta(\log{n})\)

if self.status == "INITIATOR":
    spontaneously:
	send(self.message) to self.neighbors

else:
    recieving(message):
	 l = message.fromEdge
	 for i in range(1,l):
	     send(message) to self.neighbors[i]