Come ribadito nell’articolo di introduzione ai sistemi distribuiti, essi sono sistemi che consistono in una collezione di macchine che cooperano al fine del raggiungimento di un obiettivo comune.

Un sistema distribuito, ha innumerevoli vantaggi rispetto ad un sistema centralizzato in quanto evita colli di bottiglia per elevate richieste al server ed è molto più robusto, quindi, tollerante ai guasti in quanto i dati e le operazioni sono affidati a più nodi della rete che possono essere macchine eterogenee (sia nell’hardware che nel software).

Il problema della sincronizzazione dei processi distribuiti

Tutto ciò, introduce una delle problematiche più discusse dei sistemi distribuiti: la sincronizzazione. In quanto sistemi di macchine eterogenee non è possibile avere un clock globale per tutte le macchine in modo da avere un unico riferimento temporale per sincronizzare tutti i processi distribuiti e coordinare in egual modo le operazioni.

Quindi, è impossibile ordinare tutti gli eventi che occorrono all’interno del sistema. Questo problema non persiste nei sistemi centralizzati perchè in quel caso il clock è unico e non vi è una misura del tempo ambigua.

Ci sono due soluzioni per risolvere il problema della sincronizzazione dei processi nei sistemi distribuiti:

  • sincronizzazione dei clock (algoritmi che si basano sui clock fisici);
  • generazione di clock logici (algoritmi che costruisce un clock logico indipendente da quello fisico).

Sincronizzazione dei clock

Per quanto riguarda la soluzione di sincronizzazione dei clock che si basa sull’hardware di ogni macchina del sistema distribuito, i due algoritmi con funzionamento quasi simile sono l’algoritmo di Cristian e l’algoritmo di Berkeley.

Algoritmo di Cristian

Alla base di questo algoritmo vi è un time server che restituisce il tempo periodicamente (al client) alle macchine del sistema distribuito che ne fanno richiesta (il funzionamento è quello del classico modello client/server).

Però bisogna considerare la latenza di risposta del server, ovvero il tempo che intercorre tra quando il server risponde a quando questa effettivamente arriva al client.

La latenza si calcola come RTT/2, dove con RTT (Round Trip Time) si intende il tempo di andata e ritorno, ovvero che intercorre dall’invio della richiesta all’istante in cui viene ricevuto l’output. Viene diviso per 2 in quanto si presume che il tempo di andata e ritorno sia identico tra la richiesta e la risposta e a noi interessa solo metà di questo periodo temporale, in particolare la seconda metà dal server al client.

In sintesi, l’algoritmo funziona nel seguente modo, tra un processo P e un time server S:

  • P chiede il tempo a S;
  • S prepara la risposta e vi aggiunge l’ora T del proprio orologio;
  • P imposta il suo orologio come T + RTT/2.

I problemi dell’algoritmo di Cristian sono i seguenti:

  • bisogna considerare la latenza di risposta dal time server;
  • il tempo dei client non deve mai scorrere all’indietro, piuttosto se il loro tempo è più avanti rispetto a quello restituito dal server devono rallentare il proprio clock fino ad allinearlo a quello del server. Altrimenti il tempo può essere aggiornato.

Algoritmo di Berkeley

Il funzionamento di questo algoritmo è molto simile a quello di Cristian, la differenza è la mancanza di un server che restituisce il proprio tempo. Piuttosto, esiste nella rete un nodo che riceve il tempo da tutti gli altri, effettua la media di questi tempi e li restituisce a tutti gli altri in modo tale da sincronizzarsi totalmente.

Di fatto:

  • Il server, periodicamente, chiede il clock dei vari nodi, calcola il valore medio e lo invia a tutte le macchine, che potranno aggiornare il clock con il valore ricevuto.

Anche qui, come nell’algoritmo di Cristian vi è il problema della latenza dell’invio della marca temporale e il problema che i clock non possono tornare indietro.

Generazione di clock logici

La generazione di clock logici è la soluzione proposta dall’informatico esperto di sistemi distribuiti Leslie Lamport, il quale affermò che:

  • se due processi non interagiscono tra di loro, non vi è alcun bisogno di sincronizzare i loro clock;
  • se due processi interagiscono tra di loro, vi è la necessità di rispettare l’ordine corretto in cui gli eventi realmente avvengono.

I clock logici sono utilizzati per avere un valore del tempo consistente per tutti i nodi del sistema distribuito, ma questo non deve essere necessariamente il valore del tempo reale assoluto.

L’idea è quella di mantenere un ordine tra gli eventi del sistema, quindi si definisce un clock logico (potenzialmente diverso da quello logico) al quale tutti i nodi della rete devono fare riferimento.

Per ottenere ciò, Lamport, con la notazione “→”, definisce la relazione happened before tra due eventi A e B, indicata nel seguente modo:

  1. se A e B sono eventi dello stesso processo, con A → B si indica che l’evento A precede B nell’ordine;
  2. se A e B sono eventi di due processi diversi che non interagiscono, il loro ordinamento non ci interessa;
  3. se A e B sono eventi di due processi diversi che interagiscono, se A è l’invio di un messaggio e B è l’operazione di ricezione, allora A → B è vera.

In merito all’ultimo caso è necessaria una misura globale del tempo (C) da assegnare agli eventi e che abbia valore per tutti i nodi del sistema distribuito.

Quindi, se A → B ⇒ C(A) < C(B), l’ordinamento totale degli eventi (total ordering) avviene se:

  • ogni messaggio contiene il tempo dell’invio sul mittente;
  • quando il messaggio arriva, il clock del ricevente deve essere maggiore di almeno un tick rispetto alla marca che contrassegna il messaggio. Se così non fosse, deve aumentare di un tick il suo orologio perchè la ricezione non può essere antecedente all’invio;
  • tra due eventi di clock deve avanzare almeno un tick.

A questo punto ecco l’algoritmo di Lamport per la sincronizzazione dei processi tramite clock logici:

Var Cp: integer;
Cp = 0;
if (A è un evento interno){
Cp = Cp+1;
}
if (A è l’invio di un messaggio){
Cp = Cp+1;
send(msg, Cp);
}
if (A è la ricezione di un messaggio){
receive(msg, Cr);
Cp = max(Cp, Cr)+1;
}