Algoritmo dello spaccone: differenze tra le versioni

Versione delle 09:47, 15 giu 2006

Versione attuale delle 17:46, 16 feb 2019

(26 versioni intermedie di 19 utenti non mostrate)

Riga 1:

{{F|applicazioni dell'informatica|marzo 2013}}

L''''algoritmo dello spaccone''' è utilizzato nei sistemi distribuiti per l'elezione di un coordinatore.

Nel [[calcolo distribuito]], l''''algoritmo dello spaccone''' (''bully'') è un [[algoritmo di elezione]] di un [[coordinatore]] all'interno di un pool di [[processo (informatica)|processi]].

Questo algoritmo viene utilizzato nei sistemi in cui i processi si scambiano messaggi.

Quando un processo P scopre che l'attuale coordinatore non reagisce più a causa di tempi di risposta lunghi o problemi hardware, esegue la seguente serie di azioni:

Quando un processo P scopre che l'attuale coordinatore non reagisce più a causa di tempi di risposta lunghi o problemi hardware, esegue la seguente serie di azioni:

1. P# manda un messaggio di elezione a tutti gli altri processi con un [[identificatore]] (ID) più alto del suo;

2.# se P non riceve nessuna risposta da questi processi, si autoelegge come coordinatore;

3.# se invece P riceve una risposta da uno di questi processi, P attende un determinato lasso di tempo per permettere a quel processo di proclamarsi come coordinatore. Se non riceve il messaggio in tempo, rimanda il messaggio di elezione (punto 1).

Se P riceve un messaggio di elezione da un processo con ID più basso, manderà immediatamente un messaggio di elezione. Questa è l'origine del nome dell'algoritmo: un processo che ha un ID più alto si contenderà il posto del coordinatore con un processo con ID più basso.

2. se P non riceve nessuna risposta da questi processi, si autoelegge come coordinatore;

Il numero dei messaggi scambiati è proporzionale a <math>n^2</math> (quindi di [[Stima asintotica|complessità]] <math>O(n^2)</math>).

3. se invece P riceve una risposta da uno di questi processi, P attende un determinato lasso di tempo per permettere a quel processo di proclamarsi come coordinatore. Se non riceve il messaggio in tempo, rimanda il messaggio di elezione (punto 1).

== Altri progetti ==

{{interprogetto}}

Se P riceve un messaggio di elezione da un processo con ID più basso, manderà immediatamente un messaggio di elezione. Questa è l'origine del nome dell'algoritmo: un processo che ha un ID più alto si contenderà il posto del coordinatore con un processo con ID più basso.

[[Categoria:Sistemi operativi]]

[[Categoria:Calcolo distribuito]]

[[Categoria:Sistemi operativiAlgoritmi|Spaccone]]

{{Portale|informatica}}