Distributed system lamport's and vector algorithm

THIS IS LAMPORT'S AND VECTOR CLOCK PPT

1. DISTRIBUTED SYSTEM Lamppost’s& vectors logical clocks BY- PINKI KUMARI SONI

2. Logical clock A logical clock is a mechanism for capturing chronological and causal relationships in a distributed system. Distributed systems may have no physically synchronous global clock, so a logical clock allows global ordering on events from  different processes in such systems . Note - chronological :  the relation of a serial to its predecessors and successors Casual- Causation  indicates that one event is the result of the occurrence of the other event; i.e. there is a  causal relationship  between the two events.

3. Logical clock use and algorithms Logical clocks are useful in computation analysis, distributed algorithm design, individual event tracking, and exploring computational progress. Some noteworthy logical clock algorithms are: Lamport’s timestamps , which are monotonically increasing software counters. Vector clocks , that allow for partial ordering of events in a distributed system . Timestamp- a digital record of the time of occurrence of a particular event.

4. Lamport’s Lamport’s clocks are a simple technique used for determining the order of events in a distributed system. This clock was proposed by Leslie Lamport ,  a Lamport clock maintains order of operations by incrementing a counter contained in the events By simply adding a counter value to events as they are received and incrementing this value based on the last seen value , Lamport clocks provide a  partial ordering  of events – specifically “happened-before ” ordering .

5. LAMPORT’S algorithm follows some simple rules: A process increments its counter before each event in that process; When a process sends a message, it includes its counter value with the message; On receiving a message, the counter of the recipient is updated, if necessary, to the greater of its current counter and the timestamp in the received message. The counter is then incremented by 1 before the message is considered received . The algorithm for sending: time = time+1; time_stamp = time; send(message, time_stamp ); The algorithm for reciving : ( message, time_stamp) = receive(); time = max(time_stamp, time)+1;

6. Vector clock A vector clock is an algorithm for generating a partial ordering of events in a distributed system and detecting causality violations. Just as in Lamport timestamps, interprocess messages contain the state of the sending process'slogical clock.

7. Vector Clock Algorithm Initially, all vectors [0,0,…,0 ] For event on process i, increment own c i Label message sent with local vector When process j receives message with vector [d 1 , d 2 , …, d n ]: Set local each local entry k to max(c k , d k ) Increment value of c j

8. Important Points Physical Clocks Can keep closely synchronized, but never perfect Logical Clocks Encode causality relationship Lamport’s clocks provide only one-way encoding Vector clocks provide exact causality information • Causality – If a  b then event a can affect event b • Concurrency – If neither a  b nor b  a then one event cannot affect the other • Partial Ordering – Causal events are sequenced • Total Ordering – All events are sequenced