Problema del broadcast e introduzione all'hypercube

Broadcast in sistemi distribuiti

Consideriamo un sistema distribuito dove una sola entità x conosce alcune informazioni e vorrebbe condividerle con tutte le altre entità della rete; questo problema è chiamato broadcasting. Risolvere questo problema significa disegnare un insieme di regole che, quando eseguite dalle entità, guideranno per una configurazione dove tutte le entità conoscono l'informazione.

Protocollo Flooding e complessità del broadcast

Come abbiamo visto, il protocollo flooding usa O(m) messaggi e ci si chiede se è possibile usare diversi approcci per ridurre il costo. Questa domanda è equivalente a chiedere cos'è la complessità del problema del broadcast. Per rispondere abbiamo bisogno di stabilire un lower bound: per cercare un bound f e per dimostrare che il costo di ogni soluzione è al massimo f. Un lower bound è indipendente dal protocollo, e dipende solamente dal problema.

Teorema e condizioni del problema

Teorema: prendere il problema del broadcast che è dato dalla tripla <INIT, FINAL, R> , metterci le 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.

Lower bound e complessità messaggi

Prima di dimostrare questo lower bound, c’è un lower bound più semplice: sotto le stesse condizioni per ogni protocollo la message 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 message complexity è 0). Inoltre si ha |V| = m ed |E| = m.

Dimostrazione del lower bound

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 I_a 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 I_a è diverso da I_b. Dato che ogni nodo deve essere informato, 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 lower 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.

Risultato in funzione di m

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 lì succede qualcosa di catastrofico. Si utilizza quindi la tecnica degli ambienti.

Assunzione di un algoritmo ipotetico

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).

Conclusione della dimostrazione

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 né x né 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.