Distributed Systems Lecture 9: Synchronization - PDF

Distributed Systems and Web Services Lecture 9 Synchronization in Distributed System Dr. Marwa Zamzam German International University in Cairo [email protected] 1 Why do we need Process Coordination?  A d...

Distributed Systems and Web Services Lecture 9 Synchronization in Distributed System Dr. Marwa Zamzam German International University in Cairo [email protected] 1 Why do we need Process Coordination?  A distributed system is a set of communicating autonomous systems that appear to the user as a single system (distribution transparency).  In a distributed system processes are running on multiple machines that may be dispersed geographically.  Also each machine has its own hardware and hence its own real-time clock.  Processes need to communicate and also may access shared resources such as common storage. Slides credit goes to Dr. Mohamed Abdelwahab Saleh 2 Process Coordination  Therefore, one essential need is to “coordinate” between processes to manage their interactions and dependencies.  Process coordination ensures smooth and collaborative operation between processes and avoids problems like data corruption and deadlocks. 3 Clock Synchronization 4 Clock Synchronization Parameters 5 Types of Synchronization 6 Software and Hardware Clocks 7 Clock drift 8 Detecting and adjusting incorrect times  Server A would like to synchronize time with server B which has an accurate clock (UTC).  A sends a request and receives response, both request and response are time-stamped by sender.  Of course the main problem here is the delay both during request and response. 9 Estimating delays to synchronize clocks (NTP)  Server A knows T1 (time of sending request) and T2 (it is sent by server B in the response).  Server A also knows T3 (time-stamp in received response) and T4 (time of receiving response).  Time difference between Two clocks: 𝜃 = 𝑇3 + 𝛿 − 𝑇4 10 Keeping time without UTC–Berkeley algorithm 𝟗. 𝟏𝟓 𝟐. 𝟓𝟎 + 𝟑. 𝟐𝟓 + 𝟑 = 𝟗. 𝟏𝟓, 𝒂𝒗𝒆𝒓𝒂𝒈𝒆 = = 𝟑. 𝟎𝟓 𝟑 11 Logical clocks: The happened-before relationship Issue 12 Ordering of events–the happened-before relation 1. Single process: For example in P1, we are sure that a happens before b’ as they are using the same clock. 2. Sending and Receiving: For example, a happens before b. 3. Transitivity: After ordering some events we can deduce some other relations. a b: send-receive 13 Ordering of events–the happened-before relation 14 Logical Clock 15 Logical clocks: solution 16 Algorithm for logical clocks 17 Breaking ties using process IDs 18 Problems caused by concurrency 19 Problems caused by concurrency Amount=1100 Amount=1010 20 How to achieve total-ordered multicast? 21 Achieving total-ordered multicast 22 Logical clocks: where implemented 23 Thank you  24