Universita' degli Studi di Bari Aldo Moro - CdL …disys/sidys7concorrenza.pdfModelli non...

28/11/13

1

CdL MAGISTRALE in INFORMATICA

A.A. 2013-2014

corso di “Sistemi Distribuiti”

7. La concorrenza tra processi remoti nei sistemi distribuiti

Prof. S.Pizzutilo

Riferimenti: •  A.Tanenbaum,M.Van Steen “Sistemi distribuiti” Pearson

Prentice Hall 2007 ) •  A.A. Garganico 197474 CdLS Ingegneria Informatica

(0234) Reti di Calcolatori LS a.a. 2006/2007 •  Wikipedia http://en.wikipedia.org/wiki/Publish/subscribe •  De Leonardis Salvatore Seminari : 1) La mutua esclusione

nei sist. Distr. 2) Algoritmo di Bully •  Siciliano Giulia Matricola seminario : Dai sistemi

concorrenti a quelli distribuiti: il problema della mutua esclusione

Le forme della comunicazione

Messaggio : blocco di informazioni in un formato deciso dal processo mittente in modo che sia interpretabile dal processo ricevente.

Struttura del messaggio : header di lunghezza fissa + oggetti (di dati) di lunghezza variabile

Message passing p2 p1

Dati o puntatore

ai dati N. di byte/ tipi dati elementi

Identificatore del messaggio

Indirizzo indirizzo processo processo ricevente mittente

header

Shared data p1 p2 memoria condivisa

CdL in Informatica- Magistrale Università di Bari Sistemi Distribuiti -

28/11/13

2

Altre forme di comunicazione con sincronia virtuale

o  Message queueing: modello point to point o point to many o  Publish/Subscribe: modello many to many

Message Oriented Middleware (MOM) con le funzionalità di : ü  publish/subscribe topic-based, ü  message queueing. ü  Servizio di message storing e tipizzazione dei messaggi, ü  Interfacce e strutture dati a supporto dello scambio di informazioni su file

multimediali, come musica e film, ü  Gestione automatica del salvataggio dei messaggi, ü  Supporto per la comunicazioe sincrona e asincrona, ü  Implementazione schema di comunicazione point-to-point e point-to-many per quanto

riguarda il message queueing, ü  Tecnica di replicazione hot stand by, ü  Invio e ricezione dei messaggi con semantica at-most-once e once-and-only-once.

Comunicazione orientata ai messaggi

Per risolvere i problemi relativi alla natura prevalentemente sincrona dell’ IPC, si ricorre a soluzioni basate sulla comunicazione basata sullo scambio di messaggi (conservati o meno in code).

Problemi relativi alla persistenza ed alla sincronizzazione nella comunicazione

28/11/13

3

Architettura di un Message-Queuing System (1)

Relazione tra l’indirizzamento a livello di code e di rete

CdL in Informatica- Magistrale Università di Bari - Sistemi Distribuiti -

Rif.: A.Tanenbaum,M.Van Steen “Sistemi distribuiti” Pearson Prentice Hall 2007 )


Ad es. l’organizzazione generale di un sistema message-queuing mediante router.

2-29

CdL in Informatica- Magistrale Università di Bari Sistemi Distribuiti


28/11/13

4


4 modalità di comunicazioni loosely coupled con uso di code:

2-26

CdL in Informatica- Magistrale Università di Bari - Sistemi Distribuiti


Message Broker

Organizzazione generale di un sistema message-queuing mediante broker.



28/11/13

5

Altre forme di comunicazione sincronizzata

Publish/subscribe (pub/sub) è un paradigma di messaging asincrono nel quale i mittenti (sender o publisher) non indirizzano messaggi a specifici destinatari (receiver o subscriber), bensì ad un data manager. Quest’ultimo, utilizzando tecniche di message queuing, può organizzare i messaggi ricevuti in code “tematiche” (di interesse) o “classi” diverse. I destinatari (subscriber) accedono solo alla parte di messaggi pubblicati di loro interesse attraverso un processo di filtering che può essere topic-based o content-based. In alcuni sistemi i messaggi vengono gestiti da un intermediary broker che svolge la funzione di store-and-forward tra publisher e subscriber. Il Content-based filtering viene svolto dallo subscriber, prima che i messaggi vengano passati alla applicazione.

Esempi: WEB services ( SOA), CORBA, SCRIBE, TERA, GRYPHON, JEDI, IBM WebShere MQ,….

MOM Publish/Subscribe

Ø Authoring service: fornisce funzionalità di autenticazione al sistema.

Ø Discovery service: si occupa della gestione nomi dei servizi.

Ø  Publish-Subscribe subsytem: implementa le funzionalità definite dal modello P/S.

Ø M e s s a g e Q u e u e i n g : implementa le funzionalità definite dal modello MQ.

Ø Data Manager: si occupa della gestione dei dati . Fornisce interfacce di accesso trasparenti al sistema di m e m o r i z z a z i o n e d e l l e informazioni.

Tratto da : Andrea Antonio Garganico Implementazione MOM basata sul paradigma “Publish/Subscribe” e “Message Queueing”

28/11/13

6

…ancora sulla comunicazione multicast

  Nei sistemi distribuiti il supporto per l’invio di dati a molteplici destinatari ( “comunicazione multicast”), che può essere realizzato a livello di protocolli di rete (IP - IGMP) oppure a livello applicativo.

  La comunicazione multicast a livello applicativo può essere realizzata sia in maniera strutturata (creando “communication path” espliciti), sia non strutturata (affidandosi a tecniche applicative che simulano la diffusione delle epidemie).

  Un elemento di progettazione fondamentale per il multicast strutturato a livello applicativo è la costruzione di una rete “overlay” = una rete virtuale atta a fornire meccanismi non nativamente supportati dalla rete sottostante (ad es. il multicast).

Il multicast strutturato applicativo

Esistono due approcci fondamentali per l’implementazione del multicast strutturato applicativo con una rete overlay: Ø  il primo è che i nodi si possono organizzare direttamente in un

albero, il che significa che c’è un unico percorso tra una coppia di nodi ( ad es. CHORD);

Ø  l’altro vede i nodi organizzati in una rete a maglia in cui ogni nodo ha molti vicini, creando cosi molti percorsi diversi per ogni coppia di nodi.

La differenza principale tra i due approcci è che di solito il secondo è più robusto: infatti se cadesse un nodo, ci sarebbe ancora la possibilità di distribuire le informazioni senza la necessità di riorganizzare immediatamente l’intera rete.

28/11/13

7

Overlay network I PEER (nodi, risorse) si organizzano sovrapponendo (overlay) alla rete fisica una rete logica in modo da consentire la loro localizzazione senza dover specificare indirizzi IP, ma solo indirizzi logici (generati con una funzione hash e memorizzati in una hash table distribuita (DHT)). I peer si organizzano creando dei link virtuali fra loro.

Problema : STRETCH (o Relative Delay Penalty = RDP) ovvero rapporto tra il tempo di trasferimento del messaggio tra due nodi nella rete overlay ed il tempo nella rete fisica sottostante.

Rete Overlay con Distributed Hash Table (1)

Ciascun nodo (processo) mantiene un set di link agli altri nodi (i suoi vicini). Tutti insieme questi nodi formano una Overlay Network, con una sua topologia logica ad anello. Tutte le topologie di Overlay Network condividono la proprietà essenziale: Ad ogni peer viene assegnato un ID univoco (k) generato con una funzione hash . Per ciascuna chiave k, o il nodo possiede k oppure ha un collegamento ad un nodo che è più vicino a k in termini di distanza. Ad esempio in una rete ad anello (sistema CHORD):

1

3(0, 1, 2)

2

4

7

89

0(3, 4)

(7, 8, 9)

Sistema basato su DHT con topologia logica ad anello in cui ai dati ed ai nodi viene assegnata una chiave generata all’interno di uno spazio di identificatori di 160 bit, con uno schema di mappatura tra nodi e dati attraverso la loro chiave. Nella figura ad es. si hanno 3 nodi e complessivamente 5 dati (due dati associati al nodo 2, 1 al nodo 4 e 2 al nodo 9).

Per inserire un nuovo dato, viene generata la chiave k e viene mappato nel nodo con id >= k cioè nel nodo successore di k (succ(k)).

Per inserire un nuovo nodo, viene generata la chiave k che sarà l’id del nodo e così il nodo viene inserito logicamente tra il predecessore (pred(id)) ed il succ(id).

28/11/13

8

DHT (1)

Le tabelle hash distribuite (DHT) sono una tipologia di infrastruttura di sistemi basata su tabelle di coppie (key, value) relative ai nodi/risorse del sistema, nelle quali il valore delle key è calcolato con una funzione hash applicata al valore. Tale infrastruttura consente di disporre di un servizio efficiente di lookup su ad un vasto numero di nodi (peer).

Questo tipo di infrastruttura viene utilizzata per implementare servizi complessi, quali file system distribuiti, sistemi peer-to-peer di file sharing, multicast e domain name services,….

DHT (2)

Una DHT è costruita attorno ad un keyspace astratto, come un set di stringhe di 160-bit. L’appartenenza al keyspace è divisa tra i nodi partecipanti in base ad un ben definito schema per il partizionamento.

Un tipico funzionamento di una DHT per immagazzinare e poi recupare un dato può avvenire nel seguente modo:

Ø  Si supponga che il keyspace sia un set di stringhe di 160-bit. Ø  Per immagazzinare nella DHT un file caratterizzato dai parametri filename e dati,

viene inizialmente calcolato l’SHA1 del filename, producendo così una chiave k di 160-bit.

Ø  In seguito, un messaggio put(k, data) può essere inviato ad un qualsiasi nodo della rete DHT. Il messaggio è inoltrato di nodo in nodo attraverso l’overlay network (tra i succ(k)) fino a che esso non raggiunge il singolo nodo che è responsabile per la chiave k (laddove la coppia (k, data) è già stata immagazzinata).

Ø  Qualsiasi altro client può quindi successivamente recuperare i contenuti del file calcolando a sua volta l’hash del filename (per ottenere k) e chiedere ad un qualsiasi nodo della rete DHT di trovare il dato associato a k, tramite un messaggio get(k).

Ø  Il messaggio verrà quindi inoltrato attraverso l’overlay verso il nodo responsabile per k, che risponderà con una copia del dato immagazzinato.

28/11/13

9

A questo punto risulta quindi facile inoltrare un messaggio al proprietario di una qualsiasi chiave k utilizzando il seguente algoritmo :

a)   ad ogni passo successivo, inoltra il messaggio al vicino il cui ID è più vicino a k; b)  quando non esiste un vicino con queste caratteristiche, allora si è giunti al nodo

effettivamente più vicino, il quale deve essere il proprietario di k. Questo tipo di routing viene talvolta definito come key based routing.

Al di là della correttezza di fondo di questo tipo di routine, vi sono due vincoli chiave nella

topologia: - che il numero massimo di passi successivi in un qualsiasi percorso (dilazione) sia basso,

in modo tale che la richiesta sia soddisfatta velocemente, e - che il numero massimo di vicini di ciascun nodo (il grado del nodo) sia basso, al fine di

mantenere basso l’overhead di mantenimento.

Rete Overlay con DHT (3)

L’overlay network connette i nodi, consentendo loro di trovare il proprietario di una determinata chiave nel keyspace della DHT.

Modelli non strutturati per la diffusione dei dati

Algoritmi epidemici E’ una tecnica (utilizzata nei sistemi distribuiti a larga scala) basata su un modello di propagazione dei dati che consiste nel diffondere le informazioni su un host (scelto a caso e detto “infetto”) che provvede a sua volta a diffondere l’informazione sugli host con cui è collegato. Il nodo che non ha ancora ricevuto i dati è detto “suscettibile”. Un nodo che ha già ricevuto i dati o non può diffonderli è detto “rimosso”.

Modello anti-entropia Modello gossiping

Un nodo sceglie a caso un altro nodo al quale inviare i dati (aggiornamenti) con uno dei seguenti approcci:

a)  PUSH = P (nodo infetto) invia solo i suoi aggiornamenti a Q (nodo suscettibile),

b)  PULL = P (suscettibile) accoglie solo i nuovi aggiornamenti da Q (infetto),

c)  PUSH/PULL = P e Q si mandano reciprocamente gli aggiornamenti (push-pull).

Se P è aggiornato con il dato x, prova ad inviare x ad un nodo arbitrario Q. Se Q ha già ricevuto x da un altro nodo, P perde l’interesse a diffondere ulteriormente x (viene rimosso). Tale tecnica non garantisce che tutti i nodi ricevano l’informazione, ma è molto efficiente nella propagazione del dato.

28/11/13

10

Concorrenza fra processi remoti

Interazioni fra processi remoti: 1.  Indesiderate e (spesso) impreviste

•  I processi competono per le risorse al fine di poter completare la propria esecuzione, causando condizioni di attesa ed eventualmente problemi quali blocco critico o starvation.

2.  Desiderate e previste

•  I processi cooperano al fine di giungere alla soluzione di un problema complesso

(Architetture client-server, in cui un processo richiede un servizio ad un altro e attende da esso la risposta)

Mutua esclusione distribuita

Nel caso di accesso simultaneo ad una risorsa, occorre garantirsi che tale accesso non corrompa la risorsa o la renda inconsistente.

ü  Quando si hanno processi concorrenti che accedono ad un risorsa condivisa nasce il bisogno di sincronizzarli in modo tale che tale risorsa sia assegnata ad un processo alla volta.

ü  Questo problema va sotto il nome di mutua esclusione. Dal punto di vista astratto il problema puo’ essere formulato come segue. Ci sono N processi ognuno dei quali ripete la seguente sequenza di passi di programma : •  <non in sezione critica> •  <trying protocol> •  sezione critica •  <exit protocol> •  <non in sezione critica> In un sistema concorrente esiste uno “scheduler” centralizzato che permette ad un solo processo alla volta di entrare in esecuzione e quindi di evolvere secondo il suo codice. Di fatto quindi lo scheduler esegue una linearizzazione di tutte le istruzioni elementari effettuate dai vari processi. CdL in Informatica- Magistrale Università di Bari

Sistemi Distribuiti -

Il modello di Dijkstra

28/11/13

11

Mutua esclusione distribuita

q  Soluzioni basate su autorizzazioni (un processo che intende usare la risorsa, prima richiede l’autorizzazione ad altri). ü Algoritmo centralizzato ü Algoritmo decentralizzato ü Algoritmo distribuito

In questa tipologia di algoritmi esistono diverse tecniche per coordinare la comunicazione : • quorum (o votazione): si richiede il permesso di accedere ad una risorsa condivisa ad un sottoinsieme di processi (algoritmo di Maekawa). • elezione: un processo si trasforma in coordinatore (l’algoritmo bully, algoritmo ad anello e super-peer )

q  Soluzioni basate su token (messaggio speciale tra processi che realizza la mutua esclusione, consentendo solo al processo detentore del token la possibilità di utilizzare la risorsa. (Algoritmo token ring)

Server che gestisce una mutua esclusione mediante token


Server

1. Requesttoken

Queue ofrequests

2. Releasetoken

3. Granttoken

4

2

p4

p3p

2

p1

28/11/13

12

Un anello di processi che si scambiano un token mutualmente esclusivo


pn

p2

p3

p4

Token

p1

a)  Un gruppo di processi non ordinati su una rete b)  Un anello logico costruito via software

Trasmissione del token sull’anello (logico) e suo possesso per poter utilizzare una risorsa

Algoritmo basato su autorizzazione


p5

p4

p2

p1

p0 p3

processo coodinatore

p2 p0 p5 p4 P1

a) richiesta

b) OK

c) rilascio

d) OK

d)

28/11/13

13

Mutua esclusione con autorizzazione: un algoritmo centralizzato

a)  Il processo 1 chiede al coordinatore il permesso per entrare in una regione critica. Il permesso è dato.

b)  Il processo 2 allora chiede il permesso di accedere alla stessa risorsa. Il coordinatore NON risponde.

c)  Quando il processo 1 esce dalla regione critica, lo dice al coordinatore che può finalmente rispondere al processo 2.

In totale 3 messaggi con 2 messaggi prima di poter usare una risorsa (ritardo). La soluzione centralizzata evita la starvation ma pone problemi sulla criticità del coordinatore.

Mutua esclusione con autorizzazione: Un algoritmo decentralizzato

La soluzione decentrata (basata su quorum) estende il numero dei coordinatori alle n duplicazioni delle risorse disponibili (Lin et al.2004 basato su DHT).

q  Si suppone che le risorse siano replicate n volte ed ogni replica ha il suo coordinatore.

q  Ciascun coordinatore controlla l’accesso ad ogni singola risorsa da parte di processi concorrenti.

q  La richiesta di una risorsa avviene come nell’algoritmo centralizzato. q  Un processo, per poter accedere ad una risorsa, dovrà ottenere un voto di

maggioranza da m > n/2 coordinatori. q  Quando un coordinatore vuole negare l’accesso ad un processo (perché lo ha

già dato ad un altro processo), deve comunicarlo al processo richiedente.

N. di messaggi necessari = 3mk (k=1,2,3,…tentativi) e ritardo pari a 2m

E’ ridotto al minimo il problema del crash del coordinatore, ma è possibile una starvation quando un processo non riesce ad ottenere mai la maggioranza.

28/11/13

14

Mutua esclusione con autorizzazione: Algoritmo decentralizzato

0 5 6

Processi che chiedono la risorsa 9

request replay

Mutua esclusione con autorizzazione: un algoritmo distribuito

a)  2 processi (0 e 2) vogliono entrare nella stessa regione critica nello stesso momento. b)  Il processo 0 ha il timestamp (8) più basso, perciò vince. c)  Quando il processo 0 finisce, invia un OK, in modo che il processo 2 possa entrare

nella regione critica.

N messaggi = 3(n-1), ritardo = 2(n-1) CdL in Informatica- Magistrale Università di Bari

Sistemi Distribuiti

L’algoritmo di Lamport 1978 richiede che tutti gli eventi dispongano di un clock logico di sincronizzazione scalare e che ciascun processo gestisca una coda di richieste di accesso ad una regione critica. L’ algoritmo di Ricart e Agrawala (1981) richiede che ci sia un ordinamento totale di tutti gli eventi del sistema basato sui timestamp di Lamport. Quando un processo vuole accedere ad una risorsa, costruisce un messaggio contenente il nome della risorsa richiesta, il numero del processo richiedente (0,1,2) e il suo timestamp corrente. Il messaggio viene inviato a tutti i processi (compreso se stesso). L’accesso alla regione critica è consentita solo al processo in coda con timestamp minore.

28/11/13

15

Algoritmo di Ricart e Agrawala (1981)


On initialization state := RELEASED;

To enter the section state := WANTED; Multicast request to all processes; request processing deferred here T := request’s timestamp; Wait until (number of replies received = (N – 1)); state := HELD;

On receipt of a request <Ti, pi> at pj (i ≠ j) if (state = HELD or (state = WANTED and (T, pj) < (Ti, pi))) then queue request from pi without replying; else reply immediately to pi; end if

To exit the critical section state := RELEASED; reply to any queued requests;

•  Il processo che vuole accedere ad una sezione critica manda un messaggio di richiesta a tutti, incluso se stesso, contenente: il nome della sezione critica, il proprio identificatore ed il timestamp locale e si pone in attesa della risposta da tutti.

•  Ottenuti tutti gli OK, entra nella sezione critica ed all’uscita da essa manda OK a tutti i processi in coda.

•  Il processo che riceve può non essere nella sezione critica e non vuole accedervi, pertanto manda OK al mittente; oppure si trova nella sezione critica e non risponde mettendo in coda locale il messaggio.

•  Per poter accedere alla sezione critica confronta il timestamp e vince se possiede quello più basso.

•  Quindi se il processo che possiede il timestamp più basso è un altro allora invia OK, altrimenti non risponde e pone il messaggio in coda.

Algoritmo di Ricart e Agrawala (1981)

28/11/13

16

Esempio di algoritmo distribuito di Ricart e Agrawala

Confronto tra i metodi


Algorithm Messages per entry/exit

Delay before entry (in message times)

Problems

Centralized 3 2 Coordinator crash

Distributed 2 ( n – 1 ) 2 ( n – 1 ) Crash of any process

Token ring 1 to ∞ 0 to n – 1 Lost token, process crash

Decentralized 3mk (k=1,2,3,…) 2m Starvation, lower efficiency

n = numero di processi m= numero di coordinatori k= tentativi di trasmissione

28/11/13

17

Algoritmi di elezione del coordinatore

L’elezione serve per scegliere il processo che dovrà agire da coordinatore (o da iniziatore) e su cui concordano tutti gli altri.

  Algoritmo “bully” (Gracia-Molina 1982)   Algoritmo ad anello   Elezione in ambienti mobili


Elezione del coordinatore: algoritmo Bully

Supponiamo che un qualunque processo pi invii una richiesta al coordinatore. Se dopo un tempo T la richiesta non è ancora stata soddisfatta, pi suppone che il coordinatore sia fallito, perciò indice l'elezione : a)  pi invia un messaggio di elezione a tutti i processi con maggior numero di

priorità; pi aspetta un tempo T per avere risposta; b)  se non arrivano risposte nel tempo T, pi suppone che tutti i processi (con

priorità maggiore della sua) siano falliti. Perciò pi si nomina nuovo coordinatore e avvisa tutti i processi della rete del cambiamento avvenuto. La coda e le richieste precedenti sono perse;

c)  se riceve almeno una risposta entro il tempo T, il suo ruolo nell'elezione è terminato.

In qualunque momento, un processo può ricevere un messaggio di tipo ELEZIONE da uno dei suoi colleghi con numero più basso. All’arrivo di tale messaggio, il destinatario ri-sponde con un messaggio di tipo OK al mittente, per indicare che è attivo e prende il con-trollo. Il destinatario organizza un’elezione, a meno che non lo stia già facendo. Alla fine tutti i processi rinunceranno tranne uno che sarà il nuovo coordinatore. Esso annuncia la sua vittoria inviando a tutti i processi un messaggio, comunicando loro che è il nuovo coordinatore con decorrenza immediata.

28/11/13

18

elezione del coordinatore: Bully Algorithm

a)  Il processo 4 indice una Elezione tra i processi 5, 6, 7 (con identificativo maggiore) ,

b)  I processi 5 e 6 rispondono con OK, spingendo 4 a fermarsi c)  5 e 6 indicono una nuova Elezione CdL in Informatica- Magistrale Università di Bari

Sistemi Distribuiti

Elezione del coordinatore: Algoritmo ad anello (1)

ü  Processi ordinati in maniera logica; ü  Il processo che intende incominciare una

elezione invia un messaggio col proprio identificativo lungo l’anello;

ü  Il processo con l’identificativo più alto vince.

28/11/13

19

Elezione del coordinatore: Ring Algorithm (2)

  Election algorithm using a ring.


Esempio di MANET

Università di Bari Aldo Moro -

28/11/13

20

Elezione del coordinatore in ambienti wireless

Reti mobili ad hoc Si costruisce un albero per l’elezione del nodo coordinatore, partendo dalla topologia iniziale

della rete. u  Un nodo qualsiasi può iniziare una elezione inviando un messaggio di elezione ai vicini, u  Quando un nodo riceve per la prima volta un messaggio di elezione, nomina il padre

come mittente ed invia il messaggio di elezione ai vicini, escluso il padre. u  Quando un nodo riceve un messaggio di elezione da un nodo che non sia il padre,

semplicemente invia un messaggio di avvenuta ricezione.

Nel contesto delle reti mobili (ad hoc), il problema classico dell’elezione del coordinatore richiede due importanti requisiti aggiuntivi: • l’elezione deve tollerare cambiamenti topologici arbitrari e concorrenti e terminare eleggendo un coordinatore unico; • il coodinatore eletto dovrebbe essere il “most-valued” fra tutti i nodi all'interno del sistema, dove il valore di un nodo è determinato da caratteristiche come la carica residua della batteria, la distanza media minima con gli altri nodi, le capacità di calcolo, ecc.

Assunzioni algoritmo

  La rete ad hoc è modellata come un grafo non orientato che cambia nel tempo, quando i nodi si spostano.

  Il grafo può diventare disconnesso se la rete si divide a causa di un movimento di nodo.

  Sono necessarie le seguente assunzioni sui nodi e architeIura di sistema:   Valore del nodo: valore di " desiderabilità" come coordinatore della rete;   ID nodo univoco: gli ID devono essere ordinabili in modo da risolvere il

problema di scelta   Collegamen4: i collegamenO sono bidirezionali;   Comportamento nodo: ogni nodo mobile può portare modifiche della

topologia di rete;   Comunicazione da nodo a nodo: la comunicazione è garanOta solo

quando il miIente e il desOnatario rimangono collegaO per tuIa la durata del trasferimento del messaggio.

Algoritmo di Vasudevan(2004)

Tratto da :Paolo Tomeo e Vito Rocco Albano:Algoritmo di elezione del coordinatore nei sistemi distribuiti mobile. Seminario Sis.Dis 2011-12

28/11/13

21

L'algoritmo uOlizza tre Opi di messaggi:   Elezione: uOlizzato per la fase di "crescita" dello spanning tree. Il nodo

sorgente invia un messaggio ELEZIONE a tuV i suoi vicini che a loro volta trasmeIono ai loro vicini e cosi via.

  Ack: uOlizzato per la fase "restringimento" dello spanning tree. ConOene un idenOficatore (ID) e il relaOvo valore. Ogni nodo padre confronta i messaggi ACK ricevuO, scegliendo l'idenOficatore del nodo con il valore più alto, e resOtuisce al suo nodo padre un messaggio. Il nodo sorgente ha infine informazioni sufficienO per determinare il nodo col maggior valore di tuIa la rete.

  Leader. Una volta che il nodo sorgente determina l’idenOtà del coordinatore dai messaggi ACK ricevuO, trasmeIe un messaggio LEADER a tuV i nodi contenente tale idenOtà.

Algoritmo di Vasudevan(2004)

Tratto da :Paolo Tomeo e Vito Rocco Albano:Algoritmo di elezione del coordinatore nei sistemi distribuiti mobile. Seminario Sis.Dis 2011-12

Esempio: Algoritmo di Vasudevan

Universita' degli Studi di Bari Aldo Moro - CdL …disys/sidys7concorrenza.pdfModelli non...

Documents

Transcript of Universita' degli Studi di Bari Aldo Moro - CdL …disys/sidys7concorrenza.pdfModelli non...