Distributed Algorithms di Nancy Linch → vallo a cercare in bsi magari, potrebbe essere interessante
Funziona sotto quale ipotesi: grafo connesso, archi bidirezionali, canali fifo, no failure, id distinti e le entità o sanno il diametro del grafo o un suo upper bound.
Come possiamo fare per andare a lavorare sul grafo: mando tutto a tutti cercando di andare a capire quale che sia il massimo. Siamo su un grafo quindi le cose si complicano un pochettino rispetto a quando siamo sul link di un anello.
Che cosa succede in ogni rounds. Ognuno manda il massimo che ha visto fino ad ora a tutti quanti i vicini e aspetta le risposte dai vicini e poi calcola il massimo. In quanti round convergo? Almeno il diametro del grafo. Ovviamente convergo molto in fretta più archi ho. Il caso peggiore è quando il massimo è lontano, magari non è centrale nel grafo, un po’ come se fosse una catena. Caso migliore un grafo completamente connesso perché in due round vinco.
Ogni round porta con se il massimo dei vicini, solo che praticamente ad ogni round questa distanza è crescente. Andando per round ci stiamo sincronizzando ed il tempo che ci metto è imprevedibile, però tutti quanti devono finire il round 1 prima di andare al round successivo e sto forzando con i round la sincronicità. Perché round 1 tutti parlano con i vicini. Il round 2 finisce solo quando ho saputo tutto quanto dai vicini, … in pratica quello che vedo io è sempre un porzione incrementale del grafo, aggiungendo un arco in più sempre ad ogni round.
numero vicini * numero round * 2 → 2m * d
La catena massima di messaggi di fila è d che è il diametro perché oltre quello non andiamo.