Algoritmo dello spaccone

Nel calcolo distribuito, l'algoritmo dello spaccone (bully) è un algoritmo di elezione di un coordinatore all'interno di un pool di 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:

1. manda un messaggio di elezione a tutti gli altri processi con un identificatore (ID) più alto del suo;
2. se non riceve nessuna risposta da questi processi, si autoelegge come coordinatore;
3. 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).

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 $n^{2}$ (quindi di complessità $O(n^{2})$).

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file su algoritmo dello spaccone