Logical time and logical clocks

Question 1

Why is Logical time and logical clocks a necessity? (3 reasons)

Answer 1

From the point of view of any single process, events are ordered uniquely by times shown on the local clock.

♦ Cannot synchronise clocks perfectly across a distributed system

♦ Cannot use physical time to order any arbitrary pair of events occurring within it

Question 2

Define an event

Answer 2

the occurrence of a single action that a

process carries out as it executes

Question 3

How can process pi order it’s sequence of events?

Answer 3

The sequence of events with a process pi can be placed in a single total ordering, denoted by the relation →i

Question 4

Describe the scheme similar to physical causality used to order some of the events that occur at different processes (2 parts)

Answer 4

If two events occur at the same process pi(i=1, 2, …, N), then they occur at the order
→i (the order that the process observes them)

Whenever a message is sent between processes, the event of sending the message occurs
before the event of receiving the message

Question 5

Define the Happened-before relation

Answer 5

♦ HB1: if there exists a process pi: e →i e’  e → e’
♦ HB2: for any message m, send(m) → receive(m)
♦ HB3: if e, e’ and e” are events such that e → e’ and
e’ → e”, then e → e” (transitivity property)

Question 6

When are events not related by happened-before relation?

Answer 6

if events happening in different processes, and no chain of messages intervenes between them

Question 7

Define potential causality

Answer 7

If a → b, this does not mean that a (necessarily) caused b