Architetture distribuite per il Cloud (Sistemi Distribuiti)

2020/2021

ARCHITETTURE DISTRIBUITE PER IL CLOUD

(Sistemi Distribuiti) – APPUNTI

CORSO LAUREA MAGISTRALE – CLOUD COMPUTING 1

Sommario

1. Introduzione .............................................................................................................................................. 4

1.1. Algoritmo distribuito per il problema dei due generali bizantini ................................................... 4

1.2. Modello formale per descrivere gli algoritmi ................................................................................. 5

2. Algoritmi di Base ....................................................................................................................................... 6

2.1. Broadcast/Convergecast ................................................................................................................... 6

2.1.1. Flooding ..................................................................................................................................... 6

2.1.2. Spanning tree dal flooding........................................................................................................ 6

2.1.3. Spanning Tree DFS (visita in profondità) ................................................................................... 7

2.2. Algoritmo distribuito per Minimum-weight Spanning Tree ............................................................ 8

2.2.1 Introduzione al Minimum-weight Spanning Tree ........................................................................... 8

2.2.2. Esecuzione Algoritmo ..................................................................................................................... 9

2.2.3. Descrizione dell’algoritmo ............................................................................................................ 10

2.2.4. Pseudo-Codice Algoritmo ............................................................................................................. 11

2.2.5. Correttezza e complessità ............................................................................................................ 13

3. Algoritmi di elezione ............................................................................................................................... 14

3.1. Algoritmo asincrono uniforme ....................................................................................................... 15

3.1.1. Algoritmo base ........................................................................................................................ 15

3.1.2. Algoritmo ottimale.................................................................................................................. 15

3.1.3. Lower Bound ........................................................................................................................... 16

3.2. Elezione leader con sincronismo .................................................................................................... 18

3.2.1. Algoritmo sincrono non uniforme .......................................................................................... 18

3.2.2. Algoritmo sincrono uniforme ................................................................................................. 18

3.2.3. Lower bound ........................................................................................................................... 20

4. Memoria condivisa ................................................................................................................................. 22

4.1. Algoritmo del fornaio ..................................................................................................................... 22

4.2. Algoritmo alternatico...................................................................................................................... 22

4.2.1. Per 2 processori ....................................................................................................................... 22

4.2.2. Per n processori ....................................................................................................................... 23

5. Il problema del consenso - con crash ..................................................................................................... 23

5.1. Modello del problema .................................................................................................................... 23

5.2. Algoritmo ........................................................................................................................................ 24

5.2.1. Accordo: Lemma ..................................................................................................................... 24

5.3. Lower Bound ................................................................................................................................... 24

5.3.1. 1 fault 2 round necessari ........................................................................................................ 25

6. Il problema del consenso – bizantino .................................................................................................... 27

2

6.1. Primo lower bound ......................................................................................................................... 28

6.1.1. Lower Bound ai round ............................................................................................................ 28

6.2. 1° Algoritmo .................................................................................................................................... 28

6.2.1. Lemma ..................................................................................................................................... 29

6.2.2. Validità, Accordo e Complessità ............................................................................................. 30

6.3. 2° Algoritmo (Algoritmo del King) .................................................................................................. 30

6.3.1. Validità e Accordo ................................................................................................................... 31

7. Impossibilità del consenso asincrono e algoritmi .................................................................................. 31

7.1. Impossibilità del consenso asincrono ............................................................................................ 31

7.2. Algoritmo Paxos .............................................................................................................................. 33

7.2.1. Idee .......................................................................................................................................... 34

7.2.2. Fase 1 (prepare) ...................................................................................................................... 34

7.2.3. Fase 2 (accept) ......................................................................................................................... 34

7.2.4. Proprietà.................................................................................................................................. 34

7.2.5. Esempio senza fallimenti ........................................................................................................ 35

7.2.6. Valore scelto ............................................................................................................................ 35

7.2.7. Safety ....................................................................................................................................... 35

7.3. Raft .................................................................................................................................................. 36

7.3.1. Descrizione .............................................................................................................................. 36

7.3.2. Proprietà.................................................................................................................................. 36

8. Causalità e tempo ................................................................................................................................... 37

8.1. Definizioni ....................................................................................................................................... 38

8.2. Teoremi ........................................................................................................................................... 38

8.3. Applicazioni della relazione HB (happens before) ......................................................................... 39

8.3.1. Problema 1: trovare Maxiamal Consistent Cut ...................................................................... 39

8.3.2. Problema 2: Distributed Snapshot ......................................................................................... 39

3

SISTEMI DISTRIBUITI (Clusters or MPPs)

Il cloud computing si basa sulle idee e sull’esperienza accumulata in molti anni di ricerca in sistemi paralleli

e distribuiti.

1. Introduzione

Un Sistema Distribuito è una collezione di dispositivi con autonome capacità di calcolo e capaci di

comunicare tra loro. Un Algoritmo Distribuito è un algoritmo per un Sistema Distribuito.

Sono incredibilmente flessibili ed efficienti ma difficili da mettere a punto. Inoltre hanno diversi problemi:

loro natura asincrona, conoscenza locale limitata cioè la conoscenza di tutto il sistema è limitata al nodo

stesso e ai suoi vicini e infine i fallimenti.

Sono difficili da progettare, non c’è un modello accettato (non posso fare quindi una classificazione del tipo

il mio algoritmo è meglio di un altro), comunicazione di message passing e memoria condivisa, problema di

fallimenti e timing. E praticamente impossibile dimostrarne la correttezza.

La misura di complessità più accreditata per misurare l’efficienza di un algoritmo distribuito è contare il

numero totale di messaggi spediti nell’esecuzione di tutto l’algoritmo: complessità di messaggio.

Si potrebbe parlare di complessità di tempo anche in sistemi distribuiti asincroni attraverso un artificio,

cioè si normalizza tutto all’arco più lento.

1.1. Algoritmo distribuito per il problema dei due generali bizantini

I messaggi sono l’unica comunicazione possibile, e devono

passare attraverso la valle ma non sempre ci riescono,

possono perdersi (c’è fallimento).

Non esiste alcun algoritmo distribuito che possa garantire che

i due generali attacchino contemporaneamente.

Prova: Supponiamo esista, sia A, ed usi il numero minimo di

messaggi. A deve assicurare la correttezza anche se un

messaggio non viene mai recapitato. Supponiamo che l’ultimo

messaggio non venga mai recapitato, allora esso è superfluo e

può essere eliminato. Ma allora A non è l’algoritmo che

impiega il numero minimo di messaggi. 4

1.2. Modello formale per descrivere gli algoritmi

 Comunicazione: Shared memory o message passing

 Timing: Sincrono (poco realistico ma buono per lo sviluppo di

o algoritmi e per prove di impossibilità) parte l’algoritmo se

passa troppo tempo (timeout) lo fermo e lo faccio ripartire,

siccome il numero di volte che deve essere fermato è molto

basso possono essere utilizzabili anche per sistemi asincroni.

Semi-sincrono: non c’è un singolo clock, ma la frequenza di

o clock è esattamente la stessa.

Asincrono: ritardi di trasmissioni non predicibili e non c’è

o alcuna sincronizzazione tra i nodi, buon modello per sistemi

concorrenti.

 Fallimenti:

Perdita di messaggi

o Crash: il nodo smette di funzionare, dopo aver mandato un sottoinsieme di messaggi scompare

o senza causare altri problemi (fallimento buono)

Partizionamento: un sistema distribuito diventa 2 sistemi distribuiti separati

o Bizantino: si assume che se un processore va in fallimento, può mettersi a lavorare contro

o l’algoritmo I nodi sanno grazie alle numerazioni degli archi a quale

nodo inviare un messaggio. La numerazione è locale.

Ogni p è una macchina a stati, Q l’insieme degli stati, I

i i i

insieme degli stati iniziali. 5

Cos’è un evento (fi) dipende dal timing cioè: sincrono ogni ciclo di clock

tutti i processori (o nodi) si trovano nelle stesso stato. Asincrono invece

tutti i processori rimangono nello stesso stato tranne uno, cioè quello

che applica la sua funzione di transizione e cambia stato.

Safety: ogni processore esegue un numero infinito di passi di computazione, liveness: ogni messaggio

inviato verrà recapitato.

Per ogni esecuzione la sequenza di eventi è chiamata schedule. Schedule aperto se c’è almeno un arco sul

quale non viene spedito alcun messaggio.

La complessità di tempo per il sincrono è il numero totale di round fino alla fine della terminazione, per

l’asincrono invece ad ogni esecuzione C C … viene associato un times, il tempo è una funzione non

Φ Φ

0 1 1 2

decrescente ma è strettamente crescente per gli eventi di un singolo processore. Il timestamp serve per

calcolare il ritardo id messaggio, cioè la differenza tra il tempo dell’evento che processa il messaggio ed il

tempo dell’evento che lo aveva spedito. Tra tutte le esecuzioni ammissibile si calcola il massimo e lo si

normalizza a 1.

Algoritmi di Base

2. Broadcast/Convergecast

2.1.

Supponiamo di conoscere uno spanning tree radicato.

l’algoritmo ha complessità di tempo d per MPS (message passing sincrono), dove d è la profondità dello ST

Prova: Induzione sulla profondità t dei nodi. t =1 i vicini della radice ricevono M al passo 1.

Supponiamo che i nodi a profondità t-1 ricevano M al tempo t-1.

Al tempo t al passo 4 dell’algoritmo tutti e soli i processori a profondità t-1 inviano M a processori a

profondità t.

Conosciamo già uno spanning tree con n nodi avrà n-1 archi ognuno attraversato da esattamente 1

messaggio, quindi complessità di messaggio n-1.

Convergcast funziona esattamente all’opposto, cioè raccogliendo messaggi in unico nodo ma la

dimostrazione e i tempi di complessità e messaggio sono identiche.

2.1.1. Flooding p

Supponiamo di non avere uno ST, ma di avere un nodo fissato per la radice. Per effettuare un broadcast

r

possiamo usare il flooding. Complessità di messaggio:2m – (n-1) dove m è il

numero di link del sistema (tutti vedono i nodi

vedono i messaggi 2 volte tranne n-1 archi che sono

stati eletti parent).

2.1.2. Spanning tree dal flooding

Modificando questo algoritmo del flooding possiamo costruire un primo Spanning tree. 6

Localmente ogni nodo conserva l’informazione di chi è il padre e di chi sono i figli. Abbiamo dovuto

aggiungere due nuovi messaggi <reject> e <parent> rispetto al flooding. Ogni messaggio M su un arco

produce un messaggio <reject> oppure un messaggio <parent>. Complessità di messaggio è O(m).

Correttezza: Una volta stabilita la relazione padre figlio essa non può più essere modificata, l’insieme dei

figli non decresce

Come dimostriamo che il grafo costruito da questo algoritmo sia connesso e aciclico (Spanning Tree)?

Connesso: p

Supponiamo per assurdo che non sia connesso, allora il grafo indotto avrebbe un nodo non raggiungibile

j

p p p p p p

da . Devono quindi esistere due nodi e connessi da un arco e tali che è raggiungibile da e non

r i j i r j

p p

lo è. Ma se non è raggiungibile da , non deve aver mai assegnato un valore alla variabile parent . Ma

j r j

p p

quando ha assegnato la propria variabile parent ha mandato un messaggio a che deve aver assegnato

i j

i

un valore a parent (quindi necessariamente è parte dello spanning tree).

j

Aciclico:

Supponiamo ci sia un ciclo, due processori consecutivi sono nella relazione padre/figlio. Il primo ha quindi

visto il messaggio M per la prima volta prima del secondo. La proprietà si estende per transitività a un

qualsiasi percorso ed in particolare al ciclo. Un nodo del ciclo ha quindi visto per la prima volta M prima del

nodo stesso.

2.1.3. Spanning Tree DFS (visita in profondità)

Ancora una volta assumiamo di avere un nodo distinto che farà da radice.

Ogni nodo avrà una variabile unexplored dove vengono mantenuti i vicini ancora da visitare. I vicini in

unexplored vengono visitati uno per volta. L’analisi è del tutto simile a quella effettuata per l’algoritmo

precedente. Differenza sostanziale è la complessità di tempo che passa da O(n) nel caso peggiore a O(m)

dove n è il numero di nodi e m il numero di archi. la visita DFS è uno dei classici problemi

non parallelizzabili.

Supponiamo di voler costruire uno spanning tree DFS senza partire da un nodo distinto (ciò vuol dire che

più nodi possono far partire l’algoritmo).

È strettamente necessario che la rete sia identificata, cioè che ogni nodo ha un identificatore unico nella

rete (per eleggere un leader).

Un qualunque nodo può iniziare la costruzione (eventualmente tutti). Il messaggio contiene l’identificatore.

Viene costruito lo ST DFS la cui radice ha l’id più alto tra i partecipanti. p ,

Inizialmente per ogni nodo: parent è nil, leader=0, children è vuoto, unexplored contiene tutti i vicini di i

id contiene l’identificatore del nodo. 7

Fine

Si ricomincia visita DFS

Inizia

visita DFS

Si ricomincia: Quando un nodo scopre che fa parte di un frammento che non fa parte dello ST finale cambia

frammento e svuota tutti i nodi esplorati (butta tutto il suo lavoro altrimenti si creerebbe un ciclo).

p

Uno dei vicini ha finito l’esplorazione e riconosce come

i

padre.

Il nodo ha terminato l’esplorazione. Se è la radice termina

l’algoritmo.

La complessità di messaggio risulta O(nm), perché ci sono

O(n) costruzioni distinte di ST e per costruirlo non posso

fare altrimenti se non attraversare tutti gli archi. La

complessità di tempo O(m), perché attraversiamo tutti gli

archi.

2.2. Algoritmo distribuito per Minimum-weight Spanning Tree

2.2.1