Algoritmo dello spaccone: differenze tra le versioni

Versione delle 09:55, 15 giu 2006

Versione attuale delle 17:46, 16 feb 2019

(21 versioni intermedie di 18 utenti non mostrate)

Riga 1:

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

Nel [[calcolo distruibitodistribuito]], l'<i>'''algoritmo dello spaccone</i>''' (''bully'') è un [[algoritmo]] [[algoritmo di elezione|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 scopre che l'attuale coordinatore non reagisce più a causa di tempi di risposta lunghi o problemi hardware, esegue la seguente serie di azioni:

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

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

# se invece riceve una risposta da uno di questi processi, 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).

Line 9 ⟶ 12:

Se 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.

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

[[Categoria:Sistemi operativi]]

== Altri progetti ==

{{interprogetto}}

[[Categoria:Calcolo distribuito]]

[[Categoria:Sistemi operativiAlgoritmi|Spaccone]]

{{Portale|informatica}}

[[en:Bully algorithm]]