Synchronization in Distributed Systems PDF

# Synchronisation in Distributed Systems ## Synchronisation - In a centralized system: all processes reside on the same system utilize the same clock. - In a distributed system: like synchronize everyone's watch in the classroom. ## Global Time - Global Time is utilized to provide timestamps fo...

# Synchronisation in Distributed Systems ## Synchronisation - In a centralized system: all processes reside on the same system utilize the same clock. - In a distributed system: like synchronize everyone's watch in the classroom. ## Global Time - Global Time is utilized to provide timestamps for processes and data. - **Physical clock:** concerned with "People" time - **Logical clock:** concerned with relative time and maintain logical consistency ## Physical Clocks - There are two aspects: - Obtaining an accurate value for physical time - Synchronizing the concept of physical time throughout the distributed system - These can be implemented using centralized algorithms or distributed algorithms ## Obtaining an Accurate Physical Time - A physical time server is needed to access the current time from a universal time coordinator (UTC). - Two sources for UTC: - WWV shortwave radio station in Ft. Collins, Colorado - Geostationary Operational Environmental Satellites (GEOS) ## Synchronizing Physical Time - The difference in time between two clocks due to drifting is defined as clock skew. As long as any and every two clocks differ by a value less than the maximum skew value, the time service is considered to be maintaining synchronization. ## How to synchronize two clocks in A and B? - The information necessary to read the value must be communicated across the network to location B. - B's clock value must be read. - B's clock value is communicated back to location A. - B's clock value is adjusted to reflect the time necessary to travel across the network. - B's clock value is compared to A's clock value. ## Centralized Physical Time Services - Broadcast Based - Request Driven ## Broadcast Based - first approach - **The centralized time server's action:** The physical time service broadcasts periodically the current time to members of the distributed systems. - **The participants' action:** - If a given participant's clock is ahead of the time server's clock, the participant slows down its clock so that it will continually move closer to the accurate time. - If a participant's clock is behind the time server's clock, the participant moves its clock forward. Alternatives do include gradually speeding up the clock. ## Distributed Physical Time Service - Each location broadcasts its current time at predefined set intervals. Once a location has broadcast its time, it starts a timer. It then collects time messages that it receives. Each time message that arrives is stamped with the local current time. This process continues until the timer expires. Upon the expiration of the timer, each message is adjusted to reflect the network delay time estimated for the message source. At this stage, the participant calculates the average time according to one of the following approaches: ## Logical Clocks - **Why Logical Clocks?** It is difficult to utilize physical clocks to order events uniquely in distributed systems. - **The essence of logical clocks is based on the happened-before relationship presented by Lamport.** ## Happen-Before Relationship - If two events, a and b, occurred at the same process, they occurred in the order of which they were observed. That is, a > b. - If a sends a message to b, then a > b. That is, you cannot receive something before it is sent. This relationship holds regardless of where events a and b occur. - The happen-before relationship is transitive. If a happens before b and b happens before c, then a happens before c. That is, if a > b and b > c, then a > c. ## Logical Ordering - If T(a) is the timestamp for event a, the following relationships must hold in a distributed system utilizing logical ordering. - If two events, a and b, occurred at the same process, they occurred in the order of which they were observed. That is T(a) > T(b). - If a sends a message to b, then T(a) > T(b). - If a happens before b and b happens before c, T(a) > T(b), T(b) > T(c), and T(a) > T(c). ## For example - A diagram depicting three processes with events A, B, C, D, E and F. The events A, B and C occur on different processes, with A happening before B, B happening before C, and C happening before D. Events D and E occur on different processes, with D happening before E. Event F occurs after event E. ## Lamport's Algorithm - Each process increments its clock counter between every two consecutive events. - If a sends a message to b, then the message must include T(a). Upon receiving a and T(a), the receiving process must set its clock to the greater of [T(a)+d, Current Clock]. That is, if the recipient's clock is behind, it must be advanced to preserve the happen-before relationship. Usually d=1. ## For example - A diagram depicting three processes with events A, B, C, D, E and F. The events A, B and C occur on different processes, with A happening before B, B happening before C, and C happening before D. Events D and E occur on different processes, with D happening before E. Event F occurs after event E. Timestamps are provided for each event. ## Total Ordering with Logical Clocks - A diagram depicting three processes with events A, B, C, D, E and F. The events A, B and C occur on different processes, with A happening before B, B happening before C, and C happening before D. Events D and E occur on different processes, with D happening before E. Event F occurs after event E. Timestamps are provided for each event. ## Mutual Exclusion - In single-processor systems, critical regions are protected using semaphores, monitors, and similar constructs. - In distributed systems, since there is no shared memory, these methods cannot be used. ## A Centralized Algorithm - A diagram depicting a centralized algorithm for mutual exclusion. A process sends a request to a coordinator, which then grants it. The process enters a critical section, exits it, and sends a release message to the coordinator. - **Advantages:** It is fair, easy to implement, and requires only three messages per use of a critical region (request, grant, release). - **Disadvantages:** single point of failure. ## Distributed Algorithm - A diagram depicting a distributed algorithm for mutual exclusion. There is no central coordinator. Each process sends a request to all other processes. The process then enters a critical section, exits it, and sends a release message to all other processes. - **Advantages:** More robust than centralized algorithm - **Disadvantages:** More complex to implement ## Token Ring Algorithm - A diagram depicting a token ring algorithm for mutual exclusion. A token circulates around the ring, allowing only the process holding the token to enter a critical section. The process holding the token then passes it on to the next process in the ring. - **Advantages:** Fair - **Disadvantages:** Can be slow if the token has to travel a long distance, and a process crash can prevent the token from circulating ## A Comparison of the Three Algorithms - A table comparing the three algorithms for mutual exclusion. The table shows the number of messages required per entry/exit, the delay before entry, and the problems that can occur. ## Election Algorithm - The **bully algorithm** is used to elect a coordinator in a distributed system where there is no central authority. - When a process notices that the coordinator is no longer responding to requests, it initiates an election. A process, P, holds an election as follows: - P sends an ELECTION message to all processes with higher numbers. - If no one responds, P wins the election and becomes coordinator. - If one of the higher-ups answers, it takes over. P's job is done. ## For example - A diagram showing the bully algorithm. - A process with ID 6 notices that the current coordinator is no longer responding. It sends ELECTION messages to processes with higher IDs (1, 2, 3, 4, and 5). - If none of the processes with higher IDs respond, the process with ID 6 becomes the new coordinator. - If one of the processes with a higher ID responds, it takes over the election process. ## A Ring Algorithm - A diagram depicting a ring algorithm for election. - Each process has a unique ID. - Processes send messages around the ring. - The process with the highest ID becomes the coordinator. ## Transaction Primitives - **BEGIN TRANSACTION:** Mark the start of a transaction. - **END TRANSACTION:** Terminate the transaction and try to commit. - **ABORT TRANSACTION:** Kill the transaction; restore the old values. - **READ:** Read data from a file (or other object). - **WRITE:** Write data to a file (or other object). ## For example, - **BEGIN TRANSACTION** - reserve Austin-Houston; - reserve Houston-Los Angeles; - reserve Los Angeles-Seattle; - **END TRANSACTION** ## Properties of Transactions - **Atomic:** To the outside world, the transaction happens indivisibly. - **Consistent:** The transaction does not violate system invariants. - **Isolated:** Concurrent transactions do not interfere with each other. - **Durable:** Once a transaction commits, the changes are permanent. ## Isolated or serializable - Isolated or serializable means that if two or more transactions are running at the same time, to each of them and to other processes, the final result looks as though all transactions ran sequentially in some (system dependent) order. ## Nest Transactions - Transactions may contain subtransactions, often called nested transactions. - If the subtransaction commits and the parent transaction aborts, the permanence applies only to top-level transactions. ## Concurrency Control - When multiple transactions are executing simultaneously in different processes, some mechanism is needed to keep them out of each other's way. That mechanism is called a concurrency control algorithm. ## Concurrency control algorithms - **Locking:** - In the simplest form, when a process needs to read or write a file (or other object) as part of a transaction, it first locks the file. - Distinguishing read locks from write locks. - The unit of locking can be an individual record or page, a file, or a larger item. - **Two-phase locking** - The process first acquires all the locks it needs during the growing phase, then releases them during the shrinking phase. - In many systems, the shrinking phase does not take place until the transaction has finished running and has either committed or aborted. This policy is called strict two-phase locking. ## Two-phase locking - A diagram depicting two-phase locking. The number of locks held by a transaction increases during the growing phase and decreases during the shrinking phase. ## Optimistic Concurrency Control - A second approach to handling multiple transactions at the same time is optimistic concurrency control. The idea is simple: just go ahead and do whatever you want to, without paying attention to what anybody else is doing. If there is a problem, worry about it later.