time and synchronisation

dsa621s - 2021
back to processes
• process action: local instruction or communication

• action leads to state change

• process has local clock

• events within a process can be assigned a timestamp

3
• in what order were replicas copied on di erent nodes?

4
ff
• process clock can be di erent

• algorithms

• time synchronisation

• happened before

5
ff
synchronising physical clocks
 mr
P S

mt

7
 cristian’s algorithm (1)

• time server keeps reference time

• client sends a request about time

• client adjusts time based on received message

8
 cristian’s algorithm (2)

• round-trip time

• response reception time - message send time

• rtt could be wrong

• when was the time added to the message?

9
 cristian’s algorithm (3)

• min = min value of client-server one-way transmission

• client adjusts time between t+min and t+rtt-min

10
 berkeley algorithm (1)

• uses elected master process to synchronise among slaves

11
 berkeley algorithm (2)

• master

• broadcasts to all clients requesting their time

• adjusts time with rtt and latency

• averages time and indicates to each process how to adjust their time

12
 berkeley algorithm (3)

• how to circumvent single point of failure (master)?

13
 network time protocol (1)

• network of time servers to synchronise processes

• subnet tree

• root connected to utc

• each node synchronises with its children

14
logical clocks
• happens before between events

• time at each process is well de ned

16
fi
 →ı ′
𝖾
𝖾

17
 rules

• local ordering

• happens before

• message exchange

• send before receive

• transitivity

18
 concurrency

• some events might be unrelated (partial order)

• concurrent events

19
 Lamport logical clock

• Lamport’s clock assigns timestamp to events following happens before

ordering

20
 Lamport logical clock

• algorithm

• increment timestamp before each event

• add timestamp when sending messages

• increment when receiving a message (max(local, new message))

21
 example
1 2 3 4 6 8
P1 a b c d e f

1 4 6 7
P2 g h i 5 j k

3 4 5
6
P3 l m n o

1 6 8
7
P4 p q r s

22
 vector clock

• vector of clocks for events and processes

• similar rules with focus on vector’s dimension

23
 example
[1000] [2000] [3000] [4001] [5301] [6333]
P1 e
0
e
1
e
2
e
3
e
4
e
5

[0100] [3200] [3400] [3520]

P2 i i i [3300] i i
0 1 2 3 4

[2010] [2020] [2030]

j j [2040]
P3 0 1 j
2 j
3

[0001] [2032] [2044]

[2033]
P4 l
0
l
1 l
2
l
3

24
global state
 detecting global properties

• garbage collection

• termination

• deadlock

26
 global state

• states of all processes + state of communication channels

27
• how to construct a global state?

28
• synchronise clocks of all processes

• ask all processes to record their state at time t

29
• however

• clock synchronisation only works approximately

• channel states not recorded

30
• actually only causality is needed

31
• solution

• cut: time frontier, one at each process

32
Cuts
0" e1 2"
e1 e11" e1 3"

P1"
e2 1"

P2" 0" e2 2"

e2

P3" e3 0" e3 1" 2"

Consistent e 3

Inconsistent cut! cut!

! Cut = time frontier, one at each process

33
• cut is consistent is causality is included

• global state is consistent is corresponds to consistent cut

• consistent cut is a global snapshot

34
 snapshot algorithm (1)

• objective

• record a set of process and channel states

• achieve a global snapshot/consistent cut

35
 snapshot algorithm (2)
• assumptions

• unidirectional communication channel between each ordered pair of

processes

• communication channels are fo

• no failure, all messages arrive

• any process may initiate the snapshot

36
fi
 snapshot algorithm (3)

• principle

• snapshot does not require applications to stop

• each process is able to record its state and the state of its incoming
channels

37
 snapshot algorithm (4)
• algorithm

• after a process has recorded its state, it sends a marker message on

each outgoing channel

• after receiving a marker message on channel c

• process records its own state (if it has not recorded its state yet)

• record the state of c as empty

38
 snapshot algorithm (5)

• algorithm

• after receiving a marker message on channel c

• sends a marker message on each outgoing channel

• turn on recording of messages on each incoming channel

39
 snapshot algorithm (6)
• algorithm

• after receiving a marker message on channel c

• if process has already recorded its state

• records the state of c as all the messages received since it

recorded its state

• stops recording state of c

40
in short…
• physical clock synchronisation

• logical clocks

• global state

42