Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Ingegneria
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Stefano Russo » 8.Algoritmi di elezione nei sistemi distribuiti


Sommario

  • Formulazione del problema dell’elezione distribuita
  • Algoritmo ad anello di Chang e Roberts
  • Algoritmo del prepotente di Garcia-Molina
  • Valutazione degli algoritmi

Algoritmi di elezione: definizione

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:

  • nell’algoritmo del server centrale per la mutua esclusione distribuita, tipicamente occorre o è opportuno scegliere il server tra i processi che condividono la risorsa;
  • 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.

Elezione distribuita: modello di sistema

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.

Elezione distribuita: requisiti

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:

  • E1 (safety): un partecipante pi ha electedi = ⊥ o electedi = P, dove P è il processo superstite con l’identificativo più alto, eletto alla fine dell’algoritmo.
  • E2 (liveness): tutti i processi pi partecipano e prima o poi definiscono un valore per electedi ≠ ⊥ , se non vanno in crash.

Possono dunque esserci processi pj non ancora partecipanti, che in electedj conservano il risultato di una precedente elezione.

Elezione distribuita: criteri di valutazione

Gli algoritmi di elezione distribuita possono essere valutati in base ai seguenti criteri:

  • banda di rete (network bandwidth) consumata, proporzionale al numero di messaggi inviati;
  • tempo di esecuzione dell’elezione (turnaround time), misurato come insieme dei tempi di trasmissione dei messaggi serializzati tra l’inizio e la fine di una esecuzione.

Algoritmo ad anello

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:

  • diventa partecipante;
  • mette il suo id in un messaggio di elezione;
  • invia il messaggio al suo successore nell’anello.

Algoritmo ad anello

Un processo che riceve un messaggio di elezione confronta l’id nel messaggio di elezione con il proprio id:

  • se l’id ricevuto è il maggiore,
    • diventa partecipante;
    • inoltra il messaggio di elezione;
  • se il proprio id è il maggiore e il processo è ancora non-partecipante:
    • sostituisce il proprio id nel messaggio;
    • diventa partecipante e inoltra il messaggio di elezione;
  • se il proprio id è il maggiore e il processo è già partecipante:
    • non inoltra il messaggio di elezione.
  • se gli id sono identici (il ricevente ha l’id più elevato):
    • diventa il coordinatore e non-partecipante;
    • invia il messaggio eletto, con il proprio id.

Algoritmo ad anello

Un processo che riceve un messaggio eletto:

  • diventa non-partecipante,
  • definisce il valore della propria variabile electedi;
  • se non è il coordinatore
    • inoltra il messaggio eletto;

Algoritmo ad anello

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:

  • elezione indetta dal processo 17;
  • partecipanti correnti in marrone scuro;
  • l’identificativo corrente più alto è 24.

Algoritmo ad anello – valutazione

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).

Algoritmo del prepotente (bully)

L’algoritmo del prepotente (bully) (Garcia-Molina, 1982) assume – a differenza dell’algoritmo ad anello – che:

  • I processi sono soggetti a fallimenti per crash;
  • Il sistema è sincrono;
  • Ogni processo conosce quali altri processi hanno id più elevati;
  • Ogni processo può comunicare con i processi con id più elevati.

Un processo indìce un’elezione quando si accorge – tramite timeout – che il coordinatore è fallito.
Più processi possono indire un’elezione concorrentemente.

Algoritmo del prepotente

L’algoritmo prevede 3 tipi di messaggi:

  • Election: annuncia un’elezione;
  • Answer: inviato in risposta a un annuncio di elezione;
  • Coordinator: dichiara l’identità del processo eletto.

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.

Algoritmo del prepotente

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).

Algoritmo del prepotente

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.

Algoritmo del 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.

Algoritmo del prepotente – valutazione

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.

I materiali di supporto della lezione

G. Coulouris et al.: Distributed Systems: Concepts and Design (Cap. XII §3), IV ed., 2005.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion