Mettiamo dei clock per cui abbiamo una sincronia tra tutti quanti gli agenti del mio sistema. Non solo stiamo dicendo che questi oggetti lavorano alla nostra velocità, ma stiamo dicendo che battano tutti quanti in contemporanea.

Questa assunzione è abbastanza forte e ci mettiamo a lavorare in questo contesto. Siamo portati a fare anche altre assunzioni e conclusione riguardo i tempi di comunicazione del sistema. Assumiamo come convenzione che gli orologi battano tutti quanti insieme e che i messaggi partano nel momento in cui parte il clock.

Le entità mandano un messaggio ai vicini solamente a clock tick; si manda solamente un messaggio. Quello che si aggiunge come restrizione è che non solo la comunicazione arriva dall’altra parte in tempo finito, abbiamo però un upper bound sul tempo di arrivo del messaggio. Abbiamo un Delta entro il quale i messaggi spediti arrivano a destinazione.

Possiamo già dire che possiamo sapere dopo quanti tick del clock sicuramente sarà arrivato. Basta dividere il tempo massimo, tra il tempo che intercorre tra un clock e l’altro e sappiamo in quanti tick il messaggio arriva a destinazione.

Questo mi permette di lavorare con unità di tempo unitarie per far sì che il messaggio arrivi a destinazione. La conseguenza di queste assunzioni è che però dobbiamo andare a metter un bound sulla dimensione del messaggio.

Devo mandare una limitazione superiore al numero massimo di bits da mandare ad ogni messaggio. Se devo mandare più bit li devo andare a dividere in più messaggi. Non dipende dall’input del nostro problema, ma dalla rete. Sarà da considerare a questo punto anche quanto sarà grande il messaggio in bit.

Si introduce così il concetto di tempo condiviso. Quindi possiamo provare a pensare di riprendere un protocollo che avevamo visto in precedenza e vedere se riusciamo a ri-adattarlo a questa nuova situazione. In questo contesto riusciamo a dire invece se riesco a fare andare dei messaggi più veloci degli altri? Così il messaggio del minimo va più veloci di tutti e riusciamo a stoppare tutti quanti. Se riesco a fare andare più veloce quello dell’identificativo più piccolo potrei salvarmi. Come posso andare a fare andare più piano alcuni messaggi e più veloci altri?

Posso introdurre dei ritardi nei nodi, considerando che tutti contino il tempo allo stesso modo. Che cosa succede? Non possiamo andare a cambiare la velocità sui link ma possiamo introdurre dei ritardi nel modo in cui viaggiano questi messaggi. Se chiaramente l’id che mi arriva è più piccolo di quello che arriva in un determinato momento, lo posso fare aspettare per una certa qtà di tempo.

Quando finisce questo protocollo?? Quando mi ritorna lo stesso identificativo finisce e devo andare a notificare gli altri (questo è il leader). Qual è una misura di attesa che funziona? 2^i, per un determinato valore i che viene ricevuto.

Quanto tempo possiamo misuriamo? Possiamo contare le unità di tempo normali. Quante unità di tempo ci mette l’id più piccolo a fare tutto il giro del ring? Considerando 2^i come funzione: n * 2^i = tempo di attesa dei nodi, ma devo considerare il tempo per passare dei link. Quindi è n*2^(min) + n, quindi è attesa + passaggio sui link.

Prendiamo il secondo più piccolo, quale potrebbe avere come valore? min+1, è quasi il più veloce.

diviNel tempo che il più piccolo ha fatto tutto quanto il giro, il più piccolo al massimo quanti link avrà percorso? Sicuramente avrà fatto meno del minimo. Prendo il tempo che ci mette l’altro a fare tutto il giro e divido per il tempo di attesa: (2^min * n) + n/ 2^(min+1) ≤ n/2 + n/4 ≤ n links

Posso andare a fare lo stesso discorso per tutti quanti gli altri identificativi. Facendo lo stesso conto che ci mette quello del minimo.

Questo ci permette di ragionare su quanti messaggi girano su questo sistema, per cui effettivamente il minimo gira su n, il secondo al massimo su n-1, il terz’ultimo su n/2 etc. … potrebbero essere anche di meno con id non consecutivi al più piccolo.

Quando andiamo a contare il numero di messaggi possiamo dire in generale: n

$$ n + n \sum_{i=0}^{n-2} \frac{1}{2^{i}} \in O(n) $$

rispetto ai protocolli che abbiamo visto fino ad ora è meglio decisamente! Ha senso quindi usarlo? Certamente! Perché stiamo lavorando con ipotesi molto più forti e riusciamo a fare cose migliori sicuramente.

Qual è il rovescio della medaglia? Quanto tempo ci mettiamo a fare questo protocollo?

$$ O(2^{min}n) $$

Devo attendere che venga effettuato tutto quanto il giro del ring + la notifica (consideriamo poi quel +n per la notifica).