8-timing-synchronisation

Question 1

List the 8 Fallacies of Distributed Computing.

Answer 1

1. Network reliable, 2. Latency zero, 3. Bandwidth infinite, 4. Network secure, 5. Topology constant, 6. One admin, 7. Transport free, 8. Network homogeneous.

Question 2

What is the 9th fallacy sometimes added?

Answer 2

All clocks are synchronised.

Question 3

Why do distributed systems need time?

Answer 3

Schedulers

Question 4

What are Physical clocks?

Answer 4

Count number of seconds elapsed.

Question 5

What are Logical clocks?

Answer 5

Count events (e.g. messages sent).

Question 6

Why is time difficult in DS?

Answer 6

No global agreement on time. Each machine has own clock running at slightly different rate.

Question 7

What is Clock Skew?

Answer 7

Different clocks running at slightly different rates in a distributed system.

Question 8

How do Quartz clocks work?

Answer 8

Crystal resonates at specific frequency via piezoelectric effect. Count cycles to measure time.

Question 9

What is clock drift measured in?

Answer 9

Parts per million (ppm). 1 ppm = 1 μs/sec = 86 ms/day = 32 s/year. Most computers within 50 ppm.

Question 10

What happens if two clocks drift opposite directions?

Answer 10

After time δt they may be 2ρδt apart (where ρ is max drift rate).

Question 11

What was TAI before 1958?

Answer 11

Time based on mean solar second: 1/86

Question 12

What is TAI (International Atomic Time)?

Answer 12

1 second = time for caesium-133 to make 9,192,631,770 electronic transitions.

Question 13

Why are leap seconds needed?

Answer 13

Mean solar day growing longer. Without them

Question 14

What is UTC?

Answer 14

Universal Coordinated Time - TAI corrected with leap seconds to match solar time.

Question 15

What is Unix time?

Answer 15

Seconds since 1 January 1970 00:00:00 UTC (the epoch)

Question 16

What is ISO 8601?

Answer 16

Date format: year

Question 17

How does most software deal with leap seconds?

Answer 17

Ignores them! Smearing spreads leap second over a day.

Question 18

When to use Cristian’s Algorithm?

Answer 18

One machine has UTC receiver - synchronise others with it.

Question 19

When to use Berkeley Algorithm?

Answer 19

No machines have UTC receivers - just minimise clock skew between them.

Question 20

What is the drift rate constraint for proper clock?

Answer 20

1 - ρ ≤ dC/dt ≤ 1 + ρ where ρ is max drift rate.

Question 21

How does Cristian’s Algorithm work?

Answer 21

Client asks UTC server for time, server responds. Client adjusts gradually to avoid time running backward.

Question 22

What is the formula for round-trip delay in Cristian’s?

Answer 22

δ = (t₄ - t₁) - (t₃ - t₂)

Question 23

What is estimated server time when client receives response?

Answer 23

t₃ + δ/2

Question 24

What is estimated clock skew in Cristian’s?

Answer 24

θ = t₃ + δ/2 - t₄ = (t₂ - t₁ + t₃ - t₄)/2

Question 25

How does Berkeley Algorithm work?

Answer 25

Time daemon asks all machines for clock values, calculates average, tells everyone how to adjust.

Question 26

What is the key difference between Cristian's and Berkeley?

Answer 26

Cristian's uses external UTC source. Berkeley uses average of all clocks (no external source).

Question 27

Why do we need election algorithms?

Answer 27

Many distributed algorithms need one coordinator. Need to pick one if coordinator fails.

Question 28

What are the assumptions of Bully Algorithm?

Answer 28

Each process has unique ID, processes know all IDs/addresses, communication reliable.

Question 29

What is the key idea of Bully Algorithm?

Answer 29

Select process with highest ID as coordinator.

Question 30

What are the 3 message types in Bully Algorithm?

Answer 30

Election, OK, I won.

Question 31

How does Bully Algorithm work?

Answer 31

P sends Election to higher IDs. If no OK received, P is coordinator and sends I won. If OK received, waits for I won.

Question 32

What happens when process receives Election?

Answer 32

Returns OK and starts its own election.

Question 33

What is the message complexity of Bully Algorithm?

Answer 33

O(n²) messages with n processes.

Question 34

What is NTP?

Answer 34

Network Time Protocol - enables Internet clients to synchronise to UTC reliably.

Question 35

What are the goals of NTP?

Answer 35

Synchronise to UTC, survive connectivity loss, authenticate timing data, resync frequently to offset drift.

Question 36

What is an NTP synchronisation subnet?

Answer 36

Hierarchical structure of time servers organised in strata.

Question 37

What is Stratum 1 in NTP?

Answer 37

Primary servers connected directly to UTC source (radio clock).

Question 38

What is Stratum 2 in NTP?

Answer 38

Secondary servers that synchronise with Stratum 1.

Question 39

What happens to accuracy in NTP strata?

Answer 39

Decreases as you go down through strata.

Question 40

How does NTP correct small clock skew (|θ| < 125ms)?

Answer 40

Slew - slightly speed up or slow down by up to 500 ppm.

Question 41

How does NTP correct medium clock skew (125ms ≤ |θ| < 1000ms)?

Answer 41

Step - reset client clock to estimated server timestamp.

Question 42

How does NTP handle large clock skew (|θ| > 1000ms)?

Answer 42

Panic - do nothing

Question 43

What is the Ring Election Algorithm?

Answer 43

Nodes in logical ring communicate with upstream neighbours. Election message circulates collecting IDs. Highest ID wins.