Se calcolo tutto con i costi uguale 1 praticamente trovo un albero dei cammini minimi che è anche una BFS. Se voglio posso anche usare Dijkstra appena visto e funziona anche con costi tutti 1. Se voglio posso anche andare ad aggiungere un po’ di parallelismo.
Se sono in un BFS posso prendere in considerazione tutti i vicini. Posso pensare di lavorare per iterazioni successiva, ma cerco di vedere quelli che stanno a distanza +1 ogni volta.
Se io sono un nodo sorgente a che distanza possono stare i miei vicini? distanza i, i-1, i+1, ma non a livello 1 come o livelli diversi da quelli appena detti. se un nodo dista i dalla sorgente e non altri cammini allora i suoi vicini possono stare o a distanza i, o a i-1 o i+1, ma non in altre posizioni.
Quindi tutto questo per dire: se ad un certo momento voglio andare a scoprire che nodi sono a i+1 dalla sorgente, chi devo considerare quelli che prima sono a distanza i. Posso pensare di fare delle iterazioni, anche queste sequenziali in cui ciascuna scopre un nuovo livello dell’albero della bfs e questi nodi li vanno a cercare i nodi che sono i più lontani dalla radice in questo momento. Anche l’albero della BFS posso calcolare in distribuito con una serie di iterazioni successive. Che cosa faccio alla generica iterazione i, che sono quella in cui voglio andare a trovare i nodi a distanza i dalla sorgente.
All’inizio dell’iterazione costruisco fin alla distanza i-1 e alla fine sono arrivato alla distanza i. Quello che devono sapere i nodi e qual è la distanza rispetto alla radice, perché devono sapere quando devono lavorare oppure no. La distanza dalla radice dipende dal numero dell’iterazione in cui sono stati coinvolti.
Come segnalo l’inizio di una nuova iterazione? Ci sarà la sorgente che lo notifica mandando un messaggio a tutti i nodi e quelli a i-1 passano il messaggio, mentre quelli ad i svegliano i vicini a i+1.
A chi può arrivare questo messaggio? i, i-1 o i+1. Questi vicini ricevono questo messaggio di esplorazione e rispondono in maniera coerente con quello fatto fino ad ora. Il vicino a distanza i-1 risponde che è già nell’albero. Quelli a distanza i+1 invece mandano un ack. Se però ricevo una roba del tipo: sto esplorando i miei vicini da un mio vicino, vuol dire che è al mio stesso livello!
Se mi arriva roba diversa da ack dai miei vicini vuol dire che sto parlando con qualcuno che non è a i+1, ma allo stesso livello.
Cosa succede se gli arrivano più messaggi di explore più vicini prima di noi? Ad uno dice si e ad altri dice no, perché può avere un solo padre (rivedere questa frase, magari vedere anche le slides).
Ripensamento sul fatto che possa andare a scoprire un nodo che è già ad altezza i, perché magari ha risposto tardi per farsi aggiungere e lo scopro perché magari mi dice che anche lui mi risponde qualcosa di strano anche quando non dovrebbe.
O so che conto sempre n-1 (caso peggiore della catena) o ogni volta dico quanti nodi aggiungo per iterazione e quando ne aggiungo zero finisce tutto. per la terminazione dipende dalle informazioni che ho e dipende dalle end iteration.
2/11/2023
Broadcast: Quanto ci costa all’iterazione i fare broadcast. Parte il messaggio della radice e arriva a tutti i nodi, quanti messaggi in totale possiamo dire con esattezza: 1 per ogni ling fino a i-1. In generale non lo so alla iterazione in i-esima quanti nodi sono presenti. Posso dire che n_i = # nodi dell’albero parziale che ci sono all’inizio dell’iterazione. In questo modo lo so dire quanti messaggi viaggino per il broadcast? n_i -1 (tolgo come sempre la radice).
Converge cast: parto dagli stessi nodi che avevo raggiunto al broadcast e quando finiscono explore e ricevono l’ack mandano il messaggio di “END” verso l’alto, verso la radice. Quindi spendo sempre n_i - 1.