Tag: converse

  • Lamport’s Clocks (notes)

    Lamport’s Clocks (notes)

    [ez-toc]

    Introduction

    Summary

    Now that we talked about happened before events, we can talk about lamport clocks

    Lamport’s Logical Clock

    Summary

    A logical clock that each process has and that clock monotonically increases as events unfold. For example, if event A happens before event B, then the event A’s clock (or counter value) must be less than that of B’s clock (or counter). The same applies between “happened before” events. To achieve this, a process will increase its own clock monotonically by setting the counter to the maximum of “receipt of the other process’s clock or its own local counter”. But what happens with concurrent events? Will hopefully learn soon

    Events Quiz

    Summary

    C(a) < C(b) means one of two things. A happened before B in the same process. Or B is the recipient and chose the max between its local clock.

    Logical Clock Conditions

    Lamport’s logical clock conditions

    Summary

    Key Words: partial order, converse of condition

    Lamport clocks give us a partial order of all the events in the distributed system. Key idea: Converse of condition 1 is not true. That is, just because timestamp of x is less than timestamp of y does not necessarily mean that x happened before y. Also, is partial order sufficient for us distributed system designers?

    Need For A Total Order

    Need for total order

    Summary

    Imagine a situation in which there’s a shared resource and individual people want access to that resource. They can send each other a text message (or any message) with a timestamp. The sender with the earliest timestamp wins. But what happens if two (or more) timestamps are the same. Then each individual person (or node) must make a local decision (in this case, oldest age of person wins)

    Lamport’s Total Order

    Lamport’s total order

    Summary

    Use timestamps to order events and break the time with some arbitrary function (e.g. oldest age wins).

    Total Order Quiz

    Total order quiz

    Summary

    Identify the concurrency events and then figure out how to order those concurrent events to break the ties

    Distributed Mutual Exclusion Lock Algorithm

    Distributed mutual exclusion lock

    Summary

    Essentially, this algorithm basically requires each process to send their lock requests via messages and these messages need to be confirmed by the other processes. Each request contains a timestamp and each host will make its own local decision, queueing (and sorting) the lock request in their local process and breaking ties by preferring lowest process ID. What’s interesting to me is that this algorithm makes a ton of assumptions like no broken network links or split brain or unidirectional communication: so many failure modes that haven’t been taken into consideration. Wondering if this will be discussed in next video lectures

    Distributed Mutual Exclusion Lock Algorithm (continued)

    Distributed mutual exclusion lock continued

    Summary

    Lots of assumptions of distributed mutual exclusion lock algorithm including 1) All messages are received in the order they are sent and 2) no messages are lost (this is definitely not robust enough for me at least)

    Messages Quiz

    Messages Quiz

    Summary

    With Lamport’s distributed mutual exclusion lock, we need to send 3(N-1) messages. First round that includes timestamp, second for acknowledge, third for release of lock.

    Message Complexity

    Message Complexity

    Summary

    A process can defer its acknowledgement by sending it during the unlock, reducing the message complexity from 3(N-1) to 2(N-1).

    Real World Scenario

    Real world scenario

    Summary

    Logical clocks may not good be enough in real world scenarios. What happens if a system clock (like the banks clock) drifts? What should we be doing instead?

    Lamport’s Physical Clock

    Lamport’s physical clock

    Summary

    Key Words: Individual Clockdrift, Mutual Clockdrift

    Two conditions must be met in order to achieve Lamport’s physical clock. First is that the individual clock drift for any given node must be relatively small. Second, the mutual clock drift (i.e. between two nodes) must be negligible as well. We shall see soon but the clock drift must be negligible when compared to intercommunication process time

    IPC time and clock drift

    IPC and Clock Drift

    Summary

    Clock drift must be negligible when compared to the IPC time. Collectively, this is captured in the equation M >= Epsilon ( 1 – k) where E is the mutual clock drift and where K is individual clock drift.

    Real World Example (continued)

    Real world example

    Summary

    Mutual clock drift must be lower than IPC time. Or put differently, the IPC time must be greater than the clock drift. So the key take away is this: the IPC time (M) must be greater than the mutual clock drift (i.e. E), where k is the individual clock drift. So we want a individual clock drift to be low and to eliminate anomalies, we need IPC time to be greater than the mutual clock drift.

    Conclusion

    Summary

    We can use Lamport’s clocks to stipulate conditions to ensure deterministic behavior and avoid anomalous behaviors