a CONTENTS el KCS 077 : Distributed Systems UNTT:1: CHARACTERIZATION OF DISTRIBUTED 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 Distted Syste Limitation of Distributed system, absence of global clock, shared memory, ; ectoe local locks, ed memory, Lagi clociaLamport's 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 rnon token based algorithms, performance metric for distributed mutual exclusion algorithms. Distributed Deadlock Detection: system model, resource Vs communication deadlocks, deadlock prevention, avoidance, detection & resolution, ‘centralized dead lock detection, distributed dead lock detection, path pushing + algorithms, edge chasing algorithms. AGREEMENT PROTOCOLS (8-1 Bto3-32B) “Agreement Protocols: Introduction, System models, classification of /‘ngreement 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 Diatributed Shared Memory, Algorithm for Implementation of Distributed Shared Memory. FAILURE RECOVERY IN DS (4-1 B to 4-21 B) ‘ilure Recovery in Distributed Systems: Concepts in Backward and Forward recovery, Recovery in Concurrent systems, Obtaining consistent Checkpoints, Recovery in Distributed Database Systems. Fault Toleranet: Cases Fault Tolerance, Commit Protocols, Voting protocols, Dynamic voting protocols. TRANSACTIONS CONTROL (5-1 B to 5-32 B) Y snsactions and Concurrency Control: Transactions, Nested transactions, Locks, OptimisticConcurrency control, Timestamp ordering, Comparison of methods for concurrency control. Diueibuted Transactions: Flat and nested distributed transactions, Atomic Commit protocols, Concurrency control in distributed transactions, Distributed deadlocks, Transaction recovery: Replication: System model and group communication, Fault - tolerant services, highly available services, Transactions with replicated data SHORT QUESTIONS (SQ-1 B to SQ-17 B) SOLVED PAPERS (2014-15 TO 2020-21) (SP-1 B to SP-23 B) Scanned with CamScannerwww.askbooks.net *AKTU Quantums :Toppers Notes *Books *Practical Files *Projects *IITJEE Books www.askbooks.net All AKTU QUANTUMS are available Preeneey Ser * Your complete engineering solution. * Hub of educational books. Ce eee eT te ere et ee eta DP RU Om Cur MCE CEL Cy RCE Ce CR Aree ee UE oe Ck eC au CULL e 2. We don't intend to infringe any copyrighted material. 3. If you have any issues with any material on this PO i eet om cece 4. All the logos, trademarks belong to their respective owners.Characterization of Dintributed System 1-2 (C8-8em-7) PAR’ Introduction, Example of Distributed System. Characterization of Distributed System Long Answer Type and Medium Answer Type Questions distributed system ? Describe the main Que td. | What it characteristics of distributed system. Give two example of siecle Answer Distributed eystem : 1. A distributed system is @ system in which software or hardware ‘components connected va communication netwack communicates and” CONTENTS Part-1: Introduction, Example of Distributed System 14B to 1-98 Resource Sharing and Web Part? = Ghatenges, Architectural Sede Fundamental Models ordinates their actions only by pasting me «_Theoretial Foundation fof nwo A108 (0 1-188 ther ati — Parts Mart yen : Linialons 2 Computers that are connected bya network may be spatially idistance, separated 4. Resources may be managed by serves and secesed byeients. of Distributed System, Absence of Global Clock, Shared Memory vw 1-12B to 1-18B Characteristics of distributed system : 11. Heterogeneity : Distributed system enables the users to access services and run application over a heterogeneous collection of computers and Part-4 + Logical Cock, Lamport and Vectors Logieal Clocks ae v~ 1H16B to 1-208 2 Openness : The openness ofa computer system isthe characteristics that determine whether the system canbe extended and reimplemented Part-5 : Concept in Message System Causal Order, Total Order, Total Ceusal Order, Techniques for Message Ordering, Causal Ordering of Messages, Ghbal State and Termination Detection. in various ways “8 Concurrency : Concurrency in distributed system is use to help diferent users to access the shared resource atthe same time. A system is described as scalable if it remains effective xis significant increase inthe number of resources and the numbers of users. © Security : Security provides confidentially, integrity and availability of the information resources. Example of distributed system: 1. Internet : The Internet isa very large distributed system. Itenables users to make use of services such as the World Wide Web, e-mail and 1-1B(C8-Sem-7) file transfer. ‘Scanned with CamScannerDistributed System ISB CS Seme7) TF _40 (C8-8em-7) Characterization of Distributed of item 2 Intranet : 3 4. Incremental grovth Computing power can - a An intranet is a private network that is contained within aq increments, a ees . & Data sharing: Allow many users access to a common d ; ' atabase. 1k Anintrane is connected to the internet vi router, which allows J gq Doviee sharing: Allow many users toshareener noe ‘he users inside the intranet to make use of services such as web op Flexibility : In distri : oan 1 in distributed computing workload can be spread over c the available machines inthe most cost effective way, Quer | What are distributed systems ? What are significant Gara] ae ved _ ‘nea advantages and applications of distributed system ? . tributed transparency ? Explain the different ARTU 2018-19, Marke] types of distributed transparencies. ‘Answer Answer i 4 Distributed transparency is the property of distributed databases Distributed system : Refer Q. 1.1, Page 1-2B, Unit-1. tirtu of which the internal details of the distribution are biddes othe Advantages of distributed system : users. 1. Data sharing :It allows many users to access to acommon database, |] TYP¢s of transparencies : : cae i i |. Access transparency : It enables local and remote resources to be 2 Resource sharing : Expensive peripherals like color printers canbe [J 1 ans) 7 shared among different nodes (or systems). 7 ae re iteniieal _— i pate ae nl Location transparency It enables resources tobe accessed without S Communication : Enhance human-to-human communication, eg, knowledge oftheir physical or network location. email. chat. ‘4 Flexibility : Spread the workload over the available machines, Se ae dared canna euaet iicascne ites Applications of distributed systems: them. 1 Telecommunication networks such as telephone networks and cellular J) 4 Replication transparency :It enables multiple instances of resources tobe used to increase rebaility and performance withost knowledge of networks, 2 _ Network applications, worldwide web and peer-to-peer networks. the replica by users op 3. Real-time process controls airraft control systems Failure transparency :It enables the concealment of fults allowing 4 ee users and application program to complete their tasks despite the failure ofhardwvare or software components SETS] How the distributed computing system is better than |) 6 Performance transparency Itallowsthe system tobe reconfigured toimproved performances as load varies. parallel procesing tem? Eephin, [RETURNED] fe oom Distributed computing system is better than parallel processing system because of following advantages pel " 1. Economics : Microprocessors offer better performance than parallel processing system. 2 Speed :A distributed system may have more total computing power than parallel processing system. . ‘& Reliability : If some of the machines are downed, the distributed system as a whole can still survive with small degradation of performance. Scanned with CamScanneri araen ee aes Distrib a —— jadone in distributed tystem GQuets. | How the resource sharing Explain with an example. al L FReanurce sharing is one of the mor" Each resource must be managed by & Eee ato} in re rea . eeu = —- one vente mine Rae ler ere saree ein sees ad a ‘The serverexecutes the request and sends back a reply tothe client rect deaeseaee Ques. | Discuss the major issue in designing a system. ‘Answer ‘Major issues in designing a distributed system : 1. 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. Openness: Distributed system should be extensible ie. to develop interface forthe distributed system component so that they ean be integrated to new extension of distributed system. A Security: a. Encryption can be used to provide adequate amount of shared resources and to keep sensitive information secret when itis transmitted in messages over a network. Denial of Services DoS) attacks one ofthe big problems for security. cdvantages which is obtained .sare enclosed within comy by communicat a 4. Sealaiity Scalability refern tothe capability of a system to adapt to sreased service load. " 1 Ininovtbe that dite system il ero thine ict tn very common to add new machines to ake cre of creased stork lad Therefre, a itibted rate shoal be designed to aly cope with the growth of nodes and users inthe system 5 Fault avoidance: Fault avoidance dese wth desing the component ofthe tem ineucha may thatthe occurrence af ft sunimie Conservative design practice auch a8 using high reliability commponent are eten employed for improving the ayer’ Felbltybasedonthe eaof fal avedance Transparency + a Transparency sins to hide the details fist fom the ere bh Foran example, wero programmer need not be concerned with Heloaton rte details eho ts operations ace accessedby oer ompancnts or whether it wile repitedormirated Jie 177] Why is scalability an important feature inthe design of distributed system ? Discuss some of the guiding principles for ‘designing a scalable distributed system. ‘ane Scalability is important because: Ithelps the system to work efficiently users. bh. Trinereases the system performance by incorporating additions) resources. Guiding principle for designing scalable distributed system: 1. Avoid centralized entities: ‘a. Use ofcentralized entities shouldbe avoided inthe design of sealable distributed system because teoentralied system, ifeentralized entity fas then the entire system will also foil Capocity ofthe network that connets the centralized entity gets saturated. In case of wide-area network system, increases. TARTU 2014-15, Marks 10) features in design of distributed system a swith an increase in number of traffic in the network Scanned with CamScanner11 (C8-Sem-7) ted Sete? 4 control algorithms are on of ert eae freon we ie rally netric configuration should. Foe tter wali fe em sould pay ena role vr hl nodes of sewed te ser tralized algorithms + + pean or fon a rae erent See dabuting St et loritm mayb er hig % Taecenset fer panes network Dandi, aaee ea fhe design ofa distributed operating system, only ert a he Piceeed dana towed Pesan pertinent workstation re rmants mo peraten sdb petra o the ct cite ‘the syste it allows ste eabiy tthe tn sicitallos ie Sal fqucmerrmnce oie ase Gr Cachgien equ ed tigre retin of thi “s 4 controling ot pyc anuee A the domand a ‘clumped edd pniioenendthe em, reno cost, tomeet it. QaeTAD] Discuss architectural models of distributed system. vy Replica symm com by collecting information ‘single node and 1 Anarchitecture model ofa distributed system simplifies and abstracts the functions ofthe individual components of distributed system 2. Italso considers the placement ofthe components aeross a net components across a network of 4 Supers andthe nterclatinsip between the components tain objective ofthese modes is to make the system rel ‘manageable, adaptable and cost-effective. ent ag 4. Thetwomsintypesof architectural model are: 4% Client-server model (Search engine) : { Fig. 183 illustrates the i illustrates the simple structure in which elien ener with individual erverrceteinsoparte they amputers in order to acces the shared resource thet 1-8 (C8-Sem-7) Characterization of Distributed System Invocation Invocation ‘Server Result Client Tar compote ‘Thisis the architecture that is most widely employed. Client-server model offers.a direct and simple approach to the sharing of data and other resources. Servers may acts asa client of other servers. For example, aweb servers often aclient of local file server that manages the files in which the web pages are stored. _2e Peer-to-Peer model: . In this architecture, all ofthe processes which are involved in a task play similar roles, interacting cooperatively as peers without any distinction between elient and server processes i The Fig. L82illustrates the form ofa peer-to-peer application. : Scanned with CamScanner= Dots Communication between them depends on appl, requirements Gee] Explain the fundamental models of distributed, ae the fundamental fe lamental models are based on the fundamental propertie 1 Biante te mere peie abut thee charctristcy, failure security risks that they might exhibit 2 The purpose ofa made is | 4. Tomake explicit allthe relevant assumptions about the 1h Tomake geeralizationconcering whats possible or impogsbl, sven thore assumptions Following ae the fundamental model : 1. Interaction models IL ix concerned with performance of process communteath channels and absence of global clock. a Interaction model is further classified us aynchronoun ang ‘synchronous nylon, a «Interacting proces performallofthe activity in adit ays, 4 Each process has ita own stale, consiting af the at of data that ft «an accoes and update, eluding the variable in te program, ‘The late belonging to each proces completely private, 2 Fallure model 1 Inadtatrtutedayatem both procnaon nnd communk hprocemes and communication channola 4, Reve themeel explo hang ali aur. b The fallure model denen and claa Frclle model define wa closon the fale that occur in the © Mprovden wel oun 4 Kecurlty model * Heston th psi tinea channels tn an open diate sutestcation piomy ote 1 Thomrehiteet wleraland (ho effeetxot faults ln the aystom, slo our erly mel “edeltdelontnceeneirn algae ne thoi Intoraeti naan unauthorized access, oo f Preeti in dened Interna otobjoct, alt ong ha *HAr equally well toroanucenotny eae the concopte 1-10 8 (C8-Som-7) Characterization of Distributed System ‘Theoretical Foundation for y of Distributed System, Absence of ‘Clock, Shared Memory. Jaold0.] Explain the limitations of distributed aystem with example. (AKTU 2016-19, Marks 10) ‘Anawor Limitations of distributed systema are as follows: 1, Absence of global clock : distributed system, global clock (or common clock) in not a In present, b. Suppowe a global clock I available for all the processes in the sytem, : In thin cane, two different procennes enn observe a labal clock difforent instante duo to unpredictable mensage tranninnion dolays, a fore, two different procennon, may faleoly porceive tw ho mingle instant in physical nf Iontante in phyaleal tne 2 Abnonce of ahared memory 4. Tho computor {nw dintributed ayntom do not share common poate ntato of the entire nyatom te not available fnocomnary for reawontoy about the aysten's behaviour, dolar, recovering fron faluron te A procoms ina distributed aynton can obtatn a cohort but partial View of thomyatem or a complete hut incabwrent view of the ayaten, 4A viow in anid to bw coherent {Fall the olworvations uf different utorn) are mado at (ho wamp phyaical time, une of the abnor of w ylobal clock iy « liarituted ayaton, oblainiog a cohoront global atate of the ayatous ie itil, b Scanned with CamScannerrpotsitutel yen, ssa! Aoi ata Sab wa ign cong unter eat ta st reached to 1) ska 820 , 10d St records it eal stato (Rs 460 just after debit (— 60) records location (200) before receiving. 1 Atranst manag nat taken care off Glob atato» Local state 81+ Local state S2 480-4200 + 650 Ra, 60 missing ce. in coherent ay Weer] What aro distetbuted aystems 7 What are advantages, applications and limitations of distributed sy Explain with examples, what could be the Impact of absence of lock shared memory. Tanewer | Dt systems: Refer Q. 1.1, Page 1-2B, Unite. cant advantages and ions Refer. 12. Pag 1a Ua none of etetbuted Limitations of distributed systems: 1 Absence of shared memery. 2. Absence of global clock, 4% Theinitial deployment eng ofa distributed system is very high. bueno of qlobal elook 1 Ieindlficult in aditrated nyater to ronson about the tomporal order at ovents, Impnot of the absence of ahared memory 1 1, Anup-to-date state of the entire rystem in not available to any of the inxlividual praconson, Rocovory {lure cannot be porsible, For example: Rofor Q. 1.10, Page 1=10B, Unit-1, - Ez | Logical Clock, Lamports an i ab Que 12, | What re Lamport loxteal clocks ? List the Important conditions to be satisfied by Lamport logical elocks. If A and B represent two diatinet events in a process and if A > B then CUA) < CUB) but vice-versa not truc. Justify the statement Lamport logical clocks + {A Lamport logial clock is « monotonically increasing software counter, ‘howe Value need bear no particular rolationship to any physical clock. Following conditions aro to be satisfied by Lamport logical clocks: Ifa and are two events within the same process P, and a occurs before , then Ca) < Cb. Ia ia the sending of a message by process P, and bis the receipt of that message by process P, then Ca) < C{b). 3. Aclock C, associated with a process P, must always go forward, never backward. That is, corrections to time ofa logical clock must always be made by adding a positive value to the clock, never by subtracting value. Scanned with CamScannerstributed System Justi ‘cation : Event 4’ casually affects event B'ifA — B i; REECUY a, however we eannat $2 sg Sarena elated no by jt loin a he timestamps ofthe events ‘e. The reaton for the above limitation is that each clock can ” independently advance due to the occurrence of local event proces. i canne between the The Lamport’s clock system cannot distinguish a ‘advancements of clocks due to local events from those due to the exchange of messages between processes. fg Therefore, using the timestamps assigned by Lamport's clocks we Cannot reason about the causal relationship between two events ‘ccurring in different processes by just loking atthe timestamps ofthe events. WESTIE] What are vector clocks ? Explain with the help of station rule of vector clocks, how they are implemented ? Give the advantages of vector clock over Lamport clock. [ATU 20IE15, Marks 05) raver Vector clocks: 1 Yeetor clocks are used in a distributed system to determine whether pairs of events are causally related. 2 Using vector clocks, timestamps are generated for each event in the system, and their eausal relationship is determined by comparing those timestamps. Implementation of vector clocks : 1. Let'n’be the numberof processes in a distributed system. Each process P is equipped with a clock C,, which isan integer vector of length n- 2 Lcta,b be a pair of events. Let Clalli] be the / clement of the vector lock for the event a. Gia)s dominated by CW)i«, 1a)< C1) fend ony ifthe felowing two ‘conditions hold : * a & Yi,0sisn—1:Clallil 6. Characterization of Distributed System 1-16 B (CS-Sem-7) [REET] Wnat do you mean by casual ordering of messages ? If process P sends two message m, and m, to another process Q, what problems may arise ifthe two messages are not received by recipient Qin the order they were sent by process P. Develop an algorithm Shich guarantees the casual ordering of message in distributed system. (AKTU 2015-16, Marks 10] oR Discuss causal ordering of messages. Give one algorithm which ean order the messages according to causal dependencies. [ARTO 2016-17, Maris Casual ordering of message : The casual ordering of message deals with the concept of maintaining same casual relationship that holds among “message send” event with corresponding “message receive” event. Problem: Ifthe two messages m, and m, are not received by recipient Q in the order they were sent by process P, this means message delivery will nt be causal Algorithm : Schiper-Eggli-Sandoz algorith Instead of maintaining a vector clock based on the number of messages sent toeach processes, the vector clock for this algorithm can be incremented at ‘any rate and has no additional meaning related to the number of messages ‘spent to the processes. Sending a message TAllmessages are timestamped and sent out with alist of ll timestamps of messages sent to other processes,JoUUBOS LEY Yim PouUeoS siveredifthereis predate svered, performing the following stePt red message in the ist = vertined for other processes t0 essage canbe del ERTTET explain the slorithmforcasualondering of message 2 distributed system. “Aaower] Algorithm for casual ordering of message in a. Birman-SchiperStephenson algorjthm ? ‘There are three basie principles to this algorithm : 1, CAllmessages are time stamped by the sending process. 2 Amessage cannot be delivered until: {L_ All the messages before this one have been delivered locally. ii _Alltheother messages that have been sent out from theoriginl process have been accounted as delivered at the receiving process. 3. When amessageis delivered, the clock is updated, ‘This algorithm requires that the processes communicate through broadcast messages which ensure that only one message could be received at any one time. bh. Schiper-Eggli-Sandoz algorithm : Refer Q. 1.15, Page 1-16B, Unit -. Gus LAT] Write short note on global state. distributed system: 1-18B (CS-Sem-7) Characterization of Distributed Systera 1. The global state ofa distributed computation isthe set of local states of individual processes involved in the computation and the state of the communication channels ‘The global state ofthe system isa collection ofthe local states (LS) of ‘a processing system, GS= 115,18, 15, where N is number of sites in the system. Consistent global state : 1. Aglobalstate GSis.aconsistent global state iffit satisfies the following two conditions: a. Every message m, that is recorded as sent in the local state of a process P must be captured in the state of the channel C, or in the Collected local state of the receiver process P,. b, Ifamessage m, isnot recorded as sent in the local state of process P,, then it must neither be present in the state of the channel C, nor in the collected local state ofthe receiver process P,. 2 Thus, in a consistent global state, for every received message a corresponding send event is recorded inthe global state. 3, Inan inconsistent global state, there is at least one message whose receive event is recorded but its send event is not recorded in the global state. 4. In Fig. 1.17.1, the global state (ZS,.,LS_.L8,,) and (LS, LS LS.) correspond to consistent and inconsistent global states, respectively. ‘Transitless global state : A global state is transitless if and only if Vi, j:1i, j snz: transit (LS, LS)= 6. Thus, all communication channels are empty in a transitless global state, S,) 8) | ig 1.17.1. Global states ina distributed computation,JoUULOSLUEY Yim pouUeoS Characterization of Distributed System -19B (CS-Sem- 119B (CSSem7 | o9p (C8-Sem-D Distributed System cate: ‘ten Sa Serongly consistent Oe ee Quests. | a patton he events fal erent Explain any intent tale 20S ent al the ecard 2 Inaetroney Reed ee ce reed events are aso Tec ponds toa consistent global ETT] te corres $ consistent stat a strongly 2 as eT ones EO. auonely cenit ernie gible 5 Se a poate a i's global state recordiog eG om me oman TARTU 2016-17, Marks 05) algorithm. : state recording algorithm : 1‘ 2 LL The Chandy-Lamport algort ‘whose role in a FIFO system bas recorded its local stat {sto separate mes ‘8. A marker separates the messages ‘ncluded inthe local state and which are not to “Aprocess must recordits local tate before it receives a marker on ay ‘ofits incoming channels. Chandy-Lamport algorithm : L_ Marker receiving rule for proces On receiving a marker along channel C: Ir has not recorded its state) then ‘Record its process state ‘Record the state of Cas the empty set Follow the “marker sending rule” in Record the state of C as the sot of messages receive lor er Frcabtareregearg seme ere tare Marker nmling al fo ices 2 = Fomontreeriiggae b. Foreach outgoing channel C on which a marker has not! been sent, i sends a marker along C before sends further messages s0%6° Notations used in algorithm Rule 2: On, Ruie3; An active process having weight W may becor doing: What is termination detection in distributed system? algorithm for termination detection. ‘the termination detection problem involves detect ‘going distributed computation has finished all its act ‘rmination detection problem arises when a distributed srminates implicitly, that i, once the computation finishes ocess knows about the termination. ‘has to be run to detect termination of ‘The ter computation te Gil its activities, no single pr ‘Therefore a separate algorithm | the computation, ‘BODW) aComputation message sent as apart ofthe computation and Be eapat assigned toi CDW) :Control message sent from the processes to the controlling ‘agent and DWis the weight assigned toit. afer ct nse marke aT ung ermnation detection eh outgoing is before sending out any $25 Rule 1: The controlling agent or an active process having weight W may ‘nthe chanel into those whidh a senda compulain mess 278 berecordedin thelocal state. 1:vq W, and W, such that cess Phy doing: Wy + Wy =, W, 20, W,>05 WieW,; send B(W,)toP; Jpt of BIDW), a process Phaving weight W does : W:= WW) IrPisidle, Pbecomes active; sme idle at any time by vena cc tfooteling see) — Wi=0; (Process becomes idle); Ruled : On receiving C(DW), the controling agent having weight W takes the following actions: Wie W+DW; Ie W= 1, conclude that the computation has terminated.JeuUBUstUeY Yum pouueos Distributed System 1-19 (CS-Sem-7) Strongly consistent global state + 1. Aglobal state is strongly consistent if itis consistent and transitless, Inastrongly consistent state, not only the send events ofall the recorded 2 received events are recorded, but the receive events of all the recorded send events are also recorded. 3, Thus a strongly consistent state corresponds to a consistent global state in which all channels are empty. 4. InFig. L17.1 the global state LS, LS,,,S,,)is a strongly consistent slobal state. TABl] Give the Chandy-Lamport’s global state recording algorithm. (ARTU 2016-17, Marks 05 ewer] Chandy-Lamport global state recording algorithm : The Chandy-Lamport algorithm uses acontrol message, called a marker whose role in a FIFO system is to separate messages in the channels. After a site has recorded its local state it sends a marker, along al of ts ‘outgoing channels before sending out any more messages. A marker separates the messages in the channel into those which are included inthe local state and which are not tobe recordedin the local state, Aprocess must record its local state before it receives a marker on any ofits incoming channels. Chandy-Lamport algorithm : L_ Marker receiving rule for process: On receiving a marker along channel C: If(has not recorded its state) then Record its process state Record the state of C as the empty set Follow the “marker sending rule” else Record the state of C as the set of messages received along C after ‘7s state was recorded and before j received the marker along C. 2 Marker sending rule for process i a, Process i records its state. b. Foreach outgoing channel Con which a marker has not been sents sends a marker along C before i sends further messages along C: 4 Characterization of Distributed System 1-208 (C5-Sem-7) aug Explain any ale What is termination detection in distributed system ? orithm for termination detection. / sea EE) srobléni involves detecting Whether an—— L 16 jination detection p# ng sme te cise ie pin ei gr at Tar pee ri nanan ev: Pn pect ne peet eet Computation messape Wis the weight assigned toit. 2 C(DW) :Control message sent from the processes to the controlling Sgent and DWis the weight assigned toi Huang’s termination detection algorithm : Rule 1 : The controlling agent or an active process having weight W may send a computation message to a process P by doing: Derive W, and W, such that W, + Wy = W,W,>0, 1, >05 2 1 Wey; send B (W,)toP; Rule 2: On regeipt of B(DW), a process P having weight W does : W:=Wws@wy _LPisidle, Phecomes active; Rule: An active process having we i be! pr having weight W may become idle at any time by send UW tfostroling agent) Wis; (Process becomes idle); Rute 4: On receiving COD thafaleaereetving CADW, the controling agent having weight W taken W:=Ws DW; weJeUULOSLUEY YuIM PouUeoS distributed ayste characteristics of distributed distributed system. ARE Refer Q. 1 @2. How the distributed rs parallel processing system AME Refer Q. 13 Q.3. What is distributed transparency ? aux {Ret of distributed transparencies Refer Q. 14. @.4. Discuss the major issue in designing a distributed system REE Refer Q. 16. @5. Why is scalability an important feature in the design of distributed system ? Discuss some of the guiding principles for designing a scalable distributed system. aBE Refer Q. 1.7. @6. What are distributed systems ? What are significant advantages, applications and limitations of distribute systems ? Explain with examples, what could be the impact of absence of global clock & shared memory. Ame Refer Q 1.11. @7. Discuss the limitations of Lamport’s logical clock with suitable example. ami Refer Q. 1.13. Q.8. What are vector clocks ? Explain with the help o! implementation rule of vector clocks, how they ar implemented ? Give the advantages of vector clock ove! Lamport clock. mm Refer Q. 1.14. better than ing system ser paplaln Explain the different Characterization of Distributed System 1-22B (CS-Sem-7) ‘8. What do you mean by casual ordering of messages ? If age m, and m, to another process ages are not @ process P sends two me: Q, what problems may arise if the two m received by recipient @, in the order they process P. Develop an algorithm which guarantees the Casual ordering of message in distributed system. waa Refer Q. 1.15. were sent by Q.10. Give the Chandy-Lamport’s global state recording algorithm. f ams: Refer Q. 1.18. Q.11. What is termination detection in distributed system ? Explain any algorithm for termination detection. ‘awe: Refer Q. 1.19. 660JoUUROS LEY Yim pouueos stributed Mutual ps Exclusion Exclusion : Classification of Distributed Mutual Exclusion, Requirement of Mutual Exclusion Theorem Token Based aD cesemnrnwsnen 3-9B t0 2-108 Non-Token Based Algerithm, Performance Metric for Distributed ‘Mutual Exclusion Algorithm Distributed Deadlock Detection : System Model Resource vs Communication Deadlocks, Deadlock Prevention, Avoidance, Detection & Resolution 2-108 to 2128 21B(CS-Sem-7) Distributed Mutual Exclusion 2-2B(CS-Sem-7) | PART-1 ! bis jon : Classi ‘Distributed Mutual ibuted Mutual Exclusion : Classification of ee Exclusion, Requirement of Mutual Exclusion Theorem. } zs Questions-Answers a a | ‘Long Answer Type and Medium Answer Type Questions eee Gueain| What do you mean by mutual exclusion in distributed system ? What are requirements of a good mutual exclusion ARTU 2014165, Marks 05 algorithm ? oR . State the classification of distributed mutual exclusion. What is requirement of mutual exclusion theorem ? “AKTU 2018-19, Marks 10. Tower] Mutual exclusion : 4. 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. 2 Concurrent access to shared resources is prevented. 3. Mutual exclusion algorithm guarantees that only one request accesses the eritieal section (CS) at atime. 4, There are two classes of distributed mutual exclusion algorithm : a. Non-token based algorithm b, Token based algorithm Requirements of good mutual exclusion algorithm : 1. Freedom from deadlocks : Two or more sites should not endles wait for messages that will never arrive. eee % Freedom from starvation: A site should not be forced to wait indefinitely to execute CS ie., every requesting site should ge opportunity to execute CSin a finite times® “te Should get an 3. Faimess: aimess dictates that requeata mus Se anasee be executed in the orderin 4 Fault tolerance :A mutual exclusion algori the wake of a failare: ita — slgorithm ia fault-tolerant if in eee ize itself so that it continu function without any (prolonged) disruptions, eeeJouUBUS LEY YIM pouueos yarees and the in shared maa sing shar’ by asi semaphores. | Mutual exclusion problem's solved by using message passing approsch. ribe the requirements ual exclusion ributed system. Is mut Sitio chan singe com DUCT ARTO 2017-18, Marks 10 js mutual exclusion ? Desc of mutual exclusion in problem more complein system ? Justify your answer. ‘Answer Mutual exclusion and its requirements Unit2. . Pat problem of mutual exclusion becomes more complex distributed system ae compared to single computer systems because of absence 00 craved memory and a common physical clock and because of unpredictable saitvage delays. So, considering these factors, its virtually impossible or © ste to have correct and complete knowledge ofthe state at the system. Refer Q. 2.1, Page 2-28, PART-2 ‘Token Based and Non-Token Based Algorithm, Performance Metrie for Distributed Mutual Exclusion Algorithm. Long Answer Type and Medium Answer Type Questions 2-4B (CS-Sem-7) Distributed Mutual Exclusion Se eee What is token based algorithm and non-token based algorithm in distributed system ? Explain with example. ‘ARTU 2016-19, Marks 10 [Answer ‘Token based algorithm : 1. Inthe token based algorithm, a unique token is shared among all sites. sits passes the token then iti allowed to enter its CS (Creal Section). ‘Token based algorithms use sequence numbers instead of timestamps. 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, ifa site attempting to enter the CS but does not have the token, it broadcasts a request message forthe 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. 3, Each request for the CS getsa timestamp and small timestamp requests have priority over larger timestamp requests. Each process freely and equally competes forthe right touse the shared resource; requests are arbitrated by a central control site or by distributed agreement. Exampl Lamport's algorithm : In Lamport’s algorithm, Vi: 1Si S.N::R,= (Sy, Sy. ...Sy). Every site S, keeps a queue, request-queue,, which contains mutual exclusion requests ordered by their timestamps. This algorithm requires message tobe delivered in the FIFO order between every pair of sites, Que25, | Differentiate between token and non-token based algorithms. ARTU 2014-15, 2016-17; Marks 05 2 3JeuUBUSLUEY Ym pouueos sites (or nodes). Z| oxen contains sasenee number of the sites ia torent rte | alr siesta 3 TAsite having tokencan 007 ‘Atos ean only enter the crit Ateharitied secéon. | vale © = are on-token based 2a 7} Raegaoegngee | nan Eo letart aganwata) Beitr based algorithm e Mackowats alge | ET ri g. Sghal Heuristic algorithm al exclusion token based mutus algorithm with its performance, Explain Lamport’ algorithm for mutual exclusion. po Lamport’s algorithm : 1. In Lamports algorithm, ¥ i:15i $ N:1R,=(SySq Sy). Every site Keeps a queve, request-queue,, which contains mutual exclusion requests ordered by their timestamps. 2 This algorithm requires message to be delivered in the FIFO order between every pair of sites. Algorithm 1 Requesting the critical section : ‘a. When a site S, wants to enter the critical section (CS), it sends @ REQUEST (i, i) message to all the sites in its request set and places the request on reques-queur, Where (, i)is the timestam? of the request. When asite S, receives the REQUEST (sf) message from site» it returns timestamped REPLY message to and places site S, request on the request-queve, 2-68 (CS-Sem- Distributed Mutual Exclusion aepeesen I 2 Executing the critical section : Site S, enters the CS when the following two conditions hold : a. S,has received a message with timestamp larger than (ts, ) from allother sites. b, Ss request is at the top of request-queve, 3, Releasing the critical section : a. Site S,, upon exiting the CS, removes its request from the top of its ‘request queue and sends a timestamped RELEASE message to all the sites in its request set. Whena site S, receives a RELEASE message from site S, it removes Ss request from its request queue. When a site removes a request from its request queue, its own request may come at the top of the queue, enabling it to enter the CS. The algorithm executes CS requests in the increasing order of timestamps. Performance : Lamport’s algorithm requires SUV ~ 1) messages per CS invocation : 1, (V-1) REQUEST, (N - 1) REPLY, and (V ~ 1) RELEASE messages. ‘Synchronization delay in the algorithm is 7. Lamport’s algorithm can be optimized to require between 3(N - 1) and ‘2(N —1) messages per CS execution by suppressing REPLY messages in certain situations. (Rae27 | Explain Suruki-Kasami algorithm. Suzuki-Kasami algorithm : 1. Inthe Suzuki-Kasami’s algorithm, if site attempting to enter the CS but does not have the token, it broadcasts a request message for the token to all other sites. 2. ‘The main design issues in this algorithm are : It distinguishws between outdated request messages and current 2 request messages. b, It dotermines which site has an outdated request for the critical section, Algorithm 1. Requesting the critical section 4. Ifherequesting site S doesnot have the token, then inerem: itssequene number, and sends a REQUEST om sneaage toall other sites. (sn is the updated value of RN,{i)). ° neeJoUULOS LEY Yum peuueoS ied the token. iv pe execution ofthe update, thenit deletes the token to the site sty to other sites with ‘Thus, after having execu! Fequests for the CS) outstanding requests for algorithm for mutual algorithm. ‘The Ricart- Agrawala algorithm is an optimization of Lampor's algorto that dispenses with ‘Bessages by merging them with REPLY messages. In this algorithm, VisksisW::Ry= Sy Sp Sy) Algorithm : 1. Requesting the critical section: ‘a When a site 5, wants to enter the CS, it sends a time REQUEST message toall the sites inits request set. REQUEST message from site S,,it sends a REPLY message to site S, if ste 5, is neither requesting nor executing the CS or if site Sis requesting and S/s request’s fimestamp is smaller than siteS/s own reques's timestamp. request is deferred otherwise 2 Executing the critical section: fa Site enters the CS after it has reuived REPLY messages from all the sites in its request st. stamped b. When site S, receivesa! 2-8B(CS-Sem-7) Distributed Mutual Exclusion 4. Releasing the critical section: 4 WhensiteSexits the CS, itsends REPLY message tall the deferred requests. “Asite's REPLY messages are blocked only by sites that. Aste igher priority Ge. a smaller timestamp). Thus, REPLY messages toall the deferred requests, the site with the next highest priority ‘receives the last needed REPLY message and enters the CS. prior ution of CS requestsin this algorithm is always in the order oftheir Cstanpe. Lime The Ricort-Agraaaaleritm reqires21¥ <1) metages Fer ee REQUEST and UV =D REPLY menage ro oton dla inte algorithms. “GaREEE] Mw the performance of mutual exsuston algorithms inwegsured? on Discuss the performance metric for distributed mutual exclusion AKT 2016-17, Marks 7.5] are requesting the CS ‘when assite sends out algorithms. oR How distributed mutual exclusion is different; in single computer system ? How the performance exclusion algorithm is measured? [ARTU 2016-19, Marks 10 Answer | Difference: Refer @. 22, age 2-89, Unit2 Performance of mutual exclusion algorithm : Performance of matual exclusion algorithm is measured by the following four metries : 1. Response Time (R7) : tis time between R and CS i. time between ‘request message is sent out and completion of eritical section. ig HEZEQWEA The site enters The ste ets CS request messages "cs. ‘he cS of mutual exclusion of mutual ‘Time 2 Synchronization delay (sd) : Itis time bet = Itis time between two consecutiv that time between endof one CS and begining of ancther CS Ia this Period, messages are exchanged to arrive at mutual exclusion decision,JeuUBS LEY Yim pouueos vs 2-9B (CS Distributed Sytem Sem 0B (C8Sem-7) Distributed Mutual Exclusion ‘Next sila Las site enters 8 Tokea Response [Synchronization | Message [Message wate time i) delay aw GD SuzukiKasami] 27 +E T N N Syachreniation ‘aay ‘Singhal’s +E T Ne N rigi292) Heuristic k NumberofmessageperCSiAsnumberofmesssgcexchangereésy — lrarmong [Piog N+] Tlogiwy2 | login) | 4 the performance will improve. sen the spuiem enscitay a epee mame isthe rate at which the aye execu iqrtsAgrawala algorithm :ReferQ.28, Page 2-7, Unit? the CS. Ifsd is the synchronizat on dey a i ong iad fon time then the throughput i given by uat section time then the PART-3 ‘System throughput = Distributed Deadlock Detection : System Model Resource vs Communication Deadlocks, Deadlock Prevention ‘Avoidance, Detection & Resolution. jon is different fry Que2i0.] How distributed mutual exclusi le-computer system ? Classify mute mutual exclusion in sing! ; inclusion algorithms. How the performance of mutual exclush Sigorithms is measured ? Compare the performance of token w non.token based algorithms. How the Ricart- Agrawala algoritt optimize the Lamport’s algorithm. [ARTU(BO015:16; Marks} ‘Answer Difference: Refer Q.2.2, Page 2-3B, Unit-2 Classification of mutual exclusion algorithm : 1. Token based algorithm : In the token based algorithm, a uni token is shared among all sites. If sites possess the token then allowed to enter its CS (critical section). 2 Non-token based algorithm : In non-token based algorithms, at communicates with a set of other sites to arbitrate who should exee the CS next. Performance of mutual exclusion algorithm : Refer @. 29, Page 24 Unit2, json of performance of token and non-token bat Compari algorithms : (l= light load, hl = heavy load) Non-token | Response | Synchronization | Message | Messs! time (0) delay @ oD Lamport 2 +E Tr aN) | a=! [Ricart-Agrawal | 27 +E T auv—1) | 2N-! Maekawa Or+E or sin | 5 Long Answer Type and Medium Answer Type Questions ‘GaeBAi. | What is deadlock ? What are necessary conditions for the occurrence of deadlock in distributed system ? Shores. Deadlock is defined as the permanent blocking of the process i... a set of process is waiting for an event that is held by other process Necessary conditions for deadlock : 1. Mutual exclusion : A resource can be held by at most one process 2 Hold and wait: Preceses that already bol resources can wait for other resources 4. _Nopreemption A resource, once granted, cannot be token aw a process till its complete execution. om 4. Circular wait Two or more processes are waiting for resources used bone ofthe other processes, Wecan represent resource allocation agraph where : Pe R means aresource R is currently held by i per 2s eam arene cure hel by proce Quo FZ | What is distributed deadlock ributed deadlock? Explain vari handling strategies. ain various deadlockJouueaswiey Yum pauueos 211B(CSSem-7 Distributed System ) 9.42 B(CS-Sem-7) Distributed Mutual Exclusion i Using advance knowledge of resource usage of processes and — Se ee tt ms i ae tae gene tach process is holding a resources 8m or unsafe. Sequired by some other proces Ts resume waicosted' 5 resource is. the process ony ifit is safe todos, 2 sc Om ofdeadock ina dsrbuted DBMS is more comple athorwive the request i deferred. ly ifit in safe todo so, because it involves several di 4g. Deadlock detection: ited DBMS itis necessa a Inthis approach for de entire system to dete nis approach for dealok detection, the system does not make ‘any attempt to prevent deadlock but allows processes to request ofprocosses are blocked because vd waiting for another resources ferent sites. ry to draw a global wait-for ‘Thus, in a distribu ict adeadlock situation. resources and wait for each other in uncontrolled manner. graph (GWFG) for the Deadlock handling strategies in distributed system * 1. Deadlock prevention : b. Deadlock detection requires status of the uires status of the process and resources asec siede prevention is achieved by having aprocess coves} Oe interaction for availability ofeyclie wait. Deadlock prevesatonce before it beings executing r by Preempig «Deadlock detection algorithms are easily implemented by a process that holds the needed resource. ‘maintaining Wait-for-graph (WFG) and searching for cycles. a by New mutual exclusion, bold-and-wait no preemption and les GeeRIBy] Dictinguis wait are the four necessary conditions for @ Capea w — guish between resource deadlock and ‘one of these conditions is never s¢ fied then deadlock can be communication deadlock. prevented. "AKTU 2014-15, Marks 05 Deadlock prevention methods are i Collective requests These methods deny the hold and wat ‘condition by ensuring that whenever & process requests # ‘Communication deadlock corse it does not hold any other resource 1 |The dependence of one | A one | A process can know the ident Seca uae | (eames |otegee Ordered reaver rce type is asigned a unique glob other transactions is not | whichitdepends. such that eae ce total ordering of all resource tyPes- directly known, iii Preemption : A preemptable resource isone whose sae 2 [A process cannot proceed | A process cann = Frecmption Ace etscamber 2 eee comet re | Azercematrgmng ae neem cee ree mae ont condition. which itis waiting. fhe processes for which it is 4. Deadlock prevention is highly incompetent ‘and unrealistic waiting. distributed system. a 2 Deadlock avoidance: PARnea ‘a. Fordeadlock avoidance in distributed system, aresourceis assis’ — | Centralized Deadlock Detection, Distr For donate state global system is eae a ee ee b, State of global system includes all processes and resourees és tasing Algorithm. = Gintributed system. : c. Deadlock avoidance algorithm can be done in the following steF5 cod pene en a process requests for a resource, reso ree Anener Typoand ie for allocation its not immediatly allocated to MedinmAnswenityce Question ithe system assumes that the reque! process. Rather, granted.JeuUbUstUeY Yum pouueos pis B(csSem-7) deadlock. Explain edge chasing algorithm “Answer | Deadlock handling strategies : Refer Q Controt ion: Algorithm or detect bbe handled in following W475: 1. Centralized control: ‘a In centralized deadlock detection algoithny 12, Page 2-108, Unit-2 distributed deadlock can 1s, a designated site Carre as the responsiblity of constractig the global WFC and searchingit for cycles. b. Centralized deadlock detection algorithms are conceptually simple and are easy to implement. 2 Distributed control : global deadlock a. In thes algorithms thorecpnstiity for detecting Is shared equally amongal ses The global state graph is spread over many sites and vera parteipaein the detection of iol ile 2 Hierarchical control:In rahi deadlock det Sites arc arranged ina bierarhil asin, nds involving ony it descendat sits Ede chasing algorithm 1 Bage chasing algorithm is used for phantom dead distrbuted yetems. 2, tn this, the global wait-for graph isnot constructed, but each ofthe aaa es hed has knowledge about somecft edges. rs attempt to find cycles by forwarding messages called probes, geste rap thoughoot the distributed syste for relation tection algorithms, detects deadlocks ick removal in 3, Theserve which follows the ed 4. A probe message consists of transactions wai ‘epresenting a path in the global wait-for-graph. ‘Bdge chasing has three steps. a. Initiation :The server initiates. detect deadlock Jon : Detection consists of receiving probes and deciding be Det etiejeadlock has occurred and forward probe whether de ‘on : When aeycle detected, a transaction inthe excl # ‘break deadlock. e. Resolutis aborted to 24 BcsSem-7) Distributed Mutual Exclusion zupecssen) Give the deadlock handling strategies in distributed 7 What are the differences in centralized, distributed and Inical control organizations for distributed deadlock BOTEIS, Marks 10| eystem’ bierarel detection? Deadlock handling strategies : Refer Q. 2.12, Page 2-10B, Unit-2. Difference: [No] Centralized contro! {_ |A control site has the] AMI sites have the Ipesponsbiity to detect| responsibilty to detect Distributed control [Hierarchical control Descendant site can} detect a global wait [lobal wait for graph. |aglobalwaitfor graph.| for gra ] |itave single point offNo single point of] No single point of| failure. failure. failure. 3._[Basy to implement, @. [Completely centraliz/Path pushing and| Menasce-Muntz and| Sod Ho-Ramamoorthy|edge " chasing| Ho-Ramamoorthy| [tgorithin are used for[algorithm are used] algorithm are used| Jdeadlock detection, for deadlock| for deadlock detection. detection. ‘FHRBIET] county the deadlock detection algorithms: Describe tbepathptshing deadlock detection algorithm. Sar av Difficult to implement | Simple to implement. oR Discuss Obermarck’s path-pushing algorithm. Distributed deadlock detection algorithms canbe divided into four & Path-pushing algorithm : In path-pushing algorithms, wait algorithms, wait for dependency information ofthe global WFG (wait for ‘accu 4, ntti of pati a Badge chasing algorithm :In edge chasing algorithms, 2 , special Seco te sen et ee When a blocked process receives probe it pro ; Nes locked rss reves pra, itropagates the probe slong © Diffusion computation based algorithm : Diffusion ‘ope algorithms make use af ech agorthne 1 detec deoshonceJeuUBOSLUeY YIM pouueos 2-15B (CSSen, De nv mom eng menage are successively propagated Esough the edgesot the WFC thm : These algorithms dei, Cina ste detection based lero Tho gern Gest taking snap ta a em parte a = raph is ‘over ees tathigee Reel creer econ of eal Ts eae bare ca “s Ons pulping gsi: Sema algorithm was designed for distributy Paap venice in bite letectiv ix ition abuut = een © nRirlapaace's properties of ath Algortthn Desde deat ts flows the flowing eran 1. The sites wait for deadlock-related information from other sites in ty system, 2 The site combines the received information with its local TWF graphy build an updated TWF graph. It then detect all eyeles and breaks laa {yeles which donot contain the node Ex (External node). oralleycles, Ex-> 7,» 7,» Ex which contains the node Ex’ thes ts them in string form Ex 7, T,, Bx'toall other sites where suntzaneaction of T, is waiting to receive a message fren ty by rratsaction of T, a this ste. The algorithm reduces messaye ta, £2lially ordering transaction and sending tester Ty Tol, for ether Sites onli 7 shigher than yin the lene tori Als Ar 8 deadlock, the highest priority transaction detec eee Piscuss various centralized deadlock detectia Fequest resource or a reles* resource message, it correspondingly updates its WEG, 2-16 B (CS-Sem-7) Distributed Mutual Exclusion WEG for deadlocks whenever a request edge is added to the WEG. Freee Ramamoorthy algorithms : Ho and Ramamoorthy gave Press airalized deadlock detection algorithms called two-phase sedene, The two-phase algorithm ; 1 Inthe two-phase algorithm, every site maintains astatus table {hat contains the status ofall the processes initiated at the side, At Periodically, a designated site requests the status table from al stes, constructs a WEG from the information received ed searches it for eycles. At Tr there is no cycle, then the system is fre from deadlocks, transactions which are common to both reports, 'v- It the same cycle is detected again, the system is declared deadlocked. b. The one-phase algorithm : i Theone-phase algorithm requires only one status report from £2) site; however each ste maintains two status tables a Fesource status table and a process status table. The resource status table at a site keeps track of the Hransactions that have locked or are waiting for resounes stored at that site. AE The process status table ata site keeps track ofthe resources locked by or waited for by all the transactions at that ate, ‘Periodically, a designated site requests both the tables from whieh tgrconstruct a WEG using only those transactions tor Tech the entry in the resource table matches tire forepelen PE emtY i process table, and searches the WEG for cycles, ¥. Ifnoeycleis found, then the system isnot deadlocked, otherwise a deadlock is detected.JeuUBUsteY Yum pouueos Distributed System 2-16 B (CS-Sem-7) Deadlock detection messages are successively propagated (i, “difused”) through the edges of the WFG. vpepeeee 4 Global state detection based algorithm : These etection + These algorithms detect deadlocks by taking a snapshot of the system and by examining it for the condition ofa deadlock. Several sites in distributed system participatein detection of global cycle. Thus global state graph is spread over many Sites, The responsibility of detecting deadlocks shared equally among sites. Obermarck’s path-pushing algorithm : | Obermarck’s push-pushing algorithm was designed for distributed database system. eee ae 2. In path-pushing deadlock detection algorithms, information about the wait-for dependencies is propagated in the form of a path. Algorithm : Deadlock detection at a site follows the following iterative Process : 1 Thesi system, 2 The site combines the received information with its local TWF graph to build an updated TWF graph. It then detects all cycles and breaks locl eveles which do not contain the node Ex (External node) 3. For alleycles, Ex» 7, -» 7,» Ex which contains the node Ex the ste transmits them in string form ‘Ex T,, T,, Ex’to all other sites where a fs waiting to receive a message from the ite. The algorithm reduces message traf ig the string ‘Ex, Ty, TT the lexical ordering. Als, detects the deadlock. 's wait for deadlock-related information from other sites in the subtransaction of T, subtransaction of 7 at thi by lexically ordering transaction and sendin Ex to other sites only if 7, is higher than 7, in for adeadlock, the highest priority transaction Que217.] Discuss various centralized deadlock detection algorithms. Answer tection algorithms are tralized algorithm : ; 7 1 Copley centred osname * designated site ‘called the control site, oainision De rrG af graph) of the entire system ‘and checks it for the ae — release resources (even local b Ae mt aso control. site, respectively: eee cone the conte se ee updates resource message resources) bf sages t0 st resource or a releast its WFG. 2 The Ho-Ramamoorthy algorithms two centralized deadlock detection phase algorithms, a. The two-phase algorithm : sie.e site is responsible for detecting dead Distributed Mutual Exclusion 2-16 B (CS-Sem-7) “. Thecontrol site checks the WFG for deadlocks whenever a request edge is added to the WFG. Ho and Ramamoorthy gave algorithms called two-phase and one- In the two-phase algorithm, every site maintains a status table that contains the status of all the processes initiated at that side Periodically, a designated site requests the status table from all sites, constructs a WFG from the information received, and searches it for eyeles. 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, ‘The one-phase algorithm : i, Theone-phase algorithm requires only one status report from each site; however each maintains two status tables; a resource status table and a process status table. 4 The resource status table ata site keeps track of the transactions that have locked or are waiting for resources stored at that site. * reso iil The process status table ata site keeps track of the : rack of the resources locked by or waited for by all the transactions at that site. iv, Perndially, a designated site requests both the tables from every site, construct. a WFG using only those transactions for euieblies Tene in the resource table matches the Foreyelon, 8 £0177 in process table, and searches the WFG \. Aoeyeisfound, then the systems vise a deadlock is detected. ee eadiesked,otherwt Que 2.18.] Explain variou: lain various hierarchic: Baie] hical deadlock detection Answer Inhierarchical algorithms, sites are logi Pgically arranged in hierarchical fashion, locks involving only its children2-188 (US-Sem-1) Distributed Mutual Exclusion Jouueaswiey Yum pauueos 17 BUSSem-7) aan si aneaina aa a Them it sends intercluster transaction stato information and wait- ‘arious hierarchical deadlock detection s for relations to the central control site 1 The Menasce-Muntz Algorithm : £. The central site split the intercluster information it receives, bp {athis algorithm all the controllers are arranged in tree fashion. constructs a system WFG, and searches it for eycles, b. The controllers sine mest evel eacotroler) manage Thus contol site detect all deadlock lated ineacluster, and Seaguters and others (non-leat controllers) are responsible for thecentrl contrast detects ncaa © Whenever a change occurs in a controller's TWF (Transa) graph due to a resources allocation, wait orrelease, itis propagated tots ee Parent controller. search E VERY IMPORTANT QUESTIONS The parent controller makes changes in its TWF graph, searches 7 ss |Following questions are very important. These questions for eycles, and propagates the changes upward, if necessary. . ees eive up-to-date information concerning may be asked grote Seaton ATS an well as non leaf controller ean receive Up tio UNivensrry : the TWF graph of its children continuously or periodically. The Ho-Ramamoorthy algorithm : . , OO In this algorithm, sites are grouped into several disjoint clusters. @.1, What do you mean by mutual exclusion in distributed Petey, a saa ncn oot sntl te system ?Whatarerequirementsotagoed nutans dynamically chooses acontrol ste for each cluster algorithm ? © The central control site requests from every control site their ame Refer Q 2.1. intercluster transactien statu information and waiter relations @.2, What is token based algorithm and non-token based algorithm in distributed system ? Explain with example. ana: Refer Q. 2.4, 3 Differentiate between token and non-token based algorithms, ‘Amz Refer Q. 2.5 Q4 Explain the Ricart-Agrawala algorithm for mutual Ragusion. Mention the performance of this algorithes, @5. Discuss the performance metric for exclusion algorithms, ame Refer Q.2.9, ibuted mutual Control 6. Classify the deadlock detection algorithms. Deseril ion » Describe the Rarb-pushing deadlock detection algorithay, Aue Refer Q. 2.16, on Fig: 218.1. itesinits remove phantom deadlock, e from all the sit Pk el sit collec st tection algorithm to AME Refer Q. 2.14, ult, a cont mne-phase ter transactions. Ase ist oe ee 800 cluster and appr involving all deat detectJeuUBUSLUeY Yum pouueos CONTENTS Part-1 : Agreement Protocol Introduction, System 3-28 to 34B .9-4B to 3-11B Part-2 Problem, Byzantine Agreement Problem, Consensus Problem, Interactive Consistency Problem, Solution to Byzantine Agreement Problem S-1IB to 3-148 Application of Agreement ~ Protocol, Atomic Commit in Distributed Database System Part-3 9-14B to 9-238 Distributed Resource ‘Management : Issues in ; Distributed File System, Mechanism For Building Distributed File System Part-4 3-24B to 3-268 Design Issues in Distributed Shared Memory 3-26B to 3-30B iehm For Implementation. rere ,d Shared Memory Algoriths of Distributet g-1B(CSSem-7) 3-2B(CS-Sem-7) ‘Agreement Protocols, PART-1 |__¢. Asreement Protocol: Introduction, System Models. Agreement protocol : 1 Process of sending and reaching the agreement to all sites is called agreement protocol. 2 _Indistributed system, the agreement protocols are very much useful for error free communication among various sites. 3. 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 4. Also the presence of faulty processor is not known to the non-faulty processors. So, the non-faulty processors do not restrict the mess transfer to the faulty processors. a 5. 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. 6 The common agreement among the processors i agreement among the processors is taken through agreement protocol. aa + Que's.2. | Whatis agreement protocol ? Discuss the general system ‘model where agreement protocols are used. aaa Agreement protocol : Refer Q. 3.1, Page 3-2B, Unit-3. System model: Following are the Stem gare the system models where agreement protocols 1 Ithere are proc the distr proce aren processorsin the distribute spate ut of them may be found as faulty procescors. MY ™ Processors 2JeuUbUstUeY Yum pouueos uistriputea system 3-3B(CS-Sem-7) 3. (Arrecciver processor always knows the identity ofthe sender procestor 4. ‘The communication medium is reliable (i. it delivers al : ra all messages hou! intreducinganyersoesland only processors are prone to fale Que 3:3. | Discuss various aspects for recognizing the agreement Protocol. Answer] Following are various aspects to consider for recognizing the agreements in distributed syste ae 1. Synchronous and asynchronous computations : & Inaaynchronouscomputation, proeessesin the system runinlotk step manner, where in each sep, a process receives messages, Performs a computation and sends messages ta other processes ©. In synchronous computation, a process knows all the messages whieh it expects to receive in around. ‘© Amessage delay or a slow process can slow down the entire system or computation. In anasynchronous computation, processes in the system does not Proceed in lock step. ©. Approcess can send and receive messages and perform computation atany time. 2 Process failure model: a. The processor failure is rating lnc agrees! poor proces ean ain tee nl: . i. , Crash fault : Ina crash fault, a processor stops functioning Copee a oumes neato von fle to an omiaion fault, a processor behaves the most common system model considered a processor“omits"to ii, Omi sont send messages afore proces {cious fault : In a malicious Matonly and arbitrarily i renticated messages: Athentented and ne sytem) at ticated mosotfne contents of a received messee ‘age theo San phenticity’ ‘of a received message: igned message. ‘a (faulty) processor 2 age Focivedit from another Processor a $48 (C8Sem-7) Agreement Protocole ar change the contents ofa received message before it lays the Imestage tothe proceso ¢.Apromasoris not ableta verify authentic ofarewived message © Anon-authoticated message is alo caled an oral message. _ Itiseasior to reach agreement in an authenticated message system cause fully processors are capable of deing lees damage, 4. Performance aspects: The performance of agreement protocols is generally determined by the following three metrics pe * " Time Time refers ta the time taken to reach an agreement Under protoce 41. Message trafic: Message trac is measuredby the number of meanage exchanged foreach an agreement. iL, Storage overhead Storage overhead measures the amount information that neds totn stored at procescors during the txecutlon ofa protec PART-2 Classification of Agreement Problem Byzantine Agreement Problem, Consensus Problem, Interactive Consistency Problem, Solution to Byzantine Agreement Problem. Questions-Answers ‘Long Answer Type and Medium Answer Type Questions Que34,] What are agreement protocols ? Explain Byzantine greement problem, the consensus problem and interactive consistency problem. ey probl More ‘AKTU 2016-17, Marks 10 Answer - Agreement protocol: Refer Q. 3.1, Page 3-28, Uni on of agreement protocol» ‘The Byzantine agreement problem : foro cles EI, 88 abitearily chosen Ips led he gure procs, boadewtensian genesJeuUBUSLUeY Yim pouueos Distributed System 3-5 B(CS-Sem-7) b. A solution to the Byzantine agreement problem should meet the following objectives : i. Agreement: All non-faulty proc i. Validity Ifthe source processor! ‘upon value by all non-fat initial value of the source. iii. Termination : Each ‘non-faulty processor must decide on a valve. 2 Consensus problem a. Inthe consensus problem, value toall other processors. b. Initial values of the processors may eA protocol for reaching consensus conditions : . Agreement :Allnon-faully processors agre2 08 value. si Vulnaity Ifthe initial value of every non-aully roses then the agreed ‘upon common: value’ ‘by all non-faulty processors must be 0. iii. Termination Each non-faulty ee decide on avalve The interactive consistency problem : re consistency problem, her processors. ‘may be different. rive consistency problem should meet the lessors agreeon the same value. isnon-faulty, then the common 1ulty processors should be the eventually, a initial ‘every processor broadcasts bbe different. should meet the following the same single processor must eventually ‘every processor broadcasts A protocol for the interact following conditions : i ‘Agreement = ‘All non-faulty processors: Yector (0, Yar Yn ; Validity: Ifthe i ‘processor is no! is v,, then the jth walue to be ogre Bofessorsmust ber venation + Each non-faulty ii, Termination : Ea . «< fii Teeide on different value of vectors. agree on the same itsinitial value faulty and SS ‘all non-faulty wed on bY 35. | What ¢ problem, the © coment Brom Dente nr” ns 3-6B(CS-Sem-7) rat protocol : Refer Q. 8.1, Page 3-28, Unit-3. Aammatine agreement problem, the consensus Probl and Byzanilve consistency problem : Refer Q. 24, Page 4B, Unit‘) ‘Shostal-Pease algorithm :>—> lise Yoad kr ben? “gorithm, also referred to as Oral Message algorithm OM(™), aes Bycantine agreement problem form Ler more processors ma Sresence of at most m faulty processors sa poote the total mmber of processors (where, 2 m+ 1). The algorithm [enccursively defined as follows : “Algorithm OM(O): 1 the source processor sends its value to every processor. 2. Bech processor uses the valu it receives from the source. it receives ovalve, then it uses a default value of 0. ‘Algorithm OM (m), m > 0: {Lhe source processor sends its value to every processor. 2. Foreachi, letu be the value processor i receives from the source (iit aan vowalve, then it uses a default value of 0). Processor i acts as Faerie source and initiates algorithm OMI ~1) wherein, itsends the value g, to each ofthe other n~2 processors, 4. Foreach¢ and where and are not equal) lt be the value processor received from processor jin step 2 using Algtithm OM (m — DIF ___feveives no value, then it asesadefalt value of. Processor uses the valve majority (04,0 no Yq ‘4. The majority function is used to select the majority value out of val received in round of message exchange. * me 5. The function majority ( ) jor yy, Ys By) computes majority of values Uy Uy, 0, fit exists (otherwise returns 0). * QuedG.] Describe Lamport-Shostak-Pease algorithm. How does vector clock overcome the disadvantages of Lamport clock ? Explain ‘AKTU 2016-17, Marks 15 with an example. i . {Lamport Shostak Pee algorithm :Refor@ 2.5, Page 9-5B, Unt iss clock overcome avantage of Lamport lock With Lamport oe jine whether two events are casu: ching at to timestanpe caste f CA) CW) dace not cleans eee Iways mean A- Bwile vector clock al le veetor clock allow to ‘ determ ‘compare the tin Jeermine whether they are casually related or not,” tne events toJeuuogUIey Yum peuueos Distributed System 3-7B (CS-Sem-7) For example : Vector timestamp is shown in Fig. 3.6.1. The event e,, with vector timestamp (2, 1, 0) is causally ordered before the event e,, with the vector timestamp (2, 1, 4), but is concurrent with the evente.’ having timestamp (0, 0, 2). 41,0 21,0) y (0,0,0) Space Ds £ 6,0) ea 22 p01 0,2) (21.9) * (0,00) és oe a es Time Fig 36.) QueS7] what do you understand by Byzantine agreement problem? ‘AKTU 2016-19, Marks 10] oR What is Byzantine agreement problem ? Provide the solution to Byzantine agreement problem. “AKTU 2016-19, Marks 10 =a 1. In Byzantine agreement problema single vi on is initializes by an arbitrary processes an have to agree on that value. 2 ‘There are n processes, x = (Pyy Par Pa! with unique names ove! Nail... n) and at most Byzantine participants ¢ 3, ” Solution to Byzantine agreement : Solution to Byzantine agreement a ere aye Se ttn treatin ae Lamport Shostak-Pease algorithm : Refer Q. 3.5, Page 3-SB, Unit-3. aeGRE] Show that a Byzantine agreement cannot be reached mong thirve processors, where one processor is faulty. on Explain treatment of impossible result forthe solution of Byzantis ‘agreement problem. * ‘ine = 1. Sometimes, the agreement problem may lea to such acondition whi is quite impossible to solve. Honwhich 2 Thesituation where the agreement is impossible, called as impossi Tea possible, called as impossible 3. This type of problem cannot be reached to agreement. 4. Inasystem, the impossible result situation is found with more " ndwith more than two 5 Let us check the situation of impossible result ina system wit Let us che pos tina system with three Consider a system with three processor, P,P, and P, ‘We assume that there are only two values, 0. whi proces only two values, Oand 1, on which agree and processor P, initiates the initial value. = 8 Thereare two possibilities: Case: Py is not faulty : 1 Assume Py is faulty. 2 Suppose tha i 3 pects hat Pa ond an initia value of Io bth Py and Py ocean iciously and communicates a value of 0 to Toe, -P receives conflicting values from Py and P, lowever, since Pps non-faulty, proc oweyes since Pa isnon faulty, processor P, must accept Las the t.JeuUbOSLUeY Ym pouueos Distributed System 3-9B (CS-Sem-7) (Cuse 11: Ps is faul ‘Suppose that processor Pp sends an initial value of 1 to P, and ta L Py 2. Processor P, will eommunicate the value 0 to Py. 3 As faras P, is concerned, this case will ook identical to Case I 4. Soany agreement protocol which works for three processors cannot distinguish between the two cases and must force P, to accept Las the agreed upon value whenever P, is faced with such situations 5. However, in case II, this will work only if P is also made to accept 11 as the agreed upon value. 6. Using a similar argument, we can show thatifP, receives an nit value of O from Py then it must take O asthe agreed upon vale even if P, communicates a value of 1. However, if this is followed in case Il, P, will agree on a value of! and P, will agree on a value of 0. ‘Fig. 9.8.2 Processor Py is fault ‘Therefore, no solution exists for the Byzantine agreement problem for thr processors, which can work under ‘single processor failure. problem, and explai# ibe Byzantine agreement Que 3.9. | Deseri pena ‘Show that Byzantine agreement cannot 1 Agreement Protocols 3-10B(CS-Sem-7) Agreement Pretoccte Epssotine Agreement problem and its solution : Rel rene ars te soltion «Refer 27 Pree Pr Scider ret wit fur rcetrs sy PPP anu that proeors tre exchanging hve valecs 2 a afk oes Py B te the initial value and processors P, and P, are faulty. . a. Tolnlinte th aprenneat procemer Lente poten OM fendsite value tall atber procsso? so chown Fig 39.0 eser) the value x from source processor P,, processors P,P, 3. Afterrecei and P, execute the algorithm OM(0). 4 Brocstsor Py is non-faulty and send value x to processor P, and P processors P, sends valuey to (P,, P,) and 2 ) respectively as shown in Fig. 3.9.2. anna 5. After recei ies, processor P,, P,, P, ler receiving all the messages, processor : if PI *» Py, Pyand P, decide on ity values for Byzantine solution : Procestor | Received majori ‘vod majority/Common majority values BR (,x,2) 3 (xy, 2) ia Le &xy) a its solution. if two processors are f r processors reached among four PF earmarksJoUUBUS LEY Yum pouUeos 3-11B(CSSem-7) rr... System ‘According to majority value table, processors does not agree on single eetrnon majority value, which violates the condition of Byzantine agreement problem. ‘This proves that Byzantine agreement cannot always reach among four processors if two processors are faulty. “Answer In distributed systems, it is often necessary that sites (or processes) intain physi ks that are synchronized with one another. 2 Since pypical sacks have a ih problem, they must be perindcaly resynthesized. ; 3. Such periodie synchronization becomes extremely difficult if the Byzantine failure is allowed because a faulty process can report differest clock values to different processes. 4. Now the assumptions regarding the system are : a. All clocks are initially synchronized to approximately the sam* values. b. Anon-faulty process's clock runs at approximately correct rate. ¢. A non-faulty process can read the clock value of another nor ity process with at most a small error ¢. . A oy synchronization ‘algorithm should satisfy the following a re time, the values of the clocks of all non-faulty proces? pro} ual. ese yun dl > Taulty process is changed daring cach renynbreizaton ‘tion implies that resynd ion does se contin arbitrarily far, thereby preventing the clock rane ig too far from the real time. 128 (08-Sem-7) Agreement Protools Explain the interactive convergence algorithm for clock yyachronization. The interactive convergence algorithm : 1, It is called interactive convergence algorithm because it causes the ‘convergence of non-faulty clocks, “ ‘This algorithm assumes thatthe clocks are initially synchronized and {hoy are recynthesized often enough oo that wo non fay eek aeres difer by more than 6 ‘According to the algorithm, each process reads the value of all other processes clocks and sets its clock value tothe average ofthese values. Itaclock value differs from its own lock value by more than it replaces that value by its own lock value when tang the avestan 5 Theprocessing ofthe algorithm is very simple, & Now, assume the situation where, there are two processes p and respectively, use C,, and C,, as the clock values of a third process © hen computing thir averdn aan 1. Mrisnon-faulty, then Cp = Coe 8 Uris faulty, then 1G, = Cy, 1598 ‘when p and q compute their averages for the n clock values, t rages for values, they both, {Mfrence in the clock values of faulty processes they use is bounded 8 In this way, the aver {iis way, the average value computed by p and g differ by at most Since, n> am Ae (min) 5<5 Thus, each resynchronization brings arunCeh Fesynchronisation brings the locks closer by a factor of 1. This impli Jocks synchronized implies that wecan keep the clocks synchronized withi i , in any ce by resynchronizing them often enough using the almeetaene 880327] Explain interactive con fency algorithm, 1 Inthis, algorithm we, consider two important ‘conditions :JeuUBOS LEY Yum pouueos Distributed System 3:19 B (CS.Sem, 1+ Bie proceaes obtain proximately the same value fora pica, Pa cleck (even if Pis faulty). This condition is important because any two processes almay compute approximate same median ifthey get approximate ak set of clock values for other processes. Cz: If i anon-faulty process, then every non-faulty process cbtsin approximately the correct value for process q's clock, ‘Thus, ifa majority of the processes are non-fulty, the median of the clock values is either approximately equal to a good clo Value or it lies hetween the values of two good clocks, 2 The algorithm is as follows : & _Allthe processes ina system execute an algorithm tocollect value, for clock that satisfy the conditions C,, Cy b Every process uses the median of collected values to compute is new clock value, Que 3.13. ] Write a short note on atomic commit in distributed database system. Answer 1. In the problem of atomic commit, sites of a distributed system mut agree whether to commit or abort a transaction | 2 In the first phase of the atomic commit, sites execute their part oft | distributed transaction and broadcast their decisions (commit or abort) to all other sites. . 1e second phase, each site, based on what it received from other sin the is pass, decides wheat cma aba tof tr distributed transaction. Ifevery site receives an identical response from all other sites, they wil reach the same decision. icingrnpone me sit ve maliciously, they can send a conflicting response! other eieseentag them to makeconflstng decisions. . 6. _Inthese situation, we can use algorithms forthe Byzantine agree to insure that all non-faulty processors reach a common deci adistributed transaction. It works as follows: ; a vn the first phase, after a site has made a decision, ine agreement. eer determine a common decision ba! the second phase, processors; * Ee the agreed vector of values. starts 3-14 (C5-Sem-7) Agreement Protocols RagSAA] What are agreement protocols ? Discuss the general system model where agreement protocols are i applications of agreement protocols. [ARTUR0IEI@; Tnswer Agreement protocols : Refer Q. 3.1, Page 3-28, Unit.3, System model : Refer Q. 3.2, Page 3-28, Unit-a Applications of agreement protocols 1. Fault-tolerant clock synchronization : a. Distributed systems require physical clocks to synchronize. b. Physical clocks have drift problem, © Agreement protocols may help to reach a common clock value. 2 Atomic commit in distributed database system (DDBS) DDBSsites must agree whether to commit or abort the transaction. b. Agreement protocols may help to reach a consensus, PART-4 & $16: Explain typical architecture of Distributed File System ). 1n distributed file system, files can be thine ile system, files can be stored at o i 2 Gqubutation can be performed at other mathine, * TINE and th pmea: machine needs to access a file stored on a remote. muchine, the turng machine performs the necessary file aceon ions a. pacts dataifaread operations performed, SSS PETations and ile server are hi i ‘er are higher performance machines whi Sleand performs storage and retrieval operations MEW store Client machin, chines are used for computat, flea stored on servora ™PUtational purpose and to access th.