Informalmente, il problema della elezione distribuita consiste nel far sì che un insieme di processi peers distribuiti scelgano (eleggano) un processo destinato a svolgere uno specifico ruolo, che la scelta sia unica, e che tutti siano consapevoli dell’esito della scelta.
Un esempio applicativo:
- i processi votano e devono concordare tutti sull’esito dell’elezione;
- quando il server vuole rinunciare al suo ruolo (o si guasta), viene indetta un’altra elezione.
Si dice che un processo indìce l’elezione, se intraprende l’azione di iniziare l’esecuzione dell’algoritmo di elezione.
In linea generale, un algoritmo di elezione distribuita considera un sistema con N processi pi, i = 1, …, N.
Il sistema è asincrono.
I processi sono soggetti a fallimenti per crash.
I canali sono affidabili, e i messaggi prima o poi sono consegnati intatti una e una sola volta.
Un processo non indice più di una elezione alla volta.
È possibile che due o più processi indìcano concorrentemente altrettante elezioni.
I processi hanno identificativi univoci (id) numerici, e si assume – senza perdita di generalità – che il processo da eleggere sia quello con l’id più elevato.
In ogni istante, un processo è partecipante o non-partecipante.
Ogni processo pi ha una variabile electedi, che conterrà l’identificativo del processo eletto (inizialmente electedi = ⊥ , valore indefinito).
I requisiti che devono essere soddisfatti da un algoritmo di elezione sono:
Possono dunque esserci processi pj non ancora partecipanti, che in electedj conservano il risultato di una precedente elezione.
Gli algoritmi di elezione distribuita possono essere valutati in base ai seguenti criteri:
Serve a comprendere le caratteristiche generali di un algoritmo di elezione, ma si basa sull’ipotesi che non ci siano fallimenti, perciò nella versione base (Chang e Roberts, 1979) è di limitata utilità pratica.
I processi sono organizzati logicamente ad anello: il processo pi ha un canale di comunicazione con il successivo p(i+1)mod N.
I processi si scambiano messaggi sempre nella stessa direzione.
Inizialmente tutti i processi sono non-partecipanti.
Qualunque processo può indire l’elezione; a tale scopo:
Un processo che riceve un messaggio di elezione confronta l’id nel messaggio di elezione con il proprio id:
Un processo che riceve un messaggio eletto:
Il requisito E1 è soddisfatto in quanto tutti gli id sono confrontati, poiché un processo deve ricevere di nuovo il suo id prima di trasmettere il messaggio elected.
Per ogni coppia di processi, quello con id più elevato non inoltra l’id dell’altro, perciò è impossibile che entrambi ricevano di nuovo il proprio id.
Il requisito E2 discende dall’assenza di guasti.
Esempio nella figura a lato:
A. Se un solo processo pi indìce l’elezione, il caso peggiore è quello in cui il processo precedente pi ha l’id più elevato.
I messaggi inviati sono in totale 3N-1:
N-1 messaggi per raggiungere il processo precedente pi;
N messaggi prima che tale processo possa annunciare la sua elezione;
N messaggi eletto.
B. Il tempo di turnaround è quello di 3N-1 messaggi (poiché sono inviati sequenzialmente).
L’algoritmo del prepotente (bully) (Garcia-Molina, 1982) assume – a differenza dell’algoritmo ad anello – che:
Un processo indìce un’elezione quando si accorge – tramite timeout – che il coordinatore è fallito.
Più processi possono indire un’elezione concorrentemente.
L’algoritmo prevede 3 tipi di messaggi:
Poiché il sistema è sincrono, il tempo:
T = 2 Ttrasm + Telab
dove Ttrasm è il massimo tempo di trasmissione di un messaggio e Telab è il massimo tempo di elaborazione di un messaggio, rappresenta un limite superiore al tempo che trascorre dall’invio di un messaggio alla ricezione della risposta.
Il processo che sa di avere l’id più elevato può auto-eleggersi, inviando a tutti gli altri il messaggio coordinator col proprio id.
Qualunque altro processo può indire un’elezione inviando il messaggio election ai processi con id più elevati e attendendo i messaggi answer. Se non riceve alcuna risposta nel tempo T, si auto-elegge, inviando il messaggio coordinator con il proprio id ai processi con id minori.
Quando un processo riceve un messaggio coordinator, assegna l’id contenuto nel messaggio alla propria variabile electedi.
Quando un processo riceve un messaggio election, risponde col messaggio answer e indice un’altra elezione (se non ne ha già in corso una).
In caso di crash, il processo che fallisce viene sostituito da un altro processo.
Se questi ha l’id più elevato, si autoelegge, inviando il messaggio coordinator. È possibile però che il coordinatore fosse operativo, perciò il nuovo processo – autoeleggendosi – fa il prepotente.
Il requisito E2 (liveness) è soddisfatto in quanto i canali sono affidabili.
Se nessun processo viene sostituito in seguito a crash, anche il requisito E1 (safety) è soddisfatto, poiché è impossibile che due processi si autoeleggano coordinatori, dal momento che quello con l’id più basso non può non scoprire l’esistenza in vita dell’altro.
Il requisito E1 non è soddisfatto se un processo p fallito viene sostituito da un altro con il medesimo id. In tal caso infatti non solo il nuovo processo, ma anche un altro processo che nel frattempo si sia accorto del crash di p potrebbero ritenersi coordinatori, e ci sarebbero due messaggi coordinator in circolazione. Non essendoci garanzia della consegna ordinata dei messaggi, due riceventi potrebbero riconoscere due coordinatori diversi.
A. Il caso migliore è quello in cui ad accorgersi per primo del crash del coordinatore sia il processo picon il secondo id (per valore): in tal caso pi si autoelegge inviando N-2 messaggi coordinator.
Il caso peggiore è quello in cui ad accorgersi per primo del crash del coordinatore sia il processo con l’id minore in assoluto: in tal caso sono indette N-1 elezioni, ognuna delle quali comporta l’invio di O(N) messaggi ai processi con id più elevati. Nel caso peggiore l’algoritmo richiede dunque O(N2) messaggi.
B. Nel caso migliore, il tempo di turnaround è di un solo messaggio.
1. Caratterizzazione dei sistemi distribuiti
2. Modelli di sistemi distribuiti
3. Tempo e sincronizzazione nei Sistemi Distribuiti
4. Stato globale nei Sistemi Distribuiti
5. Problemi di consenso nei sistemi distribuiti
7. Algoritmi di mutua esclusione nei sistemi distribuiti
8. Algoritmi di elezione nei sistemi distribuiti
10. Il Network File System di SUN Microsystems
11. AFS (Andrew File System) e GFS (Google File System)
12. Transazioni e controllo di concorrenza
13. Transazioni
15. Affidabilità (dependability) dei sistemi software distribuiti
16. Affidabilità dei sistemi software distribuiti
17. Software Faults
18. Classificazione e analisi dei difetti software
G. Coulouris et al.: Distributed Systems: Concepts and Design (Cap. XII §3), IV ed., 2005.