Problema del broadcast e introduzione all'hypercube

INIT FINAL

seguenti restrizioni:

Unico iniziato

- G è connesso

- Non ci sono fallimenti

- Link bidirezionali

-

allora quello che possiamo dire è che non esiste nessun protocollo che possa usare l’avversario in

tutti i modi possibili dove l’avversario dice che se un protocollo completa correttamente il broadcast

deve necessariamente scambiare il numero totale di messaggi che sarà almeno m (vuol dire che in

media su ogni arco della rete deve passare almeno un messaggio) ossia se il conteggio del numero

di messaggi scambiati dal protocollo è < m significa che almeno un nodo non è stato informato.

Prima di dimostrare questo lower bound, c’è un lower bound più semplice:

sotto le stesse condizioni per ogni protocollo la mexage complexity di questo protocollo P su un

grafo G = (V,E) di n nodi ed m archi, afferma che (P) >= n-1.

Stando su un grafo connesso di n nodi, supponiamo che n>=2 (perché se n = 1 non si deve

dimostrare nulla perché la mexage complexity è 0). Inoltre si ha |V| = m ed |E| = m.

Dim: per vedere il lower bound si può dimostrare che tutti i nodi del grafo devono ricevere una

copia del messaggio e la situazione iniziale del grafo è che solo il nodo sorgente è informato.

Affinchè si arrivi nello stato finale bisogna arrivare nella situazione in cui tutti i nodi sono

informati; questo significa che gli altri nodi possono essere informati attraverso messaggi. Si può

affermare che ciascun nodo dovrà essere informato da una copia distinta del messaggio.

Per ogni a,b appartenente ad V: a diverso da b

Abbiamo immediatamente che la copia Ia che è responsabile di aver informato il suo nodo a deve

essere necessariamente diversa dalla copia che è responsabile di aver informato il nodo b.

Per ogni a,b appartenente ad v, con a diverso da b si ha che Ia è diverso da Ib.

Dato che ogni nodo deve essere informato allora questo significa che ci deve essere una copia per

ogni nodo e quindi il problema del broadcast non può essere risolto su un grafo connesso con un

numero di nodi >=2 in meno di un numero di messaggi n-1. Questo loweb bound dice che un

protocollo ci mette almeno un numero di messaggi n-1 ossia ordine di n. In questo caso si perde la

ridondanza.

Se invece si vuole ottenere un risultato che è in funzione di m, non si può più contare raggruppando

i messaggi rispetto ai nodi, ma raggruppandoli rispetto agli archi ragionando per assurdo ossia se

per assurdo su un arco non passa una copia del messaggio bisogna dimostrare che li succede

qualcosa di catastrofico. Si utilizza quindi la tecnica degli ambienti.

Dim: assumiamo che esiste un ipotetico algoritmo A che esegue il broadcast scambiando un numero

di messaggi strettamente inferiore al numero di archi del grafo. Quindi qualunque sia la sequenza

dei ritardi che fa l’avversario, il protocollo ci deve mettere sempre un numero di messaggi < n.

quello che possiamo vedere è che c’è almeno un arco in G su cui non passa nessun messaggio

(questo avviene per un semplice fatto di conteggio, cioè se gli archi sono m e se si invia un numero

<= n-1 allora facendo gli accoppiamenti c’è un arco che rimane da solo).

Se siamo nell’ipotesi assurda, ci deve essere per forza un arco su cui durante tutta l’esecuzione del

protocollo non passerà nessun messaggio. Ora si può prendere questo stesso protocollo, in

particolare osservando la storia di x e y, su due ambienti diversi.

Si prende il grafo originale, si toglie l’arco x-y e ci si sostituisce con altri 2 archi un ulteriore nodo

z. quindi il grafo anziché avere n nodi ne ha n+1. Da un punto di vista di porte logiche non è

cambiato nulla. Adesso si esegue l’algoritmo P sul grafo G’ e per ipotesi assurda su G tutti i nodi

erano informati. Siccome la storia di x ed y nel nuovo contesto non può essere cambiata (perché nel

grafo originale il protocollo non scambiava niente tra x e y), siccome il nodo z non è collegato con

nient’altro, allora quello che x e y vedono in G’ è lo stesso perché tutti gli stimoli che riceveva x

venivano da archi diversi da y. Da questo si può capire che in E2 ci interessa solo quello che fanno

x ed y perché sono gli unici che potrebbero informare z.

Se si dimostra che ne x e ne y instraderanno niente sugli archi che vanno verso z il protocollo

terminerà. Questo perché se per assurdo su G il protocollo termina allora anche su G’ il protocollo

termina e x ed y saranno informati, ma siccome z non riceverà nessun messaggio da x e y allora z

non potrà mai essere informato.

In questa dimostrazione si è sfruttato il fatto che la storia di x e a storia di y nell’ambiente G sotto

gli stessi stimoli che il protocollo e l’avversario generavano ha permesso di costruire un altro grafo

G’ con un nodo in più in cui x ed y hanno la stessa storia, gli stessi stimoli e siccome nell’ambiente

precedente ne x e ne y spediscono un messaggio sull’arco x-y allora neanche in questo nuovo

ambiente ripetendo la stessa storia nessuno dei due invierà un messaggio sugli archi x-z ed y-z ed z

non verrà informato.

Questo dimostra che se stiamo su un grafo generale, i nodi inizialmente non conoscono niente di

questo grafo tranne le condizioni iniziali (unico iniziator, gli altri stanno nello stato DONE, ecc) e

non c’è un protocollo che riesce ad eseguire il task del broadcast con un numero di messaggi

strettamente inferiore ad m. possiamo inoltre notare che il protocollo flooding che aveva una

mexage complexity di 2m-n+1 confrontandolo con la mexage dell’intero problema (broadcast)

possiamo dire che il problema è ottimale.

HYPERCUBE

La message complexity su grafi densi è molto costosa e per risolvere i vari problemi del mondo distribuito si

può costruire una sottorete (spanning tree) cioè un sottografo molto più sparso; si informano tutti i nodi di

questo nuovo sottografo e, una volta costruito lo spanning di ordine n, quando i nodi si sono messi d’accordo

su un unico spanning tree allora se un nodo vuole inviare un messaggio lo invia lungo l’albero di spanning

2

tree ed ogni operazione costa n e non n .

L’idea quindi è quella di costruire uno spanning tree ed eseguire il flooding nello spanning tree ossia vedere

se sotto certe condizioni si possono fare dei protocolli più “furbi”.

Agli inizi degli anni 80 nacque il calcolo parallelo dove si poteva mettere in uno spazio limitato molti

processori e organizzarli in una struttura topologica. Dati dei nodi, ci sono degli archi su cui vengono

scambiati dei dati e lo scopo è usare questi nodi per svolgere un certo task (es: fare la moltiplicazione tra

matrici). Qui il sistema è sincrono ossia c’è un clock e i processori sono sincronizzati. La matrice viene

selezionata in blocchi, dove ogni processore è responsabile di un blocco, risolve il sottoproblema all’interno

del blocco e poi si trasmettono questi dati agli altri processori in modo tale che tutti i processori convergano

alla stessa soluzione.

Quindi ci piacerebbe che questi processori comunicassero nel modo più efficiente e veloce possibile (si è

tentati a costruire strutture con un diametro molto piccolo e con grado elevato, ossia ad inserire molti archi).

Possiamo rappresentare l’architettura parallela come una griglia (MESH) dove su ogni spigolo c’è un

processore e sono tutti processori identici.

Questo significa che la topologia è a griglia e che il nodo quando ha un dato da comunicare lo può

spedire facendo un cammino di routing per trasmetterlo al nodo destinatario; il nodo può

comunicare al passo successivo solamente sugli altri 4 vicini (nord, sud, ovest, est). Lo scopo è

sempre quello di parallelizzare la computazione.

Più il diametro dell’architettura è lungo e più il numero di hop che un messaggio deve fare per

andare da un posto all’altro diventa elevato; quindi al crescere di n si vorrebbe che il tempo di

trasmissione di un messaggio da un nodo all’altro sia piccolo. L’idea sarebbe di far crescere il grafo

con diametro costante.

Data la topologia Tn ci piacerebbe che il diametro al crescere di n fosse θ, ossia:

(Tn) = θ(1)

Questo non è possibile perché l’unico modo al crescere di n per mantenere questa cosa costante è prendere

grafi densi.

Un risultato in combinatorica dei grafi dice che se si vuole mantenere il diametro costante con una famiglia

2

infinita di grafi allora implica che il numero di archi deve essere per forza n = Ω(n ) e che il grado minimo di

ogni nodo è d(w) = Ω (n) (ossia non si possono scegliere 4 vicini perché se l’architettura raddoppia il

numero di nodi il grado raddoppia).

Quindi si deve prendere una struttura completamente diversa da questa dove per ogni nodo il grado è ordine

di n. Nelle tecnologie Mesh si deve essere in grado di farli incontrare tra di loro. In questa struttura al

crescere delle dimensioni dell’architettura parallela (al crescere di n) il grado di ogni nodo è costante.

Possiamo dire quindi che le architetture parallele hanno come scopo quello di avere il grado piccolo e

diametro piccolo. Il tempo di completamento dell’operazione globale è proporzionale al diametro.

Esiste una famiglia di grafi infiniti simmetrica e connessa che ha le seguenti proprietà, dato Gn:

- Il grado massimo costante al crescere di n è {Gn, con n>=0} con G(n) = O(1)<cost

- Con diametro di G(n) = Θ(logn)  il diametro che quando raddoppia, ossia passa da n a 2n, cresce di

1, quindi la crescita deve essere al più logaritmica.

Adesso prendere una distribuzione uniforme (scegliere un grafo random) e una volta creata la distribuzione

prendere un grafo a caso, allora si può dimostrare con alta probabilità che il grafo random G è un

EXPANDER.

L’expander è un grafo connesso che ha un grado piccolo (coatante) e diametro logaritmico. Gli expander

sono fault tollerant.

Dopo qualche anno si è riusciti a de-randomizzare questa costruzione e a costruire algoritmi efficienti che in

tempo polinomiale in m costruiscono, fissato n, grafi expander con grado costante. L’Hypercube non ha

grado costante come gli expander ma ha:

- Grado d(Gn) = log n

2

- Diametro (Gn) = log n

2

Ossia rispetto agli expander ha un diametro uguale però ha un grado che cresce rispetto ad n con una

funzione piccola; in particolare quando si raddoppia il numero di nodi il grado aumenta solo di una unità.

La struttura è: c’è un Hypercube di dimensione 1, di dimesione 2, ecc … quindi al crescere della dimesione i

nodi raddoppiano.

L&rs