Coordination
CE32204– Distributed System
Presented by: Eka Stephani Sinambela
Institut Teknologi Del
Introduction
Why coordination is important?
◉ Concentrate on how processes can synchronize and coordinate their actions.
◉ Example:
○ Multiple processes do not simultaneously access a shared such as a file, but
instead cooperate in granting each other temporary exclusive access.
○ Multiple processes may sometimes need to agree on the ordering events, such as
whether message m1 from process P was sent before or after message m2 from
process Q.
Why coordination is important?
◉ Synchronization and coordination are two closely related phenomena.
○ Process synchronization one process waits for another complete its operation.
○ data synchronization to ensure that two sets of data are the same.
○ Coordination the goal is to manage the interactions and dependencies between
activities in a distributed system.
◉ Issue of synchronization
○ actual time
○ Synchronization in which only relative ordering matters rather than ordering in absolute
time
Logical Clock
The Happened-before relationship
◉ What usually matters is not that all processes agree on exactly what time it is, but
they that they agree on the order in which events occur. Requires a notion of
ordering.
◉ The happened-before relation
○ If a and b are two events in the same process, and a comes before b, then a b.
○ If a is the sending of a message, and b is the receipt of that message, then a b.
○ If a b and b c, then a c
Logical Clocks
◉ Problem
○ How do we maintain a global view on the system’s behavior that is consistent with
the happened-before relation?
◉ Attach a timestamp C(e) to each event e, satisfying the following properties:
○ P1 if a and b are two events in the same process, and a b, then we demand that C(a) < C(b).
○ P2 if a corresponds to sending a message m, and b to the receipt of that message, then also C(a) <
C(b).
◉ Problem
○ How to attach a timestamp to an event when there’s no global clock maintain a consistent set of
logical clocks, one per process.
Logical Clocks
◉ Solution
○ Each process Pi maintains a local counter Ci and adjust this counter
■ For each new event that takes place within Pi, Ci is incremented by 1.
■ Each time a message m is sent by process Pi, the message receives a timestamp ts(m) = Ci.
■ Whenever a message m is received by a process Pj, Pj adjusts its local counter Cj to max{Cj,
ts(m)}; then executes step 1 before passing m to the application.
○ Property P1 is satisfied by (1); Property P2 by (2) and (3).
Logical Clocks
◉ Example
○ Consider three processes with event counters operating at different rates
Logical Clocks
◉ Where implemented
○ Adjustments implemented in middleware
Vector Clocks
◉ Observation
○ Lamport’s clocks do not guarantee that if C(a) < C(b) that a causally preceded b.
○ Concurrent message transmission using logical clocks.
○ Observation
■ Event a: m1 is received at T = 16
■ Event b: m2 is sent at T = 20
◉ We cannot conclude that a causally precedes b
Vector Clocks
◉ Example:
○ Capturing potential causality when exchanging messages
○ Analysis
Mutual Exclusion
◉ Problem
○ A number of processes in a distributed system want exclusive access to
some resource (simultaneously access the same resources).
◉ Basic solution:
○ Permission-based: A process wanting to enter its critical section, or access a
resource, needs permission from other processes.
■ Centralized algorithm
■ Distributed algorithm
Permission-based centralized
◉ Simply use coordinator
◉ (a) Process P1 asks the coordinator for permission to access a shared
resource. Permission is granted.
◉ (b) Process P2 then asks permission to access the same resource. The
coordinator does not reply.
◉ (c) When P1 releases the resource, it tells the coordinator, which then replies
to P2
Permission-based distributed
◉ Mutual Exclusion Ricart & Agrawala
○ Return a response to a request only when:
■ The receiving process has no interest in the shared resource; or
■ The receiving process is waiting for the resource, but has lower priority (known through
comparison of timestamps)
◉ Example with three process
○ (a) Two processes want to access a shared resource at the same moment.
○ (b) P0 has the lowest timestamp so it wins.
○ (c) When process P0 is done, it sends OK also, so P2 can now go ahead.
Thanks!
