Computer Networking
Clocks and Watches
The Difference Between

Lamport's logical clock?

Top Answer
User Avatar
Wiki User
Answered 2009-05-04 17:07:30

Leslie Lamport proposed this scheme to provide ordering of events in a distributed environment using logical clocks. Because it is impossible to have perfectly synchronized clocks and global time in a distributed system, it is often necessary to use logical clocks instead. Definitions:

Happened Before Relation (->). This relation captures causal dependencies between events, that is, whether or not events have a cause and effect relation. This relation (->) is defined as follows: * a -> b, if a and b are in the same process and a occurred before b. * a -> b, if a is the event of sending a message and b is the receipt of that message by another process. * If a -> b and b -> c, then a -> c - that is, the relation has the property of transitivity. Causally Related Events: If event a -> event b, then a causally affects b. Concurrent Events: Two distinct events a and b are concurrent (a b) if (not) a -> b and (not) b -> a. That is, the events have no causal relationship. This is equivalent to b a. For any two events a and b in a system, only one of the following is true: a -> b, b -> a, or a b. Lamport introduced a system of logical clocks in order to make the -> relation possible. It works like this: Each process Pi in the system has its own clock Ci. Ci can be looked at as a function that assigns a number, Ci(a) to an event a. This is the timestamp of the event a in process Pi. These numbers are not in any way related to physical time -- that is why they are called logical clocks. These are generally implemented using counters, which increase each time an event occurs. Generally, an event's timestamp is the value of the clock at that time it occurs. Conditions Satisfied by the Logical Clock system:

For any events a and b, if a -> b, then C(a) < C(b). This is true if two conditions are met: * If a occurs before b, then Ci(a) < Ci(b). * If a is a message sent from Pi and b is the recept of that same message in Pj, then Ci(a) < Cj(b). Implementation Rules Required

* Clock Ci is incremented for each event: Ci := Ci + d (d > 0) * if a is the event of sending a message from one process to another, then the receiver sets its clock to the max of its current clock and the sender's clock - that is, Cj := max(Cj, tm + d) (d > 0) .

User Avatar

Your Answer


Still Have Questions?

Related Questions

Conditions to be satisfied by lamports logic clock?

Conditions satisfied by the logical clocks&Acirc;&middot; Clock condition: if a&Atilde;&nbsp;b,&Acirc;&middot; then C(a) o If event a happens before event b, then the clock value (timestamp) of a should be less than the clock value of bo Note that we can not say: if C(a)&Acirc;&middot; Correctness conditions (must be satisfied by the logical clocks to meet the clock condition above):[C1] For any two events a and b in the same process Pi, if a happens before b, then Ci (a) [C2] If event a is the event of sending a message m in process Pi , and event b is the event of receiving that same message m in a different process Pk, then Ci (a)

Drawbacks of Lamport logical clock?

Lamport's clock does'nt ensure that if L(e1)&lt;L(e2) e1-&gt;e2

What is positive and negative trigger SR flip flop with clock input?

WHY not what positive triggering means as a signal rises from a negative potential and vice verse. R means reset whereby a state is mandated by that signal. Set is the means TO SET A FLIP FLOP to a certain condition. When S = logical '1' value, and the clock input toggles, the output (normally labelled 'Q') will be a logical '1'. when R = logical '1' and the clock input toggles, the output will become a logical '0'.

What is internal clock speed?

Here is a short explanation. Clock rate or clock speed is the speed at which a microprocessor (CPU) executes instructions. Clock speeds are typically expressed in megahertz (MHz) or gigahertz ((GHz). A single clock cycle (usually shorter than a nanosecond in modern non-embedded microprocessors) toggles between a logical zero and a logical one state. Sources:

What ticks but never tocks but can tock but never tick?

This is a really interesting scenario. However, the answer is a clock. It is only logical because it ticks and tocks, but not at the same time.

Why microprocessor frequency is half of crystal frequency?

Because that's how Intel designed it. They wanted an internal four phase clock, so the most logical way was to divide the crystal oscillator frequency by two. Different things happen at different clock edges, and they accomplished their goal.

Difference between Bus Clock and System Clock in Microcontrollers?

Bus Clock is based on the System Clock. In other terms Bus Clock is derived from system Clock. Bus Clock is usually half System Clock. (Busy Clock = System Clock / 2)

How is a computer's clock different from real clock?

A computers clock is a real clock

What happened to the hen that ate a clock?

It went, "Clock, Clock!" Get it? Clock instead of Cluck?

What is the difference between vector clock and lamport's logical clock?

Reading Vector Clock TimestampsCausally OR Concurrent:Events a and b are either causally related or they are concurrent. Definition: "event a" causes "event b" if and only if ta where: ta they are not equal timestamps ( there exists i, ta[i] != tb[i]) andeach ta[i] is less than or equal to tb[i] (for all i, ta[i]

O'clock is it on clock or of clock?

the full form of it is of the clock

What kind of a clock is an electric clock?

digital clock

What does o clock means?

it meas the clock hand it meas the clock hand it meas the clock hand

What is summary of the clock?

I think you have not asked a complete question. A clock is a clock is a clock, either digital or with a conventional clock face. How would anyone summarise that?

What is the purpose of mechanical clock?

The purpose of all clocks (e.g. mechanical clock, water clock, electronic clock, atomic clock) is to measure the passage of time.

How do you repair a clock?

Remove the clock decorative cover. Remove the clock retaining ring. Remove the clock wiring harness. Reverse the process to install the new clock.

What are the clock operators main responcabilities in basketball?

they need to manage the clock so when the referee stops the clock the clock operator needs to write it down and stop the clock.

Meaning of o' clock?

of the clock 2 o'clock = two of the clock

What is the oldest type of clock?

The oldest type of clock is a sun clock {Merket}

Why is ford clock fast?

Why is ford clock fast? why clock fast in vehicles

What is the proper contraction for of the clock?

The term "o'clock" means "of the clock" or "according to the clock."

Fusee Wall Clock?

form_title= Fusee Wall Clock form_header= Always be on time with a wall clock. What size would you like your clock?*= _ [50] What color would you like your clock?*= _ [50] Where will you hang your clock?*= _ [50]

What's the difference between a clock radio and an alarm clock?

A clock radio and an alarm clock are two very similar things which provide some of the same functions however they differ in their features. An alarm clock is a basic clock which has an alarm function and a clock radio combines the use of an AM/FM radio and an alarm clock.

What's the best alarm clock app for iPhone?

The iPhone comes with a clock app already installed that has an alarm clock features. This is the best alarm clock that I have found so far. Other popular alarm clock apps are:CARROT Alarm - Talking Alarm ClockWake Alarm ClockSpeakToSnooze ProSleep Cycle Alarm ClockWake n Shake Alarm ClockRise Alarm Clock

What is clock in Irish?

clog = clock