Problema della Terminazione
per reti asincrone in algoritmi
distribuiti
Fabio Bassino - Luca Cacchiani
Monitoraggio di algoritmi per reti asincrone
durante l'esecuzione
Un algoritmo per il monitoraggio di reti asincrone
deve essere in grado di:





Assistere nel debug verificando gli invarianti
creare dei backup dello stato globale di
computazione
capire quando un algoritmo termina la computazione
rilevare i deadlock
compiere ulteriori calcoli sull'algoritmo (per esempio
delle statistiche)
Monitoraggio di algoritmi per reti asincrone
durante l'esecuzione
In questa presentazione ci concentreremo
prevalentemente su queste due nozioni


snapshot coerente dello stato globale
stato globale di un algoritmo rilevato su tutti i processi e
su tutti i canali nel medesimo istante
rilevamento della proprietà stabili
una proprietà definita stabile e’ una proprietà di uno
stato globale di un algoritmo distribuito che, una volta
assunta vera, rimane tale per sempre (ad esempio un
deadlock o la terminazione)
Monitoraggio di algoritmi per reti asincrone
durante l'esecuzione
Algoritmo di monitoraggio
Un algoritmo di monitoraggio B(A) e’ definito come una
versione estesa dell’algoritmo originale A. L’algoritmo B(A)
non modifica i processi di computazione dell’algoritmo A,
bensì introduce nuovi input ed output ed estende lo spazio
degli stati dell’algoritmo A.
Problema della terminazione per algoritmi
a diffusione
Un algoritmo a diffusione e’ un algoritmo in cui tutti
processi sono inizialmente fermi tranne il processo
iniziale. I processi vengono attivati quando ricevono un
messaggio.
Immaginiamo di avere un grafo, in cui tutti gli stati
rappresentano i processi coinvolti nel nostro algoritmo a
diffusione.
Inizialmente tutti i nostri processi sono in uno stato di
riposo, ovvero uno stato in cui la computazione è ferma ed
il processo è pronto a ricevere degli input da elaborare e
non ci sono messaggi nei canali.
Problema della terminazione per algoritmi
a diffusione
Quando un processo “i” riceve un messaggio, esce
dallo stato di riposo, elabora il messaggio e lo diffonde
agli altri processi, svegliandoli di conseguenza.
Il problema della terminazione vuole dimostrare che
dopo la computazione, quando tutti i processi sono tornati
allo stato di riposo, nel nodo iniziale sarà stato prodotto
l'output desiderato e l'algoritmo sarà quindi terminato
Problema della terminazione per algoritmi
a diffusione
Utilizzeremo l'algoritmo B(A), che per questo
problema si comporterà nel modo seguente:





conterrà nuovi stati non presenti nell'algoritmo A
lo stato iniziale di B(A) sarà lo stesso dell'algoritmo A
dovendo contenere nuovi stati, l'algoritmo B(A) avrà a
sua disposizione nuovi input, output e funzioni non
presenti nell'algoritmo A
questi input saranno accodati ad esempio come
parametri aggiuntivi di funzioni dell'algoritmo A
gli input di B(A) aggiuntivi porteranno modifiche
esclusivamente negli stati di B(A) non presenti in A
Problema della terminazione per algoritmi
a diffusione
Nel 1980 Dijkstra e Scholten proposero un
schema per la soluzione di questo problema.
Partendo dal concetto di grafo di processi
definito in precedenza, l'algoritmo B(A) crea un
albero contenente le relazioni tra processi padri
e processi figli. Quest’albero può essere
schematizzato nella modo seguente:
Problema della terminazione per algoritmi
a diffusione


il processo iniziale della computazione è la radice
dell'albero
appena un processo riceve un messaggio:




se era nello stato di riposo (è il primo messaggio che riceve),
viene aggiunto un nodo all’albero. Tale nodo sarà figlio del
nodo (processo) che ha spedito il messaggio
se non era nello stato di riposo, viene mandato un ack al
processo che ha spedito il messaggio, e si prosegue nella
computazione
quando un processo non ha figli ed entra in uno stato di
riposo (ha finito la computazione), viene tolto il nodo
dall'albero legato al processo e viene mandato un ack
al processo padre
l'algoritmo termina quando il nodo padre non ha piu’ figli
ed è in uno stato di riposo
R
Nodo a riposo
Nodo occupato
2
3
Nodo bloccato
Messaggio
1
Ack
Albero
3IlIlOra
3manda
nodo
Analogamente
1
nostro
nodo
ha
torna
12e’manda
finito
eR
213sistema
un
che
in
riceve
ricevono
la
uno
messaggio
un
torna
computazione
ilstato
un
messaggio
2e’
messaggio
manda
ilin
input,
composto
messaggio,
di
uno
ariposo,
si
2.
stato
unsveglia
a
Dato
eed
messaggio
da
2,
torna
quindi
diimposta
eimpostano
quattro
che
riposo,
dato
edimanda
ilmanda
uno
che
puntatore
nodi,
ilaquindi
puntatore
1,
stato
due
entrambi
un
che
un
inizialmente
messaggio
manda
ha
di
ack
del
avendo
riposo,
gia’
padre
apadre
il R,
un
manda
di al
suo
2 quindi
impostato
e’
anche
nodo
nodo
gia’ R.
stato
un
luipadre.
tutti
1ack
puntatore
ack
un
ilmanda
impostato,
padre
padre
in
al
alal
La
stato
nodo
padre
nodo
computazione
gli
due
gli
padre
di
restituisce
padre
restituira’
per
1
messaggi,
2riposo
manda
astaccarsi
1 un
un
e’a ack
finita!
ack
2dall’albero
e 3a 3
Problema della terminazione per algoritmi
a diffusione
Invarianti di stato






statusi  { source, idle } e parenti = null
per ogni j  i, statusj  { idle, non-source }, e se statusj = nonsource allora parentj  null
per ogni j, se statusj = idle, allora il corrispondente stato di Aj
è di riposo, parentj = null e deficit(k)j = 0 per ogni k
per ogni j e k, deficit(k)j è la somma di quattro valori: il
numero di messaggi nel canale da j a k, il numero di ack in
send-buffer(j)k, il numero di ack nel canale da k a j, più 1 se
parentk = j
se statusi = source, allora i puntatori dei padri guardano ad “i”
come il nodo radice e lo collegano all'insieme dei nodi con
status  idle
se statusi = idle, allora statusj = idle per tutti “i”e “j”, e tutti i
canali sono vuoti
Problema della terminazione per algoritmi
a diffusione
L’algoritmo di Dijkstra Scholten rileva la
terminazione di un qualsiasi algoritmo a diffusione
Dimostrazione
Per il terzo e sesto invariante di stato sappiamo che un algoritmo quando torna
in uno stato di riposo produrrà un output.
Per assurdo ipotizziamo che non ci sia output quando l’algoritmo torna in uno
stato di riposo. In questo stato di riposo, nessun output e’ prodotto (in base alla
definizione di riposo, tutti processi sono in attesa di input e nessun messaggio
e’ presente nei canali). Questo implica che l’albero che raccoglie i processi
padri e’ stabile, ovvero non si amplia ne si restringe. Non essendoci messaggi
nei canali, non ci sono neppure messaggi di ack.
La funzione deficit(k), introdotta tra le varianti di stato, restituirà sempre 0. Ma
questo implica che la procedura cleanup, introdotta nel codice sia abilitata per
l’esecuzione, e che quindi all’albero dei padri sia concesso di ridursi. Ma questa
e’ una contraddizione, in base a quanto abbiamo detto precedentemente!
Da questo possiamo dedurre che quando arriviamo in uno stato di riposo
globale, un output deve essere restituito.
Problema della terminazione per algoritmi
a diffusione
Analisi della complessità
Facilmente la complessità dell’algoritmo dipende dal
numero di messaggi spediti dall’algoritmo distribuito. In
particolare la complessità per un algoritmo distribuito che
sappiamo restituisca un determinato output sarà O(2m),
con m il numero dei messaggi spediti durante l’esecuzione
dell’algoritmo. Il coefficiente 2 arriva dalla necessità di
mandare dei messaggi di ack da parte dell’algoritmo.
Possiamo definire quindi lineare la complessità
dell’algoritmo
Snapshot globale coerente
Problema:
effettuare uno snapshot globale coerente di un algoritmo di
rete con send e receive asincrone.
Uno snapshot è coerente se riesce a catturare lo stato dei
processi del sistema come se ciascuno di essi fosse
osservato nello stesso istante
Snapshot globale coerente
Definiamo

G: grafo arbitrariamente connesso, non orientato

A: arbitrario algoritmo di rete che usa send/receive
asincrone

B(A): algoritmo di monitoraggio che e’ anch’esso un
algoritmo di rete basato sul grafo G

Ogni processo B(A)i dell’algoritmo di monitoraggio
B(A) deve essere definito nei termini degli Ai
Snapshot globale coerente
Caratteristiche di B(A):

Un’ esecuzione di B(A) contiene una esecuzione di A

B(A)i può ritardare un’azione di send effettuata da Ai

Ogni B(A) accetta in input un tipo di azione chiamato
snapi che gli permette di cominciare lo snapshot di Ai

Per riportare lo stato di Ai, ciascun B(A)i esegue una
report, che contiene lo stato di Ai più lo stato di tutti I
canali entranti in Ai.

Gli stati riportati da tutti i B(A)i rappresentano lo stato
globale di A
L’algoritmo di Chandy-Lamport
CL(A): algoritmo di monitoraggio di Chandy-Lamport

Quando un processo CL(A)i, che non e’ stato ancora
coinvolto nell’algoritmo di snapshot, riceve come input
uno snapi e registra lo stato di Ai; inoltre invia un
marker per ciascuno dei canali di uscita di Ai

Tutto quello che Ai invia su un canale dopo il marker
rimane incluso nello stato di Ai

Il maker segna il confine tra i messaggi spediti prima
che lo stato locale fosse registrato e quelli spediti
successivamente
L’algoritmo di Chandy-Lamport



CL(A)i registra inoltre tutti i messaggi che arrivano su
ciascun canale di ingresso di Ai creando uno stato per
ogni canale e smetterà di registrare all’arrivo di un
marker.
L’arrivo di un marker ad un CL(A)i che non e’ stato
ancora coinvolto nell’algoritmo di snapshot ha lo
stesso effetto di uno snapi. Inoltre lo stato del canale
da cui è arrivato il marker viene registrato come vuoto.
Quando Ai ha ricevuto i marker da tutti i canali di
ingresso CL(A)i può riportare lo stato di Ai
Two-dollar Bank
Scenario
1#
stato-A1
1$
0$
1$
0$
1#
1
stato-A2
stato-canale-in(2)1
stato-canale-in(1)2
2
CL(A)
Viene
effettuato
un marker
uno snap
a CL(A)
1 manda
A1 riceve il dollaro, 1 2
e inizia
Cl(A)
CL(A)
a12registrare
riceve
AA1212registra
manda
riceve
il marker
i ilmessaggi
1$
lodollaro
stato
adda
A12di
CL(A)
in
A1arrivo
1
2
CL(A)1 lo registra in stato-canale(2)
1
1
0
1
0
L’algoritmo di Chandy-Lamport
Analisi della complessità
L’algoritmo Chandy-Lamport(A) ha una complessità di O(E)
(dove E e’ numero di archi del grafo). Infatti ogni CL(A)i
invia un marker in ogni canale di uscita e riceve un marker
da ogni canale di ingresso quindi sono esattamente 2E
marker in giro per il sistema.
Applicazioni
Banking system
Qualunque algoritmo che produce uno snapshot globale
e coerente può essere utilizzato per contare quanti soldi ci
sono in un sistema bancario.
Applicazioni
Debug per algoritmi distribuiti
Un algoritmo che produce uno snapshot globale e
coerente può essere utilizzato per il debug di algoritmi
distribuiti.
Dato un algoritmo distribuito A, il debbuger ci permette di
verificare, durante un’esecuzione, se gli invarianti che
sono stati precedentemente definiti sono rispettati, su ogni
snapshot effettuato.
Applicazioni
Rilevazione delle proprietà di stabilità
Una strategia per determinare se una proprieta’ di
stabilità P e’ vera o meno consiste nell’osservare la
proprietà P in uno stato globale e coerente del sistema
ottenuto mediante uno snapshot.
Se P risulta vera al momento dello snapshot, P rimarrà
vera nello stato globale. Altrimenti se da uno snapshot
rileviamo P falsa, siamo certi che e’ stata falsa fino a quel
momento.
Applicazioni
Rilevazione della terminazione
Supponiamo di avere un algoritmo distribuito A in cui gli
stati non sono necessariamente a riposo e non abbiamo
input esterni (diversamente da quanto ipotizzato prima).
Quando A raggiunge uno stato globale di riposo (ovvero la
computazione e’ ferma e non ci sono messaggi nel canale),
la quiescenza diventa una proprietà stabile. Possiamo
quindi rilevare la terminazione utilizzando degli snapshot
per individuare tale proprietà.
Applicazioni
Rilevazione dei deadlock
Definiamo deadlock come un circolo di due o piu’ processi
ciascuno in attesa di un input dal processo precedente. Per
sapere quando la proprieta’ stabile di deadlock risulta vera
in un algoritmo distribuito A, utilizziamo la tecnica dello
snapshot multiplo.
Bilbliografia
Lynch, Distributed Algorithms, Kaufmann Ed - Chapter 19