Algoritmo di Berkeley

Questa voce o sezione sull'argomento teorie dell'informatica non cita le fonti necessarie o quelle presenti sono insufficienti.

---

Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti.

Questa voce o sezione sull'argomento informatica non è ancora formattata secondo gli standard.

---

Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento.

L'algoritmo di Berkeley è un metodo di sincronizzazione del clock negli algoritmi distribuiti in cui si assume che le macchine non abbiano una fonte accurata da cui ricevere il tempo. L'algoritmo è stato realizzato da Gusella e Zatti presso l'Università di Berkeley nel 1989.

Al contrario dell'algoritmo di Cristian, in questo processo è presente un master che periodicamente fa delle richieste ad altri nodi della rete che si comportano da slave.

Il processo segue i seguenti passi:

1. un master viene eletto tramite un algoritmo di elezione come quello di Chang e Robert
2. il master chiede agli slave di inviargli i propri timestamp similarmente a come avviene nell'algoritmo di Cristian
3. il master quindi, tenendo conto dell'RTT, calcola la differenza (positiva o negativa) che intercorre tra il proprio tempo e quello dei vari slave che hanno risposto
4. il master quindi esegue una media delle differenze calcolate
5. ad ogni slave, il master, invia la differenza tra il tempo ricevuto dello slave e la media appena calcolata. In questo modo ogni slave sa di quanto tempo (positivo o negativo) deve aggiustare il proprio timer

L'utilizzo di questo sistema di calcolo della media evita ai vari slave di utilizzare tempi che nel tempo possono divergere tra loro. Si noti che contrariamente al funzionamento di questo algoritmo, i computer, normalmente, si rifiuterebbero di aggiornare il proprio timer con un tempo negativo a quello già passato.

L'utilizzo di questo algoritmo potrebbe creare problemi a processi presenti sul sistema che invece assumono che, per definizione, il tempo sia continuo e strettamente monotono crescente (ad esempio il comando make)

Una prima e semplice soluzione a tale problema potrebbe essere quella di fermare temporaneamente il clock che tuttavia, porterebbe ad altri problemi.

Per correzioni minori, molti sistemi rallentano il clock (aka "clock slew"). Spesso il master ignora quei tempi che gli vengono inviati dagli slave se sono troppo distanti dalla media generata: in questo modo si previene un drastico cambiamento dei timer nella rete dovuto ad errori presenti in alcuni degli slave.

Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica