LU4 Time and Global State

Question 1

What are the four sections covered on the lecture slides?

Answer 1

Foundation

Question 2

What does the “Foundation” section include?

Answer 2

Characterization of Distributed System

Question 3

What does the “Middleware” section include?

Answer 3

Distributed Object

Question 4

What does the “Support Systems” section include?

Answer 4

Operating Systems

Question 5

What does the “Algorithms & Shared Data” section include?

Answer 5

Coordination Agreement

Question 6

Why is time an important issue in distributed systems?

Answer 6

To measure the happening of a certain event accurately (for example, e-commerce transactions).

Question 7

How do timestamps help in distributed systems?

Answer 7

To serialize transactions and maintain data consistency (establishing order of events).

Question 8

How do distributed systems handle the absence of a global clock?

Answer 8

By coordinating actions through message passing (programs coordinate their actions by exchanging messages).”

Question 9

What are the two types of clocks in distributed systems?

Answer 9

Physical clocks (count seconds elapsed) and Logical clocks (count events).

Question 10

Why is a simple oscillator not sufficient as a clock in a distributed system?

Answer 10

Digital electronics are not the accurate enough for time stamp use in distributed systems

Question 11

What is clock drift?

Answer 11

The rate at which a clock deviates from an ideal clock (quartz clocks are susceptible to drift).

Question 12

What unit is clock drift typically measured in?

Answer 12

Parts per million (ppm).

Question 13

What is an atomic clock?

Answer 13

A very accurate type of clock based on atomic resonances (Caesium-133 is often used).

Question 14

Describe the usage of GPS for time synchronization.

Answer 14

GPS satellites broadcast current time and location; receivers calculate position based on signal delay.

Question 15

What is UTC?

Answer 15

Coordinated Universal Time (compromise between GMT and TAI, accounting for the Earth’s rotation).

Question 16

Why is Greenwich Mean Time (GMT) not sufficient for accurate timekeeping?

Answer 16

It’s based on solar time, which varies due to irregularities in the Earth’s rotation.

Question 17

What is TAI?

Answer 17

International Atomic Time (based on the resonant frequency of Caesium-133).

Question 18

Why isn’t TAI used directly as a universal time standard?

Answer 18

It doesn’t account for the slowing and variation of the Earth’s rotation (Earth’s rotation is not constant).

Question 19

What are leap seconds

Answer 19

and why are they necessary?

Question 20

When are leap seconds typically added?

Answer 20

June 30th and December 31st at 23:59:59 UTC.

Question 21

What are three ways one can be affected by leap seconds?

Answer 21

The clock immediately jumps forward, moves to 00:00:00 after one second, or the clock moves to 23:59:60

Question 22

What are the common methods that are used to represent timestamps in distributed systems?

Answer 22

Unix time (seconds since epoch) and ISO 8601 (human-readable format).

Question 23

How is leap second traditionally handled in software systems?

Answer 23

They are often ignored due to the complexity they introduce.

Question 24

How does the ‘smear’ approach deal with leap seconds?

Answer 24

It spreads the extra second over a longer period, avoiding sudden jumps.

Question 25

What is clock skew?

Answer 25

The difference between two clocks at a particular point in time.

Question 26

How do you fix Clock Skew?

Answer 26

By periodically getting the current time from a accurate server (atomic clock or GPS receiver)

Question 27

What are the common protocols used for clock synchronization?

Answer 27

NTP (Network Time Protocol) and PTP (Precision Time Protocol).

Question 28

What is external synchronization?

Answer 28

Synchronizing clocks to a common standard (e.g., UTC).

Question 29

What is internal synchronization?

Answer 29

Synchronizing clocks with each other to a known degree of accuracy (clocks agree within a bound).

Question 30

In a synchronous system

Answer 30

what is the source of timing error?

Question 31

What does the Ttrans represent?

Answer 31

Transmission delay

Question 32

Is accuracy important in internal synchronization?

Answer 32

No

Question 33

What is a limitation of Cristian's method?

Answer 33

Single point of failure

Question 34

What is the recommendation in a case of a failing Cristian's Method?

Answer 34

To Multicast request to more servers

Question 35

What is the function of the Berkeley Algorithm?

Answer 35

Master computer periodically polls slave computers and takes a fault-tolerant average, adjusting the clocks accordingly.

Question 36

Why is fault-tolerant average used?

Answer 36

To eliminate readings from faulty clocks (which would skew a regular average).

Question 37

What problem does the Network Time Protocol (NTP) address?

Answer 37

Distributing time information over the Internet

Question 38

Does NTP provide a service to external Intranets?

Answer 38

No

Question 39

What is stratum in NTP?

Answer 39

Indicates hierarchy (layer) of clock servers (Stratum 0 is atomic clock, higher stratum is syncing with the lower).

Question 40

Why does NTP employs statistics in its procedures?

Answer 40

Filters and discriminates between the quality of timing data from different servers

Question 41

In NTP

Answer 41

how do clients compensate with the rate of drift?

Question 42

What are three possible modes NTP can be in?

Answer 42

Multicast mode

Question 43

Which model does NTP operate most accurately?

Answer 43

Symmetric mode

Question 44

In the Estimating time over a network model

Answer 44

what is the difference between T' and T?

Question 45

What is the solution given if |Θ| >= 1

Answer 45

000s?

Question 46

What is the purpose of Monotonic Clocks?

Answer 46

Measure elapsed time

Question 47

Monotonic Clocks are not subject to X

Answer 47

what is X?

Question 48

Give 3 reasons to why Monotonic Clocks are ideal for measuring time on a single node.

Answer 48

Always moves forwards at near-constant rate, measures elapsed time, can use System.nanoTime()

Question 49

Which are two Time-of-day-clocks?

Answer 49

System.currentTimeMillis() and clock_gettime(CLOCK_REALTIME)

Question 50

Which part of physics does Causality come from?

Answer 50

Relativity

Question 51

True or False: When a || b

Answer 51

we know that a cannot have caused b.

Question 52

True or False: Happens-before relation encodes potential causality.

Answer 52

True

Question 53

What must be true for < to be a casual order?

Answer 53

(a → b) ⇒ (a < b)

Question 54

How are you able to tell whether (a -> b) and or a || b?

Answer 54

Vector Clock

Question 55

What does e stand for when trying to define a Vector Timestamp of an event?

Answer 55

event

Question 56

Why is the vector clock needed?

Answer 56

To identify what events are concurrent (events that are not casually related).

Question 57

What is the purpose of Logical Clocks

Answer 57

which is a common alternative to physical clocks?

Question 58

What must be used to use the Lamport Clock?

Answer 58

software counter

Question 59

After applying the Lamport clock

Answer 59

it still might not imply that the sequence is correct

Question 60

How does Lamport’s logical clock work?

Answer 60

Each process increments a counter for local events and updates it based on received messages (monotonically increasing).

Question 61

What is the vector time stamp of an event?

Answer 61

V(a) =

Question 62

Why does each process keep its own logical clock?

Answer 62

To timestamp its events and track the order of events locally.

Question 63

Why are vector clocks needed when comparing timestamps of events?

Answer 63

Because vector clocks helps find if they're not causally related (to determine concurrency).

Question 64

In Lamport Clocks

Answer 64

what does it mean to have (a -> b)

Question 65

If the pair of (L(e)

Answer 65

N(e)) identify a uniquely event e. Which two do L and N represent?

Question 66

Does Lamport Clocks's guarantee events can guarantee the the e can causally proceeded e'?

Answer 66

no

Question 67

What is the recommendation when dealing with Lamport's clocks when you don't know to solve this problem?

Answer 67

using Vector Clocks

Question 68

Can you guarantee that if a -> b then L(a) < L(b) in Lamport clock?

Answer 68

Yes

Question 69

True or False: The main goal for Logical Clocks is that each process observes them in the same order.

Answer 69

False, the physical order in which each process observers the events.

Question 70

Describe "FIFO broadcast"

Answer 70

If process A sends message m1 before message m2 to process B, then B must receive m1 before m2

Question 71

Describe "Causal Broadcast"

Answer 71

If send(m1) -> send(m2) then deliver(m1) -> deliver(m2)

Question 72

Describe "Total order broadcast"

Answer 72

If process A delivers message m before message n, then all processes must deliver message m before message n

Question 73

What is the hierarchy of the four Broadcast formats?

Answer 73

Best-effort Broadcast, Reliable Broadcast, FIFO Broadcast, Causal Broadcast and then Total order broadcast

Question 74

In FIFO broadcast

Answer 74

If messages are sent by the same node must it be in delivery order?

Question 75

In FIFO broadcast

Answer 75

If messages are sent by different nodes must it be in delivery order?

Question 76

In a total order broadcast

Answer 76

must all nodes follow the same delivery order?

Question 77

What are the two Layers that Broadcast algorithms can be broken down into?

Answer 77

best-effort and reliable

Question 78

With Reliable broadcast algorithm

Answer 78

what is used on First attempt?

Question 79

In Reliable broadcast algorithm

Answer 79

when directly sending

Question 80

What is the term for idea the first time that that node may receive

Answer 80

a message that will re-broadcast

Question 81

In summary

Answer 81

what are two methods used to reach reliability in Broadcasts?

Question 82

What is 'Gossip Protocols' used for?

Answer 82

large number of nodes

Question 83

How many nodes are forwarded with Gossip protocols?

Answer 83

3

Question 84

What does a "cut" represent?

Answer 84

A moment in a distributed system.

Question 85

What does the set of last events from all process called?

Answer 85

Frontier of the cut

Question 86

When is a cut considered to be "Inconsistent" in a process?

Answer 86

The process has received one message, but not sent any messages, there is an effect but not cause

Question 87

When is the "Global state predicate" set as "True"?

Answer 87

when is object stable and it's either deadlocked, terminated or garbage

Question 88

True or False: Channels must be in a process where Snapshot Algorithm will not be utilized.

Answer 88

False

Question 89

True or False: Processes must continue working on a process where Snapshot Algorithm will not be utilized.

Answer 89

False

Question 90

Does Chandy and Lamport's 'snapshot' algorithm give method gathering to a global state?

Answer 90

no

Question 91

What is the advantage of Monotonic Clocks?

Answer 91

Always moves forward, good for measuring times in a single node.

Question 92

What should a client monitor to ensure its clock is in sync?

Answer 92

Clock skew (the difference from an authoritative time source).