14-11-2012, 02:42 PM
Lamport’s Logical Clock
Lamport’s Logical Clock.pdf (Size: 393.84 KB / Downloads: 97)
Inherent Limitations of a Distributed System
Absence of Global clock
· difficult to make temporal order of events
· difficult to collect up-to-date information on the state of the entire system
Absence of Shared Memory
· no up-to-date state of the entire system to any individual process as there's no
shared memory
· coherent view -- all observations of different processes ( computers ) are
made at the same physical time
we can obtain a coherent but partial view of the system or
incoherent view of the system
· complete view ( global state ) -- local views ( local states ) + messages in
transit
difficult to obtain a coherent global state
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.
Distributed Mutual Exclusion
Distributed mutual exclusion (DME) coordinates software on different computers so that they agree
upon assigning a resource or section of code to one particular task.
Requirement
· Mutual Exclusion
· Freedom from
deadlock
· Eventual
entry(freedom from starvation)
· All processes must
participate equally.
· Only interested processes participate.
Assumptions
•N nodes randomly request access.
•Messages are not lost or corrupted.
•Message transmissions take a finite, variable, non-zero time.
•Messages arrive in order.
•Transmission time might not be transitive.
•Network is fully connected.
Mutual Exclusion Goals
· Minimize the number of messages sent.
· Grant permission in order of request.
· Fault tolerant
· Fair to all systems
· Scalable
Distributed Mutual Exclusion Algorithms
Assertion Based
· Lamport algorithm
· Ricart-Agrawala algorithm
· Maekawaa algorithm
Token Based
· Raymond’s Tree-based algorithm
· Simple 2 process algorithm