G:2 exis | QUANTUM Series + Topic-wise coverage of entire syllabus S 4 i i = Y in Question-Answer form. & ae senestel + Short Questions (2 Marks) asyyrCONTENTS f-1 : CHARACTERIZATI\ ISTRIBUTED: UNIT: d ION OF DI SYSTEM (1-1 Bto 1-22 B) Introduction, Examples of distributed Systems, Resource sharing and the ‘Web Challenges. Architectural models, Fundamental Models. ‘Theoretical Foundation for Distributed System: Limitation of Distributed system, absence of global clock, shared memory, Logical clocks, Lamport'sé& vectors logical clocks. Concepts in Message Passing Systems: Causal order, total order, total causal order, Techniques for Message Ordering, Causal ordering of messages, global state, termination detection. UNIT-2:: DISTRIBUTED MUTUAL EXCLUSION (2-1 Bto 2-18 B) Distributed Mutual Exclusion: Classification of distributed mutual exclusion, requirement of mutual exclusion theorem, Token based and non token based algorithms, performance metric for distributed mutual exclusion algorithms. Distributed Deadlock Detection: system model, resource Vs communication deadlocks; deadlockprevention, avoidance, detection & resolution, Centralized dead lock detection, distributed dead lock detection, path pushing algorithms, edge chasing algorithms. UNIT-3 : AGREEMENT PROTOCOLS (3-1 B to 3-32 B) ‘Agreement Protocols: Introduction, System models, classification of ‘Agreement Problem, Byzantine agreement problem, Consensus problem, Interactive consistency Problem, Solution to Byzantine Agreement problem, Application of Agreement problem, Atomic Commit in Distributed Database system. Distributed Resource Management: Issues in distributed File Systems, Mechanism for building distributed file systems, Design issues in Distributed Shared Memory, Algorithm for Implementation of Distributed Shared Memory. : FAILURE RECOVERY IN DS (4-1 B to 4-21 B) Failure Recovery in Distributed Systems: Concepts in Backward and Forward recovery, Recoveryin Concurrent systems, Obtaining consistent Checkpoints, Recovery in Distributed Database Systems. Fault Tolerance: Issues in Fault Tolerance, Commit Protocols, Voting protocols, Dynamic voting protocols. UNIT-5 : TRANSACTIONS CONTROL (5-1 B to 5-32 B) Transactions and Concurrency Control: Transactions, Nested transactions, Locks, OptimisticConcurrency control, Timestamp ordering, Comparison of methods for concurrency control. Distributed Transactions: Flat and nested distributed transactions, Atomic Commit protocols, Concurrency control in distributed transactions, Distributed deadlocks, Transaction recovery. Replication: System model and group communication, services, highly available services, Transactions with replicated data. SHORT QUESTIONS (SQ-1 B to SQ-17 B) UNIT-: Fault - tolerant SOLVED PAPERS (2014-15 TO 2019-20) (SP-1 B to SP-19 B)Characterization of Distributed System rr CONTENTS Part-1 Part-2 Part-3 Part-4 Part-5 Introduction, Example ... 1-2B to 1-4B of Distributed System Resource Sharing and Web 1-4B to 1-9B Challenges, Architectural Models, Fundamental Models Theoretical Foundation for. -10B to 1-128 Distributed System : Limitations of Distributed System, Absence of Global Clock, Shared Memory Logical Clock, Lamport'’s ... and Vectors Logical Clocks .1-12B to 1-15B Concept in Message System ; Causal Order, Total Order, Total Causal Order, Techniques for Message Ordering, Causal Ordering of Messages, Global State and Termination Detection. . 1-16B to 1-20B 1-1B (CS-Sem.7)1-2 B (CS-Sem-7) Characterization of Distributed System | Introduction, Example of Distributed System. Questions-Answers Ae _ Long Answer Type and Medium Answer Type Questions Que 1.1. | What is a distributed system ? Describe the main characteristics of distributed system. Give two example of AKTU 2014-15, Marks 05 distributed system. ‘Answer Distributed system : LA distributed system is a system in which software or hardware components connected via communication network communicates and coordinates their actions only by passing messages. 2. Computers that are connected by a network may be spatially separated by distance. 3. Resources may be managed by servers and accessed by clients. Characteristics of distributed system : L_ Heterogeneity : Distributed system enables the users to access services and run application over a heterogeneous collection of computers and networks. 2. Openness : The openness of a computer system is the characteristics that determine whether the system can be extended and re-implemented in various ways. Concurrency : Concurrency in distributed system is use to help different users to access the shared resource at the same time. 4. Scalability : A system is described as scalable if it remains effective when there is significant increase in the number of resources and the 3. numbers of users. 5. Security : Security provides confidentially, integrity and availability of the information resources. Example of distributed system : 1. Internet : The Internet is a very large distributed system. It enables users to make use of services such as the World Wide Web, e-mail and file transfer.1-3B f Distributed System ICS Semin 2 Intranet: a. An intranet is a pri enterprise. . ; ; t b. An intranet is connected to the internet via router, which allows An intars inside the intranet to make use of services such as web gr e-mail. What are distributed systems ? What are significan, { distributed system ? eit ivate network that is contained within anf advantages and applications o! ‘Answer Distributed system : Refer Q. 1.1, Page 1-2B, Unit-1. Advantages of distributed system : 1 Data sharing : It allows many users to access to a common database, 2 Resource sharing : Expensive peripherals like color printers can be shared among different nodes (or systems). & Communication : Enhance human-to-human communication, e.g, email, chat. 4. Flexibility : Spread the workload over the available machines. Applications of distributed systems : ; 1. Telecommunication networks such as telephone networks and cellular networks. 2. Network applications, world wide web and peer-to-peer networks. 3. Real-time process controls aircraft control systems. 4, Parallel computation. Que 13 How the distributed computing system is better than parallel processing system ? Explain. |AKTU 2017-18, Marks 10) istributed computing system is better than parallel sag evita because of following advantages : Pi processing sy: 1 Economies : Micro : processors offer b el processing system. etter performance than parall 2. Speed:A distributed s: | 7 ystem may hav. ing power than parallel processing system, N°r* “Oval ComPUEINE PON 3. Reliability : 1¢ | ' cyotem ae a whlease ainaghines are downed, he distri performance. till survive with small degradation °1-4 B (CS-Sem-7) Characterization of Distributed System 4, Incremental growth : Computing power can be added in small increments. 5. Data sharing : Allow many users access to a common database. 6 Device sharing : Allow many users to share expensive peripherals. 7. Flexibility : In distributed computing workload can be spread over the available machines in the most cost effective way. Que 1.4. | What is distributed transparency ? Explainthe different types of distributed \..uusparencies. [AKTU 2017: 0 ‘Answer | Distributed transparency is the property of dis virtue of which the internal details of the distrib users. ‘Types of transparencies : 1. Access transparency : It enables local and remote resources to be accessed using identical operations. 2 Location transparency : It enables resources to be accessed without knowledge of their physical or network location. 3 Concurrency transparency : It enables several processes to operate concurrently using shared resources without interference between them. 4, Replication transparency : It enables multiple instances of resources to be used to increase reliability and performance without knowledge of the replicas by users or application programmers. 5. Failure transparency : It enables the concealment of faults, allowing users and application program to complete their tasks despite the failure of hardware or software components. 6 Performance transparency : It allows the system to be reconfigured to improved performances as load varies. PAR | Resource Sharing and Web Challenges, Architectural Models, Fundamental Models. + tributed databases by the ution are hidden from the -Questions-AnswersDistributed System 1-5 B (CS-Sem-7) (Qtie'1'5/9] How the resource sharing is done in distributed system ? Explain with an example. [Answer 1. Resource sharing is one of the major advantages which is obtained from distributed system. 2. Ina distributed system, the resources are enclosed within computers and can only be accessed from other computers by communication. 3. Each resource must be managed by a program that offers a communication interface enabling the resource to be accessed. 4. The program also helps the resources to be updated reliably and consistently. For example : 1. Theclient-server model provides an effective general purpose approach to the sharing of information and resources in distributed systems. 2. In this model, a client sends a request to a server for getting some services such as reading a block of a file. 3. The server executes the request and sends back a reply to the client that contains the result of request processing. ‘Que 1.6. | Discuss the major issue in designing a distributed system. AKTU 2017-18, Marks 10 “Answer — Major issues in designing a distributed system : J. Heterogeneity: a. Distributed system must be constructed from variety of different networks, operating systems, computer hardware’s and programming languages. b, Internet communication protocol mask the difference (heterogeneity) in networks and middleware can deal with the other differences. 2. Openness : Distributed system should be extensible i.e. to develop interface for the distributed system component so that they can be integrated to new extension of distributed system. 3. Security: a, Encryption can be used to provide adequate amount of shared resources and to keep sensitive information secret when it is transmitted in messages over a network. b. Denial of Services (DoS) attack is one of the big problems for security.\ 1-6 B (CS-Sem-7) Characterization of Distributed System 4 Scalability a. Scalability refers to the capabili s ity of increased service load. raainatiaccig tet mama b. _Itis inevitable that a distributed system will grow with time since it is very common to add new machines to take care of increased work load. Therefore, a distributed system should be designed to easily cope with the growth of nodes and users in the system 5. Fault avoidance : a. Fault avoidance deals with designing the components of the system in such a way that the occurrence of faults in minimized. b. Conservative design practice such as using high reliability ing the system’s components are often employed for improvi reliability based on the idea of fault avoidance. 6 Transparency : ‘Transparency aims to hide the details of distribution from the users. b. For an example, user or programmer need not be concerned with jts location or the details of how its operations are accessed by other ents, or whether it will be replicated or migrated. a compont Que 1.7. | Why is scalability an important feature in the design of distributed system ? Discuss some of the guiding principles for designing a scalable distributed system. AKTU 2014-15, Marks 10 Answer Scalability is important features in design of distributed system because: a. It helps the system to work efficiently with an increase in number of users. b. It increases the system performance by incorporating additional resources. Guiding principle for designing scalable distributed system : 1. Avoid centralized entities : Use of centralized entities should be av distributed system because = i Incentralized system, if centralize system will also fail. ii Capacity of the network that conn¢ gets saturated. In case of wide-area network sy: increases. a. cided in the design of ‘scalable .d entity fails then the entire ects the centralized entity stem, traffic in the networkDistributed System 1-7B (CS-Sem-7) b. Replication of resources and distributed control algorithms are frequently used techniques to achieve scalable system. f F c. Forbetter scalability, functionally symmetric configuration oe be used in which all nodes of the system should play equal role in the operation of the system. 2. Avoid centralized algorithms : : a. Acentralized algorithm is one that operates by collecting information , from all nodes, processing this information on a single node and then distributing the result to other nodes. ' : b. Time complexity of centralized algorithm may be very high which creates heavy network traffic and consumes network bandwidth. c. Therefore, in the design of a distributed operating system, only decentralized algorithm should be used. 3. Perform most operations on client workstations : a. If possible, an operation should be performed on the client’s workstation. b. This principle enhances the scalability of the system, since it allows graceful degradation of system performance as the system grows insize. c. Caching is a frequently used technique for the realization of this principle. 4. Controlling the cost of physical resources : As the demand for a resource grows, it should be possible to extend the system, at reasonable cost, to meet it. Que 1.8. | Discuss architectural models of distributed system. Answer. 1. An architecture model of a distributed system simplifies and abstracts the functions of the individual components of a distributed system 2. It also considers the placement of the components across a network of computers and the interrelationship between the components. 3. The main objective of these models is to make ij e the manageable, adaptable and cost-effective. system reliable, The two main types of architectural model are : a. Client-server model (Search engine) : i Fig. 1.8.1 illustrates the sim, processes interact with indivi, host compute oe they manage. ple structure in which client lual server processes in c separate ts in order to access the shared resouicee that1-8 B (CS-Sem-7) Characterization of Distributed System SS cmpuntt] al Servers: ii Thisis the architecture that is most widely employed. iii. Client-server model offers a direct and simple approach to the sharing of data and other resources. iv. Servers may acts as a client of other servers. For example, a web server is often a client of a local file server that manages the files in which the web pages are stored. b. Peer-to-Peer model: i In this architecture, all of the processes which are involved in a task play similar roles, interacting cooperatively as peers without any distinction between client and server processes. The Fig. 1.8.2 illustrates the form of a peer-to-peer application. iDistributed System 1-9 B (CS-Sem-7) iti, ICesse iii, Applications are composed of large pumbers ene pro ces a ‘running on separate computers an Per eats communication between them depends on app’ requirements. Explain the fundamental models of distributed system. & A 1. Fundamental models are based on the fale allow us to be more specific about their characteristics, failures an security risks that they might exhibit. 2. The purpose of a model is: 2. To make explicit all the relevant assumptions about the systems. b. Tomake generalizations concerning what is possible or impossible, given those assumptions. Following are the fundamental model : 1. Interaction models : a. It is concerned with performance of process communication channels and absence of global clock. b. Interaction model is further classified as synchronous and asynchronous system. ¢. _ Interacting process perform all of the activity in a distributed system. d. Each process has its own state, consisting of the set of data that it can access and update, including the variable in its program. e. The state belonging to each process is completely private. 2. Failure model: a. Inadistributed system both processes and communication channels may fail, so this model is capable of handling all the failure. b. The failure model defines and classifies the faults that occur in the system. ¢. — It provides a model to understand the effects of faults in the system. 3. Security model : a. a aa the ae threats to processes and communication channels in an open distributed system such as integri authentication, privacy ete. oe b. The architectural model Provides the basis for i Thesecurity ofa distributed system can be achi ii. Protection is described in terms of objects apply equally well to resources of ay open oe1-10 B (CS-Sem-7) Characterization of Distributed System Limitations of distributed systems are as follows = Absence of global clock : | in clock) is not L a b. In a distributed system, global clock (or comm: present. Suppose a global clock is available for all-the processes in the system. i In this case, two different processes can observe a global clock value at different instants due to unpredictable message transmission delays. Therefore, two different processes, may falsely perceive two different instants in physical time to be a single instant in physical time. Absence of shared memory : a. The computer in a distributed system do not share common memory, an up-to-date state of the entire system is not available to any individual process. It is necessary for reasoning about the system’s behaviour, debugging, recovering from failures, etc. A process in a distributed system can obtain a coherent but partial view of the system or a complete but incoherent view of the system. A view is said to be coherent if all the observations of different processes (computers) are made at the samp physical time. Because of the absence of a global clock in/a distributed system, obtaining a coherent global state of the system is difficult.Distributed System 1-11B (CS-Sem-7) Example: Local state dccalctete Initial state Message under transit (Not yet reached to B) — Rs. 50 —» SLA S2:B a. $1 records its local state (Rs. 450) just after debit (— 50) and S2 records its location (200) before receiving. b. If transit message is not taken care off Global state = Local state S1+ Local state S2 = 450 + 200 = 650 = Rs. 50 missing i.e., in coherent system Que 1.11. | What are distributed systems ? What are significant advantages, applications and limitations of distributed systems ? Explain with examples, what could be the impact of absence of global clock & shared memory. AKTU 201 6, Marks 10 Distributed systems : Refer Q. 1.1, Page 1-28, Unit-1, Significant advantages and applications of distributed systems : Refer Q. 1.2, Page 1-3B, Unit-1. Limitations of distributed systems: 1, Absence of shared memor}. 2. Absence of global clock. 3. The initial deployment cost ofa distributed system is very high.3-128 (cS-Sem-7) Characterization of Distributed System Impact of the absence of global clock : 1. tis difficult in a distributed system to reason about the temporal order "at events. It is difficult to design and debug algorithms for a distributed & compared to centralized systems, a distributed system as 3, Collecting up-to-date information on the state of the entire system in harder. Impact of the absence of shared memory : 1, Anup-to-date state of the entire system is not available to any of the individual processes. 2, Recovery from failure cannot be possible. For example : Refer Q. 1.10, Page 1-10B, Unit-1. conditions to be satisfied by Lamport logical clocks. If A and B represent two distinct events in a process and if A > B then C(A) < C(B) but vice-versa not true. Justify the statement. AKTU 2016-16, Marl [Answer Lamport logical clocks : A Lamport logical clock is a monotonically increasing software counter, whose value need bear no particular relationship to any physical clock. Following conditions are to be satisfied by Lamport logical clocks : 1 O Ifa and b are two events within the same process P; and a occurs before 6, then Cia) < Cio). Ita is the sending of a message by process P, and b is the receipt of that message by process P;, then C(a) < C,(b). Aclock C, associated with a process P; must always go forward, never backward. That is, corrections to time of a logical clock must always be made by adding a positive value to the clock, never by subtracting value.Distributed System 1-13 B (CS-Sem.7) Justification : Event ‘A’ casually aff nt ‘B'if A ~> B. Now, if 3 : ly affects eve: 7 then C(A) 6 then Cla) < C@). 2. However, the reverse isnot necessarily true if the events have occurred in different processes. 3. Thatis, ifa and b are events in different processes and C(a) < C(b), then a ->b is not necessarily true; event a and 6 may be causally related or may not be causally related. 4. Thus, Lamport’s system of clocks is not powerful enough to capture such situations. : For example: Py en 12 (1) (2) Space | Pp $a. Neon a (2) Time _» a, Fig, 1.13.1 shows a computation over Cle,,) < Cle,,) and Cle,,) < Cle,,). b. However, we can see from the related to event e,, but not to ¢,, three processes clearly, Fig. 1 that event e,, is causally c. Note that the initial clock values are-assumed ii assumed to equal 1. to be zero and d is1-14 B (CS-Sem-7) Characterization of Distributed System Que 1.14. | What are vector clocks d. In other words, in Lamport’s system of clocks, we can guarantee that if C(a) < C(b) then b-4 a, however we cannot say whether events a and } are causally related or not by just looking at the timestamps of the events. The reason for the above limitation is that each clock can independently advance due to the occurrence of local events in a process. f. The Lamport’s clock system cannot distinguish between the advancements of clocks due to local events from those due to the exchange of messages between processes. Therefore, using the timestamps assigned by Lamport’s clocks we cannot reason about the causal relationship between two events occurring in different processes by just looking at the timestamps of the events. ? Explain with the help of implementation rule of vector clocks, how they are implemented ? Give the advantages of vector clock over Lamport clock. AKTU 2014-15, Marks 05 Answer Vector clocks : a Implementation of vector clocks : L Vector clocks are used in a distributed system to determine whether pairs of events are causally related. Using vector clocks, timestamps are generated for each event in the system, and their causal relationship is determined by comparing those timestamps. Let ‘n’ be the number of processes in a distributed system. Each process P, is equipped with a clock C,, which is an integer vector of length n. Let a, b be a pair of events. Let Cla] [i] be the i element of the vector clock for the event a. C(a) is dominated by C(b) i.e., C(a) < C(b), if and only if the following two conditions hold : a Vi,Osi0, W, >0; W:=W,; send B (W,) to P; Rule 2: On receipt of B(DW), a process P having weight W does : W:=W+DW; If Pis idle, Pbecomes active; Rule 3: An active process having weight W may become idle at any time by doing : send C(W) to controlling agent ; W:=0; (Process becomes idle); Rule 4 : On receiving C(DW), the controlling agent having weight W takes the following actions : W:=W4+DWw; If W= 1, conclude that the computation has terminated.Distributed System 1-21B (C8.8em.7) Q.6. Q7. Q.8. What is a distributed system ? Describe the main characteristics of distributed system. Give two example of distributed system. Refer Q. 1.1. How the distributed computing system is better than Parallel processing system ? Explain. Refer Q. 1.3 What is distributed transparency ? Explain the different types of distributed transparencies. Refer Q. 1.4. Discuss the major issue in designing a distributed system. Refer Q. 1.6. . Why is scalability an important feature in the design of distributed system ? Discuss some of the guiding principles for designing a scalable distributed system. Refer Q. 1.7. What are distributed systems ? What are significant advantages, applications and limitations of distributed systems ? Explain with examples, what could be the impact of absence of global clock & shared memory, Refer Q. 1.11. Discuss the limitations of Lamport’s logical clock with suitable example. Refer Q. 1.13. What are vector clocks ? Explain with the help of implementation rule of vector clocks, how they are implemented ? Give the advantages of vector clock over Lamport clock. Refer Q. 1.14.4-22 B (CS-Sem-7) Q.9. What do you mean by casual o: Fv Q.10. aS Qi. Aas | Characteritation of Distributed System dering of messages ? If process P sends two message m, and m, to another process , what problems may arise if the two messages are not received by recipient Q, in the order they were sent by process P. Develop an algorithm which guarantees the casual ordering of message in distributed system. Refer Q. 1.15. Give the Chandy-Lamport’s global state recording algorithm. Refer Q. 1.18. What is termination detection in distributed system ? Explain any algorithm for termination detection. Refer Q. 1.19. si ©©© |Distributed Mutual Exclusion “CONTENTS: Distributed Mutual ..... Exclusion : Classification of Distributed Mutual Exclusion, Requirement of Mutual Exclusion Theorem Token Based and ... Non-Token Based Algorithm, Performance Metric for Distributed Mutual Exclusion Algorithm Distributed Deadlock .... Detection : System Model Resource vs Communication Deadlocks, Deadlock Prevention, Avoidance, Detection & Resolution Centralized Deadlock ... Detection, Distributed lock Detection, Path- Pushing mee iH 8 Algorithms © x .. 2-8B to 2-10B 2-12B to 2-18B__ wy2-2 B (CS-Sem-7) istri Distributed Mutual Exclusion istributed Mutual Exclusion : Clas. Z it d fi c + Classification of Distribui i Exclusion, Requirement of Mutual EanO Tene | - Questions-Answers wer ‘Type and Medium Answer Type Questions {e2.1.. | What do you mean by mutual exclusion in distributed ystem ? What are requirements of a good mutual exclusion gorithm ? [AKTU 201415, Marks 05. oR ate the classification of distributed mutual exclusion. What is irement of mutual exclusion theorem ? | Mutual exclusion is a problem that arises if the process relies on a ‘common resource that can be used only by one process at a time. Concurrent access to shared resources is prevented. Mutual exclusion algorithm guarantees that only one request accesses the critical section (CS) at a time. : ‘There are two classes of distributed mutual exclusion algorithm : a. Non-token based algorithm b. Token based algorithm "Requirements of good mutual exclusion algorithm : “Freedom from deadlocks : Two or more sites should not endlessly r wait for messages that will never arrive. 2 Freedom from starvation : A site should not be forced to wait indefinitely to execute CS i.e., every requesting site should get an opportunity to execute CS in a finite time. a Fairness: Fairness dictates that requests must be executed in the order in which they arrive in the system. 4. Fault tolerance : A mutual exclusion algorithm is fault-tolerant if in the wake of a failure, it can recognize itself so that it continues to function without any (prolonged) disruptions.Distributed System 2-3B (CS.Sem.7) (Que2a)” How distributed mutual exclusion is different from ata mutual exclusion in single-computer a 2 \ ia 1 Shared memory does not | Shared memory exists. exist. 2. Both shared resources and | Both shared resources and the the users may be distributed. | users are present in shared memory. 3. | Mutual exclusion problem is | Mutual exclusion problem is solved solved by using message |by using shared variables passing approach. approach i.e., semaphores. > What is mutual exclusion ? Describe the requirements of mutual exclusion in distributed system. Is mutual exclusion problem more complex in distributed system than single computer system ? Justify your answer. “AKTU 2017-18) Marks 10] [Answer Mutual exclusion and its requirements : Refer Q. 2.1, Page 2-28, Unit-2. Yes, the problem of mutual exclusion becomes more complex in distributed system as compared to single computer systems because of absence of both shared memory and a common physical clock and because of unpredictable message delays. So, considering these factors, it is virtually impossible for a site to have correct and complete knowledge of the state at the system.2-4 B (CS-Sem-7) istril Distributed Mutual Exclusion a i 2 | What is token based algorithm and non-token based algorithm in distributed system ? Explain with example ee Token based algorithm : L Tete ean eee a unique token is shared among all sites. aa oken then it is allowed to enter its CS (Critical ection). : 2. Token based algorithms use sequence numbers instead of timestamps. 3. Every request for the token contains a sequence number and the sequence number of sites advances independently. A site increment its sequence number counter every time when it makes a request for the token. Example: Suzuki-Kasami algorithm : In the Suzuki-Kasami’s algorithm, if a site attempting to enter the CS but does not have the token, it broadcasts a request message for the token to all other sites. Non-token based algorithm : 1. Innon-token based mutual exclusion algorithms, a site communicates with a set of other sites to arbitrate who should execute the CS next. 2. Non-token based mutual exclusion algorithms use timestamps to order request for the CS and to resolve conflicts between simultaneous requests for the CS. Each request for the CS gets a timestamp and small timestamp requests have priority over larger timestamp requests. Each process freely and equally competes for the right to use the shared resource; requests are arbitrated by a central control site or by distributed agreement. Example: Lamport’s algorithm : In Lamport’s algorithm, Vi:1 Ex’ which contains the node ‘Ex’ the site transmits them in string form ‘Ex T,, T,, Ex’ to all other sites where a subtransaction of T,, is waiting to receive a message from the subtransaction of 7, at this site. The algorithm reduces message traffic by lexically ordering transaction and sending the string ‘Ex, T,, T,,Ty Ex to other sites only if7, is higher than 7, in the lexical ordering. Also, for a deadlock, the highest priority transaction detects the deadlock. Que 2.17, | Discuss various centralized deadlock detection algorithms. Answer Various centralized deadlock detection algorithms are : 1, Completely centralized algorithm : a. It is the simplest type of deadlock detection algorithm, wherein a designated site called the control site, maintains the WFG (Wait for graph) of the entire system and checks it for the existence of deadlock cycles, b. All sites request and release resources (even local resources) by sending request resource and release resource messages to the control site, respectively, c When the control site receives a request resource or a releasé resource message, it correspondingly updates its WFG.9-16 B (CS-Sem-7) Distributed Mutual Exclusion a. Thecontrol site checks the WFG for deadlocks whenev: edge is added to the WFG. ir request 2 The Ho-Ramamoorthy algorithms : Ho and Ramamoorthy gave two centralized deadlock detection algorithms called t hase i ‘wo-pl and one- phase algorithms. 2 . a. The two-phase algorithm : i Inthe two-phase algorithm, every site maintains a status table ie contains the status of all the processes initiated at that le. : ik Periodically, a designated site requests the status table from all sites, constructs a WFG from the information received, and searches it for cycles. ii. If there is no cycle, then the system is free from deadlocks, otherwise, the designated site again requests status tables from all the sites and again constructs a WFG using only those transactions which are common to both reports. iv. If the same cycle is detected again, the system is declared deadlocked. b. The one-phase algorithm : is‘ The one-phase algorithm requires only one status report from each site; however each site maintains two status tables; a resource status table and a process status table. ii The resource status table at a site keeps track of the transactions that have locked or are waiting for resources stored at that site. iii The process status table at a site keeps track of the resources locked by or waited for by all the transactions at that site. Periodically, a designated site requests both the tables from every site, construct a WFG using only those transactions for which the entry in the resource table matches the corresponding entry in process table, and searches the WFG for cycles. Ifno cycle is found, then the system is not deadlocked, otherwise a deadlock is detected. i Explain various hierarchical deadlock detection re 2.18.) algorithms. ly.arranged in hierarchical fashion, In hierarchical algorithms, sites are logicall is dlocks involving only its children and a site is responsible for detecting deat sites.Distributed System — 2-17 B (CS-Sem.7) Various hierarchical deadlock detection algorithms : 1. The Menasce-Muntz Algorithm : a. Inthis algorithm all the controllers are arranged in tree fashion, b. The controllers at the bottom-most level (leaf controllers) manage resources and others (non-leaf controllers) are responsible for deadlock detection. c. Whenever a change occurs in a controller’s TWF (Transa) graph due to aresources allocation, wait or release, itis propagated to its parent controller. d The parent controller makes changes in its TWF graph, searches for cycles, and propagates the changes upward, if necessary. e. Anon-leafcontroller can receive up-to-date information concerning the TWF graph of its children continuously or periodically. 2 The Ho-Ramamoorthy algorithm : * a Inthis algorithm, sites are grouped into several disjoint clusters. b. Periodically, a site is chosen as a central control site, which dynamically chooses a control site for each cluster. c. The central control site requests from every control site their intercluster transaction status information and wait-for relations. Control site +d. Asaresult, a control site collects status table from all the sites inits cluster and applies the one-phase deadlock detection algorithm detect all deadlocks involving only intracluster transactions.2-18 B (CS-Sem-7) e. Distributed Mutual Exclusion Then, it sends intercluster tr: i s ansacti i i i for relations to the central control = aaa a The central site split the i: intercluster information i i constructs a system WFG, and searches it for cycles. a Thus, a control site detects all deadlocks located in its cluster, and the central control site detects all intercluster deadlocks. ; ‘STIONS © What do you mean by mutual exclusion in distributed system ? What are requirements of a good mutual exclusion algorithm ? Refer Q. 2.1. What is token based algorithm and non-token”based algorithm in distributed system ? Explain with example. Refer Q: 2.4. Differentiate between token and non-token based algorithms. Refer Q. 2.5. Explain the Ricart-Agrawala algorithm for mutual exclusion. Mention the performance of this algorithm. Refer Q. 2.8. Discuss the performance metric for distributed mutual exclusion algorithms. Refer Q. 2.9. Classify the deadlock detection algorithms. Describe the path-pushing deadlock detection algorithm. Refer Q. 2.16. What are the deadlock handling strategies in distributed ii ization for distributed file system ? What is control organization t deadlock detection ? Discuss an algorithm which can remove phantom deadlock. Refer Q. 2.14. ©oOO: Agreement Protocol : Introduction, System Models : Classification of Agreement .. Problem, Byzantine Agreement Problem, Consensus Problem, Interactive Consistency Problem, _ Solution to Byzantine Agreement Problem : Application of Agreement . Protocol, Atomic Commit in Distributed Database System ta 2. Distributed Resource Management : Issues in Distributed File System, Mechanism " For Building Distributed File - System Design Issues in Distributed Shared Memory ..3)) +.) ‘Algorithm F, For Implementation ‘of Distributed Shared Memory 3-1B (CS-Sem-7)3-2B (CS-Sem-7) Agreement Protocols ies Eanoaeeh \ Agreement protocol : 7 2. 3. Ques2. | Process of sending and reaching the agreement to all sites is called agreement protocol. Indistributed system, the agreement protocols are very much useful for error free communication among various sites. ; ° In distributed system, the chances of the faulty processors are more. The faulty processor may lead to wrong message communication, no response for a message ete. ‘Also the presence of faulty processor is not known to the non-faulty processors. So, the non-faulty processors do not restrict the message transfer to the faulty processors. ‘The agreement protocols allow the non-faulty processors to reach a common agreement in the distributed system, whether there are other processors which are faulty or not. ‘The common agreement among the processors is taken through the agreement protocol. What is agreement protocol ? Discuss the general system model where agreement protocols are used. ‘Answer — Agreement protocol : Refer Q. 3.1, Page -2B, Unit-3. System model : Following are the system models where agreement protocols are used : 1 2. If there are n processors in the distributed system, then only m processors out of them may be found as faulty processors. Every processor in the system is free to communicate with other processors in the system due to their logical connections with each other.Distributed System 5-SB(C8Sem-7) 3. Areceiver processor always knows the identity of the sender processor of message. : 4. The communication medium is reliable (i.e., it delivers all messages -without introducing any errors) and only processors are prone to failures, Resa] Discuss various aspects for recognizing the agreement Protocol. Following are various aspects to consider for recognizing the agreements in distributed system : 1. Synchronous and asynchronous computations : a Inasynchronous computation, processes in the system run in lock step manner, where in each step, a process receives messages, performs a computation and sends messages to other processes, b. " In synchronous computation, a process knows all the messages which it expects to receive in a round. “ec. Amessage delay or a slow process can slow down the entire system or computation. d= Inanasynchronous computation, processes in the system does not proceed in lock step. e. Aprocess can send and receive messages and perform computation at any time. : 2 Process failure model : a. The processor failure is the most common system model considered in finding the agreement protocol. b, A precessor can fail in three models : i Crash fault : In a crash fault, a processor stops functioning and never resumes operation. ii, Omission fault : In an omission fault, a Processor “omits” to send messages to some processors, iii. Malicious fault : In a malicious fault, a processor behaves randomly and arbitrarily. 3. Authenticated and non-authenticated messages : a. In an authenticated Message system, a (faulty) processor cannot forge a message or change the contents of a received message. ». A processor can verify the authenticity of a received message. ¢. Anauthenticated message is also called a signed message. In a non-authenticated message system, a (faulty) processor can forge message and claim to have received it from another processor3-4 B (CS-Sem-7) Agreement Protocols or change the contents of a received message before it relays the message to other processors. . e. Aprocessor isnot able to verify the authenticity ofa received message. f. Anon-authenticated message is also called an oral message. g. Itis easier to reach agreement in an authenticated message system because faulty processors are capable of. doing less damage. 4, Performance aspects : a. The performance of agreement protocols is generally determined by the following three metrics : i. ‘Time : Time refers to the time taken to reach an agreement under a protocol. . ii. Message traffic : Message traffic is measured by the number of messages exchanged to reach an agreement. iii, Storage overhead : Storage overhead measures the amount of information that needs to be stored at processors during the execution of a protocol. What are agreement protocols ? Explain Byzantine agreement problem, the consensus problem and interactive consistency problem. Fe (Anewer | Agreement protocols : Refer Q. 3.1, Page 3-2B, Unit-3. Classification of agreement protocol : 1. The Byzantine agreement problem : a. In the Byzantine agreement problem, an arbitrarily chosen processor, called the source processor, broadcasts its initial value to all other processors.Distributed System 3-5B C8sea., b. Asolution to the Byzantine agreement problem should ‘hal, following objectives : i. Agreement: All non-faulty processors agree on the same Valu ii. Validity : Ifthe source processor is non-faulty, then. the coms " agreed upon value by all non-faulty processors should be the initial value of the source. jii. Termination : Each non-faulty processor must eventually decide on a value. 2 Consensus problem : a. In the consensus problem, every processor broadcasts its initia, value to all other processors. b. Initial values of the processors may be different. ¢. A protocol for reaching consensus should meet the following conditions : i, Agreement: All non-faulty processors agree on the same single value. . ii. Validity : If the initial value of every non-faulty processorisv, then the agreed upon common value by all non-faulty processors must be v. iii.Termination : Each non-faulty processor must eventually decide on a value. 3. The interactive consistency problem : a. _Intheinteractive consistency problem, every processor broadcasts its initial value to all other processors. b. The initial values of the processors may be different. ¢. A protocol for the interactive consistency problem should meet the following conditions : i, Agreement : All non-faulty processors agree on the same vector (U4, Vay vss Up). ii, Validity : If the i" processor is non-faulty and its initial value is v,, then the i value to be agreed on by all non-faulty processors must be v,. Termination : Each non-faulty processor must eventually decide on different value of vectors. ue What are agreement protocols ? Explain Byzantine agreement problem, the consensus problem and interactive consistency problem. Describe Lamport-Shostak-Pease algorith™: AKTU 2014-15) Marks 10