129 lines
6 KiB
Markdown
129 lines
6 KiB
Markdown
|
# Introduzione agli Algoritmi Distribuiti
|
||
|
|
|
||
|
|
#### Note organizzative
|
||
|
|
La presenza ad almeno l'80% dei seminari e' richiesta (meglio se tutti). Gruppi di 4.
|
||
|
|
L'argomento trattato e' lo studio di algoritmi distribuiti progettati per l'esecuzione da parte di un insieme di processori autonomi, interconnessi tra loro da un sistema di scambio di messaggi.
|
||
|
|
*(cercare in rete lucidi di N.Lynch relativi al libro)*
|
||
|
|
|
||
|
|
## Algoritmi distribuiti
|
||
|
|
|
||
|
|
Sono algoritmi progettati per lavorare in sistemi distribuiti. Si occupano di:
|
||
|
|
* Comunicazione
|
||
|
|
* Gestione di risorse *(i.e. in mutua esclusione, in ambiente distribuito)*
|
||
|
|
* Sincronizzazione
|
||
|
|
* Consenso
|
||
|
|
|
||
|
|
Considerano:
|
||
|
|
* **attivita' concorrente**
|
||
|
|
* **indeterminatezza nella temporizzazione**, ossia nell'ordine di avvenimento degli eventi. Questo perche' si preferisce avere un protocollo distribuito rispetto ad uno centralizzato (in cui un server centrale puo' agire da vigile). Quindi, non siamo in grado di dire quando un evento accada e quanto tempo richieda.
|
||
|
|
* **possibilita' di errori** (guasti a processori, canali di comunicazione). Questi casi sono gestiti tramite strategie specifiche. **Algoritmi fault-tolerant**.
|
||
|
|
|
||
|
|
Gli algoritmi distribuiti sono difficili da progettare ma soprattutto **difficili da analizzare**, e' quindi difficile stabilire la correttezza e analizzare la complessita' di un AD. La difficolta' e' data soprattutto dall'*interleaving variabile*, ossia dal cambiamento della sequenza di istruzioni da esecuzione a esecuzione.
|
||
|
|
|
||
|
|
Il corso trattera' quindi l'analisi della correttezza formale degli algoritmi, dimostrandola.
|
||
|
|
|
||
|
|
## Modelli di sistemi distribuiti
|
||
|
|
|
||
|
|
I sistemi distribuiti si possono caratterizzare in:
|
||
|
|
* **Modalita' di comunicazione** (memoria comune / messaggi)
|
||
|
|
* **Sincronia / asincronia** di interazioni ed esecuzione
|
||
|
|
* **Fault tolerance**
|
||
|
|
|
||
|
|
#### Sistemi distribuiti con malfunzionamenti
|
||
|
|
|
||
|
|
##### Malfunzionamento di processi
|
||
|
|
|
||
|
|
* **Crash**: bloccato, non manda piu' nulla
|
||
|
|
* **Fallimento bizantino**: guastato ma non bloccato, manda messaggi incongrui.
|
||
|
|
|
||
|
|
##### Malfunzionamento di canali
|
||
|
|
|
||
|
|
* Perdita di messaggi
|
||
|
|
|
||
|
|
### Sistemi distribuiti Sincroni / Asincroni
|
||
|
|
|
||
|
|
In entrambi sistemi non esiste memoria comune.
|
||
|
|
|
||
|
|
#### Sistema Sincroni
|
||
|
|
|
||
|
|
Molto rari, impongono un gran numero di constraint.
|
||
|
|
|
||
|
|
* **Ritardo noto e limitato nella comunicazione**: e' noto un limite di tempo massimo per l'esecuzione di uno **step locale** da parte di un processo. E' anche noto un limite di tempo massimo nella trasmissione del messaggio. Quando questi tempi massimi scadono, si presuppone che nessun messaggio sia stato mandato (non fault tolerant). Viceversa un ambiente fault tolerant cerca di correggere l'errore.
|
||
|
|
|
||
|
|
*(vedi slides per modello sincrono)*
|
||
|
|
|
||
|
|
##### Fasi della computazione
|
||
|
|
|
||
|
|
1. Invio di messaggi a un insieme di processi P
|
||
|
|
2. Ricezione di messaggi da parte dei processi P
|
||
|
|
3. Cambio di stato
|
||
|
|
|
||
|
|
#### Sistemi Asincroni
|
||
|
|
|
||
|
|
Molto vicini ai sistemi di rete attuali.
|
||
|
|
|
||
|
|
* **Trasmissione non sicura**, non si puo' dire quanto un messaggio impiega ad arrivare (o se arriva). Non e' infatti noto alcun limite di tempo massimo, ne' per l'esecuzione ne' per la trasmissione.
|
||
|
|
|
||
|
|
Alcuni problemi **non hanno soluzione asincrona**, specialmente per una situazione falut tolerant o deterministica (che utilizza un algoritmo deterministico). Per questo i sistemi sincroni sono necessari, ma anche algoritmi randomizzati, sistemi che sincronizzino i vari processori, etc.
|
||
|
|
|
||
|
|
#### Descrizione di un algoritmo distribuito
|
||
|
|
|
||
|
|
Occorre specificare:
|
||
|
|
* Grafo di comunicazione
|
||
|
|
* possibilita' di fallimento di processi
|
||
|
|
*(vedi slides per elenco puntato)*
|
||
|
|
|
||
|
|
### Ricerca sugli algoritmi distribuiti
|
||
|
|
|
||
|
|
*(vedi slides)*
|
||
|
|
|
||
|
|
## Reti asincrone
|
||
|
|
|
||
|
|
Due tipi di modelli asincroni:
|
||
|
|
|
||
|
|
* Reti asincrone
|
||
|
|
* Sistemi asincroni con memoria condivisa
|
||
|
|
|
||
|
|
Le reti asincrone effettuano azioni interne ed esterne, eseguite dai processi in comunicazione. L'elemento di comunicazione e' sempre il canale (come per i sincroni), ma in questo caso **i canali possono venire intasati da piu' messaggi**.
|
||
|
|
|
||
|
|
L'obbiettivo e' trovare un formalismo matematico per descrivere processi e canali. Sono detti **reattivi** perche' interagiscono con l'ambiente circostante tramite azioni di input / output. Questo modello e' l'**automa di input/output**.
|
||
|
|
|
||
|
|
### Automi di input / output
|
||
|
|
|
||
|
|
Fornisce un modello matematico generale per componenti reattivi. E' inoltre adatto per descrivere sistemi in modo **modulare**.
|
||
|
|
|
||
|
|
Gli automi di in/out sono definiti da:
|
||
|
|
* un insieme di **azioni** (input / output / interne). Le azioni esterne sono input / output, le azioni locali sono le interne e le output. Tra le azioni di output c'e' *send*, tra le azioni di input *recv*.
|
||
|
|
* un insieme di stati (non necessariamente finito), diviso in stati iniziali, stati di transizione (stati x azioni x stati, prodotto cartesiano).
|
||
|
|
* un insieme di azioni locali (controllate localmente) che rappresenta le azioni **che non possono essere trasposte all'infinito**. Sono dette **tasks**.
|
||
|
|
|
||
|
|
*(vedi slides per esempio grafico)*
|
||
|
|
|
||
|
|
Inoltre:
|
||
|
|
|
||
|
|
* uno **step** di un automa e' un elemento della transizione
|
||
|
|
* un'azione e' detta **abilitata** se esiste uno step `(s, pi, s')` per qualche stato `s'`.
|
||
|
|
|
||
|
|
### Protocollo di consenso
|
||
|
|
|
||
|
|
*(vedi slides per sequenza)*
|
||
|
|
*(vedi slides per implementazione di esempio)*
|
||
|
|
|
||
|
|
### Modelli asincroni: esecuzioni
|
||
|
|
|
||
|
|
Un automa I/O esegue un modello asincrono:
|
||
|
|
* Parte da uno stato *start*
|
||
|
|
* Ripetutamente applica *step* e *trans* fino a uno stato finale
|
||
|
|
|
||
|
|
Essendo che tutte le azioni interne sono pesanti, definiamo **traccia** la sottosequenza delle azioni esterne presenti nelll'esecuzione (studio dal punto di vista dell'osservabilita' esterna). Spesso inoltre l'esecuzione e' divisa in **frammenti**.
|
||
|
|
|
||
|
|
#### Canali
|
||
|
|
|
||
|
|
Anche i canali sono modellati come automi. *(vedi slides per descrizione ed esempio)*
|
||
|
|
|
||
|
|
#### Stati raggiungibili
|
||
|
|
|
||
|
|
Uno stato e' **raggiungibile** se e' presente in una qualche esecuzione. Un **invariante** e' un predicato che e' sempre vero in ogni stato raggiungibile. Gli invarianti sono lo strumento piu' importante per provare le proprieta' degli algoritmi concorrenti e distribuiti.
|
||
|
|
*(vedi slides per esempio di uso dgli invarianti)*
|
||
|
|
|