Page 1Page 1Logical ClocksPaul [email protected] SystemsExcept as otherwise noted, the content of this presentation is licensed under the Creative Commons Attribution 2.5 License.Page 2Logical clocksAssign sequence numbers to messages– All cooperating processes can agree on order of events– vs. physical clocks: time of dayAssume no central time source– Each system maintains its own local clock– No total ordering of events• No concept of happened-whenPage 3Happened-beforeLamport’s “happened-before” notationa  bevent ahappened before event be.g.: a: message being sent, b: message receiptTransitive:if a  band b  cthen a  cPage 4Logical clocks & concurrencyAssign “clock” value to each event– if abthen clock(a) < clock(b)– since time cannot run backwardsIf aand boccur on different processes that do not exchange messages, then neither a  bnor b  aare true– These events are concurrentPage 5Event counting example• Three systems: P0, P1, P2• Events a, b, c, …• Local event counter on each system• Systems occasionally communicatePage 6Event counting examplea bh ikP1P2P31 21 321d fg3c246e5jPage 7Event counting examplea bikjP1P2P31 21 321d fg3c246Bad ordering:e  hf  khe5Page 8Lamport’s algorithm• Each message carries a timestamp of the sender’s clock• When a message arrives:– if receiver’s clock < message timestampset system clock to (message timestamp + 1)– else do nothing• Clock must be advanced between any two events in the same processPage 9Lamport’s algorithmAlgorithm allows us to maintain time ordering among related events–Partial orderingPage 10Event counting examplea bikjP1P2P31 21 721d fg3c24667he5Page 11Summary• Algorithm needs monotonically increasing software counter• Incremented at least when events that need to be timestamped occur• Each event has a Lamport timestampattached to it• For any two events, where a  b:L(a) < L(b)Page 12Problem: Identical timestampsab, bc, …: local events sequencedic, fd , dg, … : Lamport imposes asendreceiverelationshipConcurrent events (e.g., a & i) mayhave the same timestamp … or nota bh ikjP1P2P31 21 771d fg3c646e5Page 13Unique timestamps (total ordering)We can force each timestamp to be unique– Define global logical timestamp (Ti, i)• Tirepresents local Lamport timestamp• i represents process number (globally unique)– E.g. (host address, process ID)– Compare timestamps:(Ti, i) < (Tj, j)if and only ifTi< Tjor Ti= Tjand i < jDoes not relate to event orderingPage 14Unique (totally ordered) timestampsa bikjP1P2P31.1 2.11.2 7.27.31.3d fg3.1c6.24.16.1he5.1Page 15Problem: Detecting causal relationsIf L(e) < L(e’)– Cannot conclude that ee’Looking at Lamport timestamps– Cannot conclude which events are causally relatedSolution: use a vector clockPage 16Vector clocksRules:1. Vector initialized to 0 at each processVi [j] = 0 for i, j=1, …, N2. Process increments its element of the vector in local vector before timestamping event:Vi [i] = Vi [i] +13. Message is sent from process Piwith Viattached to it4. When Pjreceives message, compares vectors element by element and sets local vector to higher of two valuesVj[i] = max(Vi[i], Vj[i]) for i=1, …, NPage 17Comparing vector timestampsDefineV = V’ iff V [i ] = V’[i ] for i = 1 … NV  V’ iff V [i ]  V’[i ] for i = 1 … N For any two events e, e’if e  e’ then V(e) < V(e’)• Just like Lamport’s algorithmif V(e) < V(e’) then e  e’Two events are concurrent if neitherV(e)  V(e’) nor V(e’)  V(e)Page 18Vector timestampsa bc dfe(0,0,0)P1P2P3(0,0,0)(0,0,0)Page 19Vector timestampsa bc dfe(0,0,0)P1P2P3(0,0,0)(0,0,0)(1,0,0)Event timestampa (1,0,0)Page 20Vector timestampsa bc dfe(0,0,0)P1P2P3(0,0,0)(0,0,0)(1,0,0)Event timestampa (1,0,0)b (2,0,0)(2,0,0)Page 21Vector timestampsa bc dfe(0,0,0)P1P2P3(0,0,0)(0,0,0)(1,0,0)Event timestampa (1,0,0)b (2,0,0)c (2,1,0)(2,0,0)(2,1,0)Page 22Vector timestampsa bc dfe(0,0,0)P1P2P3(0,0,0)(0,0,0)(1,0,0)Event timestampa (1,0,0)b (2,0,0)c (2,1,0)d (2,2,0)(2,0,0)(2,1,0) (2,2,0)Page 23Vector timestampsa bc dfe(0,0,0)P1P2P3(0,0,0)(0,0,0)(1,0,0)Event timestampa (1,0,0)b (2,0,0)c (2,1,0)d (2,2,0)e (0,0,1)(2,0,0)(2,1,0) (2,2,0)(0,0,1)Page 24Vector timestampsa bc dfe(0,0,0)P1P2P3(0,0,0)(0,0,0)(1,0,0)Event timestampa (1,0,0)b (2,0,0)c (2,1,0)d (2,2,0)e (0,0,1)f (2,2,2)(2,0,0)(2,1,0) (2,2,0)(0,0,1) (2,2,2)Page 25(0,0,1)(1,0,0)Vector timestampsa bc dfe(0,0,0)P1P2P3(0,0,0)(0,0,0)Event timestampa (1,0,0)b (2,0,0)c (2,1,0)d (2,2,0)e (0,0,1)f (2,2,2)(2,0,0)(2,1,0) (2,2,0)(2,2,2)concurrenteventsPage 26Vector timestampsa bc dfe(0,0,0)P1P2P3(0,0,0)(0,0,0)(1,0,0)Event timestampa (1,0,0)b (2,0,0)c (2,1,0)d (2,2,0)e (0,0,1)f (2,2,2)(2,0,0)(2,1,0) (2,2,0)(0,0,1) (2,2,2)concurrenteventsPage 27Vector timestampsa bc dfe(0,0,0)P1P2P3(0,0,0)(0,0,0)(1,0,0)Event timestampa (1,0,0)b (2,0,0)c (2,1,0)d (2,2,0)e (0,0,1)f (2,2,2)(2,0,0)(2,1,0) (2,2,0)(0,0,1) (2,2,2)concurrenteventsPage 28Vector timestampsa bc dfe(0,0,0)P1P2P3(0,0,0)(0,0,0)(1,0,0)Event timestampa (1,0,0)b (2,0,0)c (2,1,0)d (2,2,0)e (0,0,1)f (2,2,2)(2,0,0)(2,1,0) (2,2,0)(0,0,1) (2,2,2)concurrenteventsPage 29Summary: Logical Clocks & Partial Ordering• Causality– If a->bthen event acan affect event b• Concurrency– If neither a->bnor b->athen one event cannot affect the other• Partial Ordering– Causal events are sequenced• Total Ordering– All events are sequencedPage 30Page 30The