Distributed Computing Notes

Distributed Operating Systems

Synchronization

Synchronization ●

●

Rules for enforcing correct interaction are implemented in the form of synchronization mechanisms Issues ● ● ● ● ●

Clock Synchronization Event Ordering Mutual exclusion Deadlock Election algorithms

Clock Synchronization ●

Types –

External Synchronization ● ●

–

Internal Synchronization ● ●

●

●

Synchronization with real time( external) clocks Synchronized to UTC(Coordinated Universal Time) Mutually between different nodes For consistent view of the system

External Synchronization ensures internal synch. Clock skew – Difference in clock values between two nodes

Clock Synchronization contd... ●

Set of clocks are said to be synchronized if the clock skew of any two is less than δ (Specified constant)

●

Clocks should never run backwards

Synchronization algorithms

Centralized Algorithms

Active Time Server

Passive Time Server

Distributed Algorithms

Global Averaging

Local Averaging

Centralized Algorithms ●

Server node having real time receiver present

●

All clocks synchronized to this server node

●

Drawback – single point failure

●

Major classification –

Passive Time Server

–

Active Time Server

Passive Time Server ●

Each node periodically sends message(“time=?”) to the time server

●

Server responds by sending (“time=T”)

●

After receiving client adjusts time to –

T+(T1-T0)/2 (T0 – Client time when message sent T1 - Client time when reply received)

–

T+(T1-T2-I)/2 (I – Time taken by time server to handle interrupt)

–

Several T1-T0 are considering and an average is used

–

Minimum of T1-T0 is used

Active Time Server ●

●

●

●

●

Time server node periodically broadcasts clock time (“time=T”) Time of propagation (Ta) from server to client is known Client adjusts time to T+Ta Not fault tolerant if the communication time is high then wrong adjustment Ex. Berkeley algorithm

Berkeley algorithm ●

●

●

●

Used for internal clock synchronization of a group Time server periodically sends a message (“time=?”) to all computers in the group On receiving the message each computer in the group sends its clock value to the server Server has prior knowledge of propagation time from node to the server

Berkeley algorithm contd… ●

● ●

Time server readjusts the clock values of the reply messages using fault tolerant average The time server readjusts its own time too. Time server sends the adjustment (positive or negative) to each node

Distributed Algorithms ●

All nodes equipped with real time receiver so that each node’s clock is independently synchronized with real time

●

External synch. Also results in internal syn.

●

Internal synchronization performed for better results –

Global averaging distributed algorithms ● ●

●

●

–

Clock process at each node broadcasts its local clock time in the form of resynch message After broadcasting node waits for time T during which it collects resynch messages by other nodes At the end of waiting time, it clock estimates the skew of its clock with respect to other nodes Uses this correct its own local clock before restart of next resync interval

Localized averaging distributed algorithms ● ●

Nodes of the system are logically arranged in some kind of pattern such as ring or grid Each node sets its own clock time to average of its own clock time and the clock time of its neighbors

EVENT ORDERING ●

Happened before relation ( casual ordering) –

If a and b are events of the same relation ● ●

●

– –

a occurs before b ; a -> b a is the event of sending message by one process and b is the event of receiving the same message by another message ; a -> b If a -> b , b -> c then a -> c

Irreflexive , a -> a not true Events concurrent if not related by happened before relation

Event ordering ●

Need for globally synchronized physical clocks For event ordering –

Logical clock concept ●

●

●

Associate timestamp with every event

Implementation of logical clocks –

If a occurs before b in process Pi then Ci(a) < Ci(b)

–

If a is the sending of a message by process Pi and b is the receipt of that message by process Pj then Ci(a)
–

Clocks should always go forward , that is corrections should be positive value

To meet the above conditions : Lamport’s algorithm –

The implementation rules of lamport’s algorithm ●

●

IR1 : Each process Pi increments Ci between any two events IR2 : If event a is the sending of message m by process Pi the message m contains a tinestamp Tm = Ci(a) upon receiving the message m a process Pj sets Cj greater than or equal to its present value but greater than Tm

Mutual Exclusion