Chapter 18 Distributed-File Systems

18 CHAPTER Distributed Coordination Exercises 18.1 Discuss the advantages and disadvantages of the two methods we presented for generating globally unique timestamps. Answer: Globally unique timestamps can be generated using either a centralized or distributed approach. The centralized approach uses a single site for generating timestamps. A disadvantage of this approach is that if this site fails, timestamps can no longer be produced. Generating timestamps using the distributed approach provides more of a fail-safe mechanism, however care must be taken to ensure the logical clocks at each site are synchronized. 18.2 The logical clock timestamp scheme presented in this chapter provides the following guarantee: If event A happens before event B, then the timestamp of A is less than the timestamp of B. Note, however, that one cannot order two events based only on their timestamps. The fact that an event C has a timestamp that is less than the timestamp of event D does not necessarily mean that event C happened before event D; C and D could be concurrent events in the system. Discuss ways in which the logical clock timestamp scheme could be extended to distinguish concurrent events from events that can be ordered by the happens-before relationship. Answer: Vector clocks could be used to distinguish concurrent events from events ordered by the happens-before relationship. A vector clock works as follows. Each process maintains a vector timestamp that comprises of a vector of scalar timestamp, where each element reflects the number of events that have occurred in each of the other processes in the system. More formally, a process i maintains a vector timestamp ti j such that ti is equal to the number of events in process j that have oc121 122 Chapter 18 Distributed Coordination curred before the current event in process i. When a local event occurs in process i, tii is incremented by one to reflect that one more event has occurred in the process. In addition, any time a message is sent from a process to another process it communicates the timestamp vector of the source process to the destination process, which then updates its local timestamp vector to reflect the newly obtained information. More formally, when s sends a message to d, s communicates ts along with the message and d updates td such that for all i = d, tid = ma x(tsi , tdi ). 18.3 Your company is building a computer network, and you are asked to write an algorithm for achieving distributed mutual exclusion. Which scheme will you use? Explain your choice. Answer: The options are a (1) centralized, (2) fully-distributed, or (3) token-passing approach. We reject the centralized approach as the centralized coordinator becomes a bottleneck. We also reject the tokenpassing approach for its difficulty in re-establishing the ring in case of failure. We choose the fully-distributed approach for the following reasons: • Mutual exclusion is obtained. • Freedom from deadlock is ensured. • Freedom from starvation is ensured, since entry to the critical section is scheduled according to the timestamp ordering. • The number of messages per critical-section entry is 2 × (n − 1). This number is the minimum number of required messages per critical-section entry when processes act independently and concurrently. 18.4 Why is deadlock detection much more expensive in a distributed environment than it is in a centralized environment? Answer: The difficulty is that each site must maintain its own local wait-for graph. However, the lack of a cycle in a local graph does not ensure freedom from deadlock. Instead, we can only ensure the system is not deadlocked if the union of all local wait-for graphsis acyclic. 18.5 Your company is building a computer network, and you are asked to develop a scheme for dealing with the deadlock problem. a. Would you use a deadlock-detection scheme or a deadlockprevention scheme? b. If you were to use a deadlock-prevention scheme, which one would you use? Explain your choice. c. If you were to use a deadlock-detection scheme, which one would you use? Explain your choice. Answer: a. Would you use a deadlock-detection scheme, or a deadlockprevention scheme? Exercises 123 We would choose deadlock prevention as it is systematically easier to prevent deadlocks than to detect them once they have occurred. b. If you were to use a deadlock-prevention scheme, which one would you use? Explain your choice. A simple resource-ordering scheme would be used; preventing deadlocks by requiring processes to acquire resources in order. c. If you were to use a deadlock-detection scheme which one would you use? Explain your choice. If we were to use a deadlock detection algorithm, we would choose a fully-distributed approach as the centralized approach provides for a single point of failure. 18.6 Under what circumstances does the wait– die scheme perform better than the wound –wait scheme for granting resources to concurrently executing transactions? Answer: In the wound( –)wait scheme an older process never waits for a younger process; it instead rolls back the younger process and preempts its resources. When a younger process requests a resource held by an older process, it simply waits and there are no rollbacks. In the wait( –)die scheme, older processes wait for younger processes without any rollbacks but a younger process gets rolled back if it requests a resource held by an older process. This rollback might occur multiple times if the resource is being held by the older process for a long period of time. Repeated rollbacks do not occur in the wound( –)wait scheme. Therefore, the two schemes perform better under different circumstances depending upon when older processes are more likely to wait for resources held by younger processes or not. 18.7 Consider the centralized and the fully distributed approaches to deadlock detection. Compare the two algorithms in terms of message complexity. Answer: The centralized algorithm for deadlock detection requires individual processors or sites to report its local waits-for graph to a centralized manager. The edges in the waits-for graph are combined and a cycle detection algorithm is performed in the centralized manager. The cost of this algorithm is the cost of communicating the various waits-for graph to the centralized server. In the distributed approach, each site builds its own local waits-for graph and predicts whether there is a possibility of a cycle based on local observations. If indeed there is a possibility of a cycle, a message is sent along the various sites that might constitute a cyclic dependency. Multiple sites that are potentially involved in the cyclic dependency could initiate this operation simultaneously. Therefore, the distributed algorithm is sometimes better than the centralized algorithm and is sometimes worse than the centralized algorithm in terms of message complexity. It is better than the centralized algorithm since it does not communicate the entire local waits-for graph to the centralized server. (Also note that that there could be performance bottlenecks due to the use of the centralized server in the centralized algorithm.) However, the distributed algorithm could 124 Chapter 18 Distributed Coordination incur more messages when multiple sites are simultaneously exploring the existence of a cyclic dependency. 18.8 Consider the following hierarchical deadlock-detection algorithm, in which the global wait-for graph is distributed over a number of different controllers, which are organized in a tree. Each non-leaf controller maintains a wait-for graph that contains relevant information from the graphs of the controllers in the subtree below it. In particular, let SA, SB , and SC be controllers such that SC is the lowest common ancestor of SA and SB (SC must be unique, since we are dealing with a tree). Suppose that node Ti appears in the local wait-for graph of controllers SA and SB . Then Ti must also appear in the local wait-for graph of • Controller SC • Every controller in the path from SC to SA • Every controller in the path from SC to SB In addition, if Ti and Tj appear in the wait-for graph of controller SD and there exists a path from Ti to Tj in the wait-for graph of one of the children of SD , then an edge Ti → Tj must be in the wait-for graph of SD . Show that, if a cycle exists in any of the wait-for graphs, then the system is deadlocked. Answer: A proof of this can be found in the article Distributed deadlock detection algorithm which appeared in ACM Transactions on Database Systems, Volume 7 , Issue 2 (June 1982), ages: 187 - 208. 18.9 Derive an election algorithm for bidirectional rings that is more efficient than the one presented in this chapter. How many messages are needed for n processes? Answer: The following algorithm requires O(n log n) messages. Each node operates in phases and performs: • If a node is still active, it sends its unique node identifier in both directions. • In phase k, the tokens travel a distance of 2k and return back to their points of origin. • A token might not make it back to the originating node if it encounters a node with a lower unique node identifier. • A node makes it to the next phase only if it receives its tokens back from the previous round. The node with the lowest unique node identifies is the only that will be active after log n phases. 18.10 Consider a setting where processors are not associated with unique identifiers but the total number of processors is known and the processors are organized along a bidirectional ring. Is it possible to derive an election algorithm for such a setting? Answer: It is impossible to elect a leader in a deterministic manner when the processors do not contain unique identifiers. Since different Exercises 125 processors have no distinguishing mark, they are assumed to start in the same state and transmit and receive the same messages in every timestep. Hence, there is no way to distinguish the processors even after an arbitarily large number of timesteps. 18.11 Consider a failure that occurs during 2PC for a transaction. For each possible failure, explain how 2PC ensures transaction atomicity despite the failure. Answer: Possible failures include (1) failure of a participating site, (2) failure of the coordinator, and (3) failure of the network. We consider each approach in the following: • Failure of a Participating Site - When a participating site recovers from a failure, it must examine its log to determine the fate of those transactions that were in the midst of execution when the failure occurred. The system will then accordingly depending upon the type of log entry when the failure occurred. • Failure of the Coordinator - If the coordinator fails in the midst of the execution of the commit protocol for transaction T, then the participating sites must decide on the fate of T. The participating sites will then determine to either commit or abort T or wait for the recovery of the failed coordinator. • Failure of the Network - When a link fails, all the messages in the process of being routed through the link do not arrive at their destination intact. From the viewpoint of the sites connected throughout that link, the other sites appears to have failed. Thus, either of the approaches discussed above apply. 18.12 Consider the following failure model for faulty processors. Processors follow the protocol but might fail at unexpected points in time. When processors fail, they simply stop functioning and do not continue to participate in the distributed system. Given such a failure model, design an algorithm for reaching agreement among a set of processors. Discuss the conditions under which agreement could be reached. Answer: Assume that each node the following multicast functionality which we refer to as basic multicast or b-multicast. b-multicast(v): node simply iterates through all of the nodes in the system and sends an unicast message to each node in the system containing v. Also assume that each node performs the following algorithm in a synchronous manner assuming that node i starts with the value vi . • At round 1, the node performs b-multicast(vi ). • In each round, the node gathers the values received since the previous round, computes the newly received values, and performs a b-multicast of all the newly received values. • After round f + 1, if the number of failures is less than f , then each node has received exactly the same set of values from all of the other nodes in the system. In particular, this set of values includes all values from nodes that managed to send its local value to any of the nodes that do not fail. 126 Chapter 18 Distributed Coordination The above algorithm works only in a synchronous setting and the message delays are bounded. It also works only when the messages are delivered reliably.