5 - Sync and Clocks

Question 1

Temporal Ordering

Answer 1

Exact time not needed but order is important

Question 2

UTC

Answer 2

Universal Coordinated Time

Question 3

International Atomic TIme (TAI) is based on

Answer 3

electron transition frequency of calcium 133

Question 4

UTC = TAI - ????

Answer 4

leap seconds

Question 5

Precision

Answer 5

Keep deviation within specified bound

Question 6

Accuracy

Answer 6

Keep deviation from actual time within specified bound

Question 7

Internal Sync

Answer 7

Sync clocks to improve precision but not neccessarily accuracy

Question 8

Berkeley Algorithm

Answer 8

Time server sends time to all,
difference is returned,
average is calculated,
average - each computers difference is sent back to each computer

Question 9

Negative Time adjustments are bad. Why?

Answer 9

Timestamps are not monotonically increasing and events on the same computer can have smaller timestamps than earlier events

Question 10

Lamport Clock

Answer 10

Each process maintains and adjusts local counter.
Weak consistency

Question 11

Lamport Clock: Event is within Pi

Answer 11

Ci is incremented by 1.

Question 12

Lamport Clock: Message is sent by Pi

Answer 12

timestamp ts(m)=Ci is attached.

Question 13

Lamport Clock: Message is sent by Pj

Answer 13

local counter Cj is set to max{Cj,ts(m)}; then Ci +1 before passing m to app

Question 14

Weak Consistency Guarantee

Answer 14

a -> b => ts(a) < ts(b)

if a happened before b, always smaller timestamp but if a timestamp is smaller, not necessarily before b

Question 15

Strong Consistency Guarantee

Answer 15

a->b <=> ts(a) < ts(b)

Question 16

Vector Clock consistency

Answer 16

Strong

Question 17

GNSS

Answer 17

Global Navigation Satellite Systems

GPS etc

Question 18

GPS: What makes it work?

Answer 18

32 satellites with atomic clocks constantly send position and time.
Determine distance to several and compute intersection

Question 19

GPS: Computing distance

Answer 19

Multiply signal speed and transmission time

Transmission time = reception time - sending time

Question 20

Positioning: How many spheres/circles in 2D/3D?

Answer 20

3 circles in 2D
4 spheres in 3D

Question 21

Clock Deviation Problem

Answer 21

Internal Delay
Clocks not synced

Question 22

RBS: Definition

Answer 22

Internal sync in wireless networks where components are directly reachable

Question 23

RBS

Answer 23

Reference Broadcast Sync

Question 24

Showing that vector clocks fulfil strong consistency

Answer 24

Assume relation < from lecture. Consider ALL cases:
- Weak consistency follows from process clock increasing with every event and that the timestamp of reception is larger than sending. < is transitive.
- If B -> A then ts(B)<ts(A) and thus ts(A) /< ts(B). INCOMPLETE

Question 25

Where could vector clocks be useful?

Answer 25

Concurrent Events and dependencies between events.

Eg a faulty computation A, then B needs to be repaired too, but if A /-> B then B doesn’t need repair

Question 26

Total order multicast

Answer 26

Requires that messages be delivered in the same order as they would be if comms were instant.