Voglio praticamente avere un agente diverso dagli altri che praticamente funga come leader. All’inizio sono tutti quanti availables, ma alla fine uno solo deve essere leader e tutti quanti follower. Tutti devono avere la coscienza del fatto che sono leader o follower. Non è esplicito che chi è follower sappia chi sia il leader. Noi vedremo casi in cui loro sanno chi è. Non mettiamo vincoli su quanti sono gli iniziatori del protocollo e su chi possa diventare leader. Tutti quanti hanno la stessa possibilità.
Inserisci appunti cartacei del 19 ottobre 2023
20/10/2023
Posso andare a migliorare la message complexity, ma bisogna vedere un pochino che cosa andare a fare. Ci sono degli stage o round per cui abbiamo dei nodi che sono sopravvissuti a quelli precedenti e combattono per arrivare alla fine → questo per andare a decidere e selezionare il leader, dopo che tutti si svegliano e si propongono come candidati fino a che l’ultimo capisce di essere il leader. L’importante è che questo finisca in un numero finito di operazioni.
Come funziona questo protocollo? Che succede ad un generico stage i? Si sfrutta il fatto che sia bidirezionale. Io che sono sopravvissuto e mando i messaggi a dx e sx, così la distanza a cui faccio viaggiare il messaggio dipende dallo stage in cui mi trovo. la distanza a cui mando il messaggio è di=2^i
Se tutti facessero così non succederebbe nulla, dobbiamo trovare quello con ID più piccolo e vanno avanti i messaggi fino a quando un messaggio è il più piccolo visto fino a quel momento. Se vedo passare un id più piccolo di me, capisco di non essere il minimo e decido di smettere di mandare avanti il mio messaggio.
I messaggi vanno avanti e indietro come nello schema: inserire schema
Il candidato leader se si vede tornare indietro la roba passa allo stage successivo, altrimenti se passa troppo tempo o gli arriva un messaggio di qualcun altro diventa DEFEATED e fa solamente passare i messaggi praticamente.
Si va avanti così e man mano che la distanza aumenta rimarranno solo quelli piccoli. Come fa uno ad accorgersi che ha battuto tutti quanti? Come lo so senza sapere i nodi in termini di numero? Beh se il messaggio che mando a sx ritorna a dx, allora va bene! Perché i messaggi viaggiano ad una distanza che viene ogni volta raddoppiata. Ad una certa a forza di raddoppiare il messaggio riesce a tornare indietro.
Gliene potrebbero arrivare contemporaneamente da una parte e dell’altra perché potrei avere dei ritardi sui links, ma ad un certo punto arrivano. Gli altri non hanno assolutamente idea e quindi alla fine a meno che poi il vincitore non vada a notificare tutti quanti. Considera sempre che mandi messaggi a distanza che si raddoppia sempre.
Inserisci il codice del protocollo
Non è esplicitato il concetto di stage, ma è incluso nel protocollo.
La distanza 2^i ci permette di derivare delle interessanti limitazioni sul numero di messaggi che girano. Nel caso peggiore all’andata siamo 2^i come messaggio per ogni nodo: più precisamente 2*2^i (avanti e indietro) e alla fine se ne faccio il doppio: 2 x (2 x 2^i)