02-11-2012, 12:32 PM
Event Ordering
Event Ordering.pdf (Size: 88.51 KB / Downloads: 22)
Time and Ordering
The two critical differences between centralized and distributed systems
are:
• absence of shared memory
• absence of a global clock
We will study:
• how programming mechanisms change as a result of these differences
• algorithms that operate in the absence of a global clock
• algorithms that create a sense of a shared, global time
• algorithms that capture a consistent state of a system in the
absence of shared memory
Limitation of Lamport's Algorithm
In Lamport's algorithm two events that are causally related will be related
through their clock times. That is:
If a --> b then C(a) < C(b)
However, the clock times alone do not reveal which events are causally
related. That is, if C(a) < C(b) then it is not known if a --> b or not. All
that is known is:
if C(a) < C(b) then b -/-> a
It would be useful to have a stronger property - one that guarantees that
a --> b iff C(a) < C(b)
This property is guaranteed by Vector Clocks.