make depends on time.
In order to synchronize UTC time, precision and accuracy are very import but the cost is expensive.

How much synchronize and how frequecncy check you should make decision.

Every machine has its own quatrz crystal, so we need NTP ()

You can get UTC time by three popular approches, through RPC call ask UTC server, through radio box, through satellite of standard US.

Keeping time with UTC server

Client A records sending UTC request time to UTC server B about T_1, server B sends the recieve request time T_2; Sever B sends response time T_3, client A records recieve response time T_4. Then we know the time difference (T_2-T_1) and (T_4-T_3). Client computes the avarage delay time, then it adjusts its time caching up with UTC time.

If not initialize request to send to server, you’ll not get response.

Number of massages only to some client.

Broadcast algorithm without UTC

Using a time server to ask everyone the time on each machine, and compute the avarage time, send the time to everyone, to force every machine at the same time.

Never move your clock to backward, avoid sudden change otherwise may miss events, must adjust time smoothly.

Time server force all machines to send response and force every one have the same time as itself, and doesn’t care about true notion of time.

Number of massages, send to everyone and get reply from everyone. Load of massages is heavy.

Happened-before relationship without synchronization (lampor clock)

No need to synchronize time, we only need to agree event ordering without physical clock.

Partial event ordering, not care about all evens, only care about what we care, this is less expensive.

Transitivity derive: In centralize world, it is easy to know the event ordering. But in distributed system (many machines), we don’t know which one happen first. If machine A send b to machine c, then we know b happends before c.

2 rules:

  • LC1: Li is incremented before each event is issued at process Pi: Li=Li+1
  • LC2:
    • (a) when a process Pi sends a msg m, it piggybacks on m the value t=Li
    • (b) on receiving (m, t), Pj computes max(Li, t) and then applies LC1 before timestamping the event.

Process

  • Give every machine initial value, P1 (0), P2(0)
  • Give massage increase 1
  • Send it to the other machine P2, compare current time and massage time recieved, max(0, 2)=2, then increase the msg 2+1=3
  • Another msg happends after that on P2, then increase 1 to 4
  • P3 recieve the msg, max(0,4)=4, the current timestamp for the recieved msg is 5

    Vector clock

    multipel dimensions of clock, extention of lampor clock, order events across multipel processes。

On P1 (0,1,0), on P2 (1,1,0), compare them, if any dimension is bigger than anyone, other digits are equal, then indicades the timestamp is higher than the other one.

Reference material:
Book: Distributed Systems, Third edition, Version 3.02(2018), Maarten van Steen and Andrew S. Tanenbaum.
Lectures: University of Waterloo, CS 454/654 (Distributed System), 2020 winter term, Professor Khuzaima Daudjee.