Chapter 3: Time Flashcards

Question

Network time protocol (NTP)

Answer 1

* **Provides** Coordinated Universal Time (**UTC**) including **scheduled leap second adjustments** * **No information** **about** **timezones** or daylight saving time **transmitted** (must be obtained separately) * **Time service** and dissemination of time over **Internet** Maintains time to within tens of milliseconds over Internet; **achieves 1 millisecond** accuracy in LANs under ideal conditions * Supported by daemon (ntpd) in user space (kernel support) via UDP on port 123

Answer 2

* **With** a **receiver**, a **clock** can be **synchronized to 1–10s ms** of **UTC** * Quartz crystal clocks drift 1 micro second per second, about 4 ms per hour * **On** a **network**, **computer** clocks can be s**ynchronized to within 30 ms** of each other (using **NTP**) In 30 ms, a 32‐bit 2.4 GHz CPU can execute about 720 million instructions

Answer 3

* Key idea is to **abandon** the idea of **physical time** Often sufficient to know the **order of events** * Lamport (1978) introduced **logical** (virtual) time and methods to **synchronize logical clocks** Leslie Lamport, "Time, clocks, and the ordering of events in a distributed system”, Communications of the ACM, Vol. 27, No. 7, July 1978, pp. 558‐565 Won the Dijkstra Prize in Distributed Computing (2000) and the ACM SIGOPS Hall of Fame Award (2007)

Answer 4

* Often **sufficient** to know the **order of events** * An **event** may be an **instruction** **execution**, **method** call, order entry, etc. * **Events include** **message** **send** & **receive** Within a single process order **determined** **by** instruction **execution** **sequence** **Between two processes** on same computer order determined using local physical clock **Between two different computers order cannot be determined using local physical clocks, since those clocks cannot be synchronized perfectly**

Answer 5

* *Describes a causal ordering of events**, denoted by * *→** If **a** and **b** are **events _in the same process_** and a **occurred** **before** **b** then **a → b** If a is the event of sending a message m in one process and b is the event of receiving m in another process then a → b The relaton“→” is transitive: If a→ b and b→ c then a → c If neither a → b nor b → a then a and b are concurrent, denoted by a || b abhingig

Answer 6

* Intuitively, **past events influence future events** * **Influence** among causally related **events** is **referred** to as **causal effects** * **If a → b, event a (may) causally effects event b** * **Concurrent** **events** **do** **not** **causally** **affect** **each** other (e.g., neither a → b nor b → a) For any two events a and b, either a→b, b→a, or a||b * “→” captures flow of data between events, but data may flow in ways other than via message passing * First event might or might not have caused the second event

Answer 7

* **Implementation** **of clock that tracks “→” numerically** * **Each process Pi has a logical clock Ci** * **Clock** **Ci** can **assign** a value **Ci(a)** **to** any **event** a **in process Pi** * **Value Ci(a) is the timestamp of event** a in process Pi Timestamps have **no relation to physical time,** which leads to the term logical clock Logical clocks assign monotonically increasing timestamps * **Can be implemented by a simple counter**

Answer 8

Clock condition **If a → b then C(a)** **But not: If C(a) Correctness conditions For any two events a and b in the same process Pi,** if a → b then Ci(a) If a is the event of sending a message in process Pi and b is the event of receiving that same message in a different process Pj then Ci(a)

Answer 9

* Clock Ci must be incremented between any two successive events in process Pi – C = C + d(d \> 0, usually 1) If a is the event of sending a message m in process Pi then m is assigned a timestamp * Tm = Ci(a) When that same message m is received by a different process Pk, Ck is set to a value greater than its present value (prior to the message receipt) and greater than Tm Ck =max{Ck ,Tm} + d(d\>0,usually1)

Answer 10

* **One way relation** * “happens before” send Message (msg: Message) = clock = clock + 1 send Over Network (msg, clock) let receiveMessage(msg:Message, cl:Clock) = * clock = max(clock, cl) + 1

Answer 11

* If **C(a) a may or may not happen‐before b** * Example illustrating this limitation C(p0) * **C(p0) One cannot determine whether two events are causally related** from timestamps alone

Answer 12

* System with n processes Each process Pi has a clock Ci, which is an integer vector of length n: Ci = ( Ci[1], Ci[2], ..., Ci[n] ) Ci(a) is the timestamp (clock value) of event a at process Pi Ci[i], entry i of Ci, is Pi’s logical time * Ci[i] represents the number of events that process Pi has timestamped \* Pi : (Ci[1], ..., Ci[i], ..., Ci[n])

Answer 13

* Clock Ci is incremented between any two successive events in process Pi * Ci[i] = Ci[i] + d (d \> 0, usually 1) * If event a is the event of sending a message m in process Pi, then message m is assigned a vector timestamp Tm = Ci(a) * When that same message misreceived by a different process Pk, Ck is updated as follows: * For all p, Ck[p] = max{ Ck[p], Tm[p] }

Answer 14

* Events p0, p1, q0, and r0 updated by first implementation rule * Received q1 updated by both implementation rules Received p2 tells P about Q and R R’s clock is old, but better than nothing!

Answer 15

‐ Extension of Lamport clocks‐ Two‐way relation‐ “happened before”‐ “happened after”

Answer 16

* If ta * ta = tb iff for all i: ta[i] = tb[i] * ta ≠ tb iff for any i: ta[i] ≠ tb[i] * ta ≤ tb iff for all i: ta[i] ≤ tb[i] * ta Overcomes the limitation of logical clocks

Chapter 3: Time Flashcards

(40 cards)