Distribute Sys EECS 591
Popular in Course
Popular in Engineering Computer Science
This 77 page Class Notes was uploaded by Ophelia Ritchie on Thursday October 29, 2015. The Class Notes belongs to EECS 591 at University of Michigan taught by Farnam Jahanian in Fall. Since its upload, it has received 13 views. For similar materials see /class/231526/eecs-591-university-of-michigan in Engineering Computer Science at University of Michigan.
Reviews for Distribute Sys
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/29/15
Distributed Naming EECS 591 Farnam Jahanian University of Michigan Reading List Tanenbaum Chapter 4142 43optional Any problem in compuhr scionco can In solvod with anothor Iayor of inclination Distributed Naming Name string of bits or characters referring to an entity resources services mailboxes newsgroups web pages network connections processors Identi er is the unique name associated with an entity 7 Domain names and URLs are good identi ers 7 39 barneyeecsnmichedu identifies a host 39 identifies a service An entity has an access point and the name associated with an access point is an address 7 eg IP address Location independence a name for an entity ie identifier is independent from its addresses ie name of access points Naming What problem does it solve Naming is a layer of indirection Makes objects human readable Hides complexity and dynamics Multiple lowerlayer objects can have one name Changes in lowerlayer objects hidden Allows an object to be found in different ways One object can have multiple names Name Spaces 1 Data stored in n1 quot2 Newsquot f key n3quotmagtltquot 1m t m 715 1quot lhomesteenKeys f quot4 keys twmrc mbox 39 vhcmesteenmnoxquot H13 Leaf node Directory node B A general naming graph with a single root node Names are organized into a name space 7 typically represented as a labeled directed graph with leaf nodes and directory nodes Relative Vs absolute path names Linking and Mounting 1 Data stored in n1 quot2 We hem n3 max V n4 steen n1 n5l Ikeys s t J e39k maxi Data stored m n6 2 la Leafnode D QU L 39 twm b keys We Dlrec39lorynode U V mo X in 751 homesteenkeysquot The concept of a symbolic link explained in a naming graph Linking and Mounting 2 Name server Machine A V w s vunTlhomesteenquot39 Name server forfolelgn name space Machine B Reference to foreign name space Network Mounting remote name spaces through a speci c process protocol Linking and Mounting 3 N81 l home l l l O Q Oquotmmboxquot l elke max steen 777777777777777777 ill O O i twmrc ml keys l O O O quotn3homesteenkeysquot Organization of the DEC Global Name Service Name Space Distribution 1 2 quot m M An aiample pamttontng ofthe DNS name space tncludtng Intemet accessible mes tnto three tayers The name space ts divided tnto nonrovalappmg parts called zones 7 each zone ts tmptemented by a sepamte name server Name Space Distribution 2 Omamzattun DEpanment FEM Maw Secunds Mttttsecunus tmmemate tan tmmemate tmmemate Maw Nune uttew Nune Sumettmes A comparison Name Resolution Name spaces offer a mechanism for storing and retrieving info about entities by means of names The process oflooking up a name is called name resolution Name resolution service maps names to addresses Iterative vs recursive name names resolution Implementation of Name Resolution 1 1 ltnlvucsftpgt Root 777777777777 7 lt 2 ltngt ltvulcSl pgt name server 7777777777 n 7 nl 4 ltvugt ltcslftpgt nl node r V V V V V r V V V lt 6 ltcsgt lt pgt vu nOde 777777777777 N MP gt Name server 8 41 cs node Nodes are managed by the same server 3 ltvucsf39tpgt ltnvucsf tpgt T Lltnvucsf tpgt Iterative Name Resolution Implementation of Name Resolution 2 1 ltnvucsf tpgt 4 Root 8 ltnIVUCS Pgt name server 7 ltvucs pgtL Name server nlnode 6 ltcsf tpgtk Name server vu node 5 ltf39tpgtL Name server cs node ltnvucsf tpgt T Lltnvucsf tpgt 2 ltvucsf39tpgt 3 ltcsf39tpgt 4 ltf39tpgt Recursive Name Resolution Implementation of Name Resolution 3 Sewer for Receives and Returns to node Should resolve Looks up Passes to chlld caches requester cs lt pgt lt pgt lt pgt vu ltcs pgt ltcsgt lt pgt lt pgt ltcsgt ltcs a ni ltvucs pgt ltvugt ltcs pgt ltvugt ltcs pgt ltvucsgt ltvucs pgt root ltnivucs pgt ltnlgt ltvucs pgt ltvugt ltnlgt vucsgt ltnvugt ltvucs pgt ltnlvucsgt ltnlvucs pgt Recursive name resolution of ltnl vu cs ftpgt Name servers cache intermediate results for subsequent lookups Implementation of Name Resolution 4 Recursive name resolution 7 7 i 77 gt Namesewev 739 nlnode iVN l2 gtName sewer 7 7 Va node 73 quot 7 r s 7 7gtNamasawer 1R3 lteratwe name resolution 25 nude Longrdlsmnce communication R2 TL respect to communication costs Domain Name System DNS Distributed directory service DNS is simple but powerful Hierarchical name space Each level separated by 7 Analogous to separator in le systems One global root Replicated across lt20 root servers There have been Denial ofService DoS attacks on these root servers none real successful Because of caching queries to root servers relatively rare Domain Name System DNS DNS is a Hierarchical name space 7 A subtree is called a domain 7 A path name to its root is called a domain name 7 A domain name can be relative or absolute The name space is divided into nonoverlapping parts called zones 7each zone is implemented by a separate name serv The contents of a node is defined by a collection of resource records Only one type of query Queryd0main name RR type 7 Resource Record RR type is like an attribute type Answervalues additional RRs Limited number ofRR types Hard to make new RR typesbut not for technical reasons because each requires global agreement The DNS Name Space 2 f Eggclam Description SOA Zone Hoids information on tne represented zone A Host Contains an iR address of tne nosttms node represents MX Domain Refers to a maii seiyerto nandie maii addressed to tnis node SRV Domain Refers to a Sewerhandling a spedfc seiyice NS Zone Refers to a name seiyertnat impiements tne represented zone CNAME Node Symbolic link Witn tne primary name oftne represented node PTR Host Contains tne canonicai name of a Host H NFO Host Hoids information on tne nosttms node represents TXT Any kind Contains any entity pecific information considered dsefdi The most important types of resource records forming the contents of nodes in the DNS name space DNS Implementation 1 Name I am type 7 Fecal value asvunl s A starimaginingmoosaauzalszmwm A excerpt from mm m stay mu m me DNS tsmnl Dunswnl usvum K mm database for the as vu m T we umemew rMasn 5 Comp Sc zone mm M E Vquot 39 39m quot w m z tornado mu m 1 suunl swcsvum slar 6 VJ m so Sun a implemented as 1 53 as vu x 5mm w smmu l V zephyycsvu m a 5mgle zone l 5 as w m m 7 2 cs 92 3 Sunumx 1 mngusw m w zephyrg vu HI 13937 26H PC Msuos 1 73022 uzsswzm aunram 30an DNS Implementation 2 Name Record type Record value svu m NS sum 5 W m sum svu m A wan 37 2M PaIt of the description for the vunl domain which contains the csvunl domain Primary and Secondary Servers Each zone is implemented by a name server replicated for availability Updates are handled by primary server by modifying local DNS DB Secondary requests the primary server to transfer its content R for all the nodes in a zone are kept in the local DNS DB DNS Cache Management All RRs have Timeto live TTL values When TTL expires cache entries are removed NS RRs tend to have long TTLs reduces load on higherlevel servers A RRs may have very short TTLs l min for web services 1 day for typical hosts 7 What if you want a quick failover for web servers Keep TTL for web server s A RRs very short Why is DNS iterative and not recursive Locating Mobile Entities Section42 Mobile entity 7 An entity whose address often changes laptop running DHCP 7 Not necessarily physical mobility eg dialup Is mobility an issue for DNS 7 NOT REALLY 7 Mobility in practice affects leaf DNS servers A RR TTL is short but NS RR TTL is long What is the problem 7 Most mobile nodes are clients servers are rarely mobile 7 Clients initiate connects not receive it 7 Special cases email instant msg ing VolP Applicationspeci c registration Clients connects to email server IM server SIP server Naming versus Locating Entities 531 Location service Address Address Address Address Address Address a b a Direct single level mapping between names and addresses b Two level mapping using identities Separation of naming name 9 identifier frorn locating identifier 9 current location Location Service Simple solutions for LANs NOT Scalable 7 Broadcasting amp multicasting similar to ARP Drawback in practical for large networks hardware support needed 7 Forwarding pointers when moving from A to B leave a forward reference behind Many drawbacks long chains reliance on intermediate nodes broken links Mobile IP approach homebased approach 7 Introduce a home location that keeps track of current location of an entity 7 Mobile nodes has a stable home address at its home network home agent with xed IP address 7 When a mobile node moves it gets a care of address This address is registered at the home agen 7 When the home agent receives a packet for the mobile node If it s still at home local network just forward the packet Otherwise the packet is tunneled to the current location of the mobile node 9 wrapped in an 1 packet and sent to the careofad ress Sender may be informed of the mobile node s current location optional Location Service Issues with Mobile IP approach 7 Increased communication latency a problem in largescale networks Twotier or hierarchical 7 Fixed home location must be highly available 7 What if the nodes moves permanently Use traditional name service Twotier or hierarchical approaches 7 Scalability 7 PCS Forwarding Pointers 1 Process P2 Proxy p refers to same skeleton as pI39OXy p Process P3 Identical proxy 7 Process P1 Skeleton Proxy p Process P4 Object Local 1 invocation Interprocess communication ldentical skeleton The principle of forwarding pointers using prwcy Skeleton pairs Forwarding Pointers 2 Skeleton gt5 no Invocaitpn unger reierenced reques 5 an mx senttaobject y W V v i 4 r L2 1 r Skeleton at object s Chant proxy sets cunth pmcess retums 7 shortcut Ihe cunem location a b Redirecting a forwarding pointer by storing a shortcut in a my HomeBased Approaches Mobile IP 2 Relum addvess m cuvrent locauan cnenrs Iocanan k J 4 Send Successive packets mcunemmczucn 1 Hnsrs presem Iocamm The principle ofMobile IP Hierarchical Approaches l The root directory no Toplevel domain T 4 Directory node dirS of domain 8 A subdomain V 4 A leaf domain contained in S S of toplevel domain T S Is contained in T Hierarchical organization of a location service into domains each having an associated directory node Location record with only one field containing an addres Domain D1 An example of storing information of an entity having two addresses in different leaf domains u o u Hierarchical Approaches 2 Field with no data Field for domain an domN with pointer to N ixe Location record for E at n ode M Domain D2 Node has no record for E so that request is forwarded to parent Hierarchical Approaches 3 Node knows about E so request is forwarded to child 3 Domain D Looking up a location in a hierarchically organized location service Hierarchical Approaches 4 Node knows Node has no nsen request a entity E b about E so request is no longer forwarded Node creates record and stores pointer i i M Node creates record and stores address b An insert request is forwarded to the first node that knows about A chain of forwarding pointers to the leaf node is created Pointer Caches 1 Domain D Cached Winters E moves regularly between to Ode drD the two subdomains Caching a reference to a directory node of the lowestlevel domain in which an entity Will reside most of the time Pointer Caches 2 Cached pointer to node dirD which should be invalidated Original address A is still valid New address 0 A cache entry that needs to be invalidated because it returns a nonlocal address While such an address is available Consistency and Replication part b EECS 591 Farnam J ahanian University of Michigan Tanenbaum Chapter 6165 Eventual Consistency A very weak consistency model characterized by the lack of simultaneous updates or easytoresolve simultaneous updates by a small set of processes Common property of data stores with eventual consistency if no update takes place for a long time all replicas will gradually become consistent ie propagate updates to all replicas in a lazy fashion Cheap to implement later Examples DNS name space partitioned into domain each domain is assigned to a single naming authority responsible for making updates updates propagated to all copies in a lazy fashion Web pages typically updated by a single client no write Write con icts cache copies may be outofdate acceptable to have inconsistency for a short interval Example mobile user accessing different replicas Client moves to other location and transparently connects to other replica ng 8 Replicas need to maintain client centric consistency Widearea network Distributed and replicated database 7 Read and write operations Portable computer 0 Eventual consistency is easy to implement if a client always accesses the same replica 0 If the user disconnects and reconnects to another replica it may observe inconsistencies in the data store Clientcentric consistency is one such model ClientCentric Consistency Originated from the work on Bayou DB for mobile systems Wireless access andor unreliable network connectivity Provides guarantees for a single client s access to a replicated data store No guarantees concerning accesses by different clients Four models in clientcentric consistency Monotonic Read Consistency Monotonic Write Consistency Readyour writes Consistency Writesfollowsreads Consistency Monotonic Reads If a process reads the value of a data item x any successive read operations on x by that process will always return that same value or a more recent value ie P sees x it will never see an older version of x L l WSX1 Rm L2 WSX1X2 R09 60 L1 W8x1 Rm L2 WSX2 RX2 WSX1JX2 b The read operations performed by a single process P at two different local copies of the same data store a A monotonicread consistent data store b A data store that does not provide monotonic reads Monotonic Writes A write operation by a process on a data item x is completed before any successive write operation on x by the same process ie a wrote operation on a copy of data item is performed only that copy has been brought up to date by mean of any preceding write operation even taken place on another copy 0fx L l Wx1 L2 woo We a L l Wx1 L2 W 2 b The write operations performed by a single process P at two different local copies of the same data store a A monotonicwrite consistent data store b A data store that does not provide monotonicwrite consistency Read Your Writes The effect of a write operation by a process on data item x will always be seen a successive reacl operation on x by the same process ie a write operation is always completed before a successive reacl operation by the same process no matter where the read takes place L1 I W09 L23 WSX1X2 RX2 a L1 Wx1 L23 WSX2 R09 b a A data store that provides readyourwrites consistency b A data store that does not Writes Follow Reads A write operation by a process on a data item x following a previous read operation on x by the same process it is guaranteed to take place on the same or a more recent value of x that was read ie any successive write operation by a process on x will be performed on a copy of x that s up to date with the value most recently read by that process L1 3 W509 R09 L23 WSX1X2 32 3 L1 WSX1 R09 L23 W332 WW 2 b a A writesfollowreads consistent data store b A data store that does not provide writesfollowreads consistency Design Issue Replica Placement So far we discussed datacentric and clientcentric consistency models Replica placement 1 Permanent Replicas Typically small number of permanent replicas Examples Replicated copies on a cluster of serversworkstations Mirrored copies geographically distributed 2 Serverinitiated replicas Cached copies of data pushed created by the server to enhance performance Dynamic replication When to create and delete replicas 0 Dynamic replication is key for web hosting services recall discussion on Akamai Note static collection of servers dynamic placement of replicated data on these servers close to demanding clients 3 Clientinitiated replicas Also known as client caches 0 Local copy kept close to client to enhance read performance Cache copy on client machine copy on a storage device or a server on the same LAN as client copy in the network e g service provider network serving the client Replica Placement gt Serverinitiated replication gt Clientinitiated replication Server initiated replicas The logical organization of different kinds of copies of a data store into three concentric rings ServerInitiated Replicas 002 Server without I copy of file F r P In a Client x an Q Server With x men 1 gcopy ofF C 1 c Flle F Server Q counts access from C1 and C22 as if they would come from P Counting access requests from different clients Design Issue Update Propagation 0 An update must be propagated to other copies While maintaining consistency Issue 1 Transfer state data to copies vs execute operation at replicas Issue 2 replica or cache invalidation vs transfer data writethru Best for Low readtowrite ratio vs best for high readtowrite ratio 0 Issue 3 Push vs pull protocols Tighter consistency vs looser consistency Serverinitiated vs clientinitiated See chart on next page 0 Issue 4 Exploit multicast in pushbased protocols if available Pull versus Push Protocols Issue Pushbased Pullbased State of server List of client replicas and caches None Messages sent Update and possibly fetch update later Poll and update Response time at client Immediate or fetchupdate time Fetchupdate time Readtoupdate ratio Best if high Best if low A comparison between pushbased and pullbased protocols in the case of multiple client single server systems Consistency Protocols A consistency protocol describes a speci c implementation of a consistency model Most common consistency models in practice sequential consistency weak consistency with synchronization variables eventual consistency atomic transactions Terminology other texts Primaryback approach Passive replication Statemachine approach Active Replication Consistency Protocols Discussed Primarybased protocols Remotewrite protocol With no backup replica Remotewrite protocol primarybackup approach passive replication Localwrite protocol With single migrating primary copy no backup Localwrite protocol With migrating primary copy and nonmigrating backups Primarybackup approach Replicatedwrite protocols Active replication Quorumbased protocols Epidemic Protocols eventual consistency Cachecoherence protocols Primarybased Approach no backup replication Client Client Single server for item X Backup server w vw R1 R4 1L W2 R2 L E U WUT U Data store W1 Write request W2 Forward request to server for x W3 Acknowledge write completed W4 Acknowledge write completed R l Read request R2 Forward request to server for x R3 Return response R4 Return response Primarybased remotewrite protocol With a xed server to which all read and write operations are forwarded PrimaryBackup Protocol remotewrite protocol Client Client Primary server for 39tem x Backup server W1 W5 R1 R2 Vl it u W4 f a W4 4 gt Wi U Data store W2 W3 W4 W1 Write request R1 Read request W2 Forward request to primary R2 Response to read W3 Tell backups to update W4 Acknowledge update 39 39 W5 Acknowledge write completed BIOCklng VS39 non bIOCklng update of backups LocalWrite Protocols no backup replica Client Current server New server for item x for item x 1 4 Data store 1 Read or write request 2 Forward request to current server for x 3 Move item x to client39s server 4 Return result of operation on client39s server Primarybased localwrite protocol in which a single copy is migrated between processes LocalWrite Protocols PB Approach with Migrating Primary Client Client Old primary New primary for item X for item X Backup server R1 R2 W1 W3 A L W5 lL ws lt tj W l W4 Data store W5 L W4 W2 J W l Write request R l Read request W2 Move item x to new primary R2 Response to read W3 Acknowledge write completed W4 Tell backups to update W5 Acknowledge update Primarybackup protocol in which the primary migrates to the process wanting to perform an update Replicated Writes Active Replication Approach Also known as statemachine replication Alternative to PB approach Every replica is a primary no backup Each replica has an associated process each update is sent in the form of an operation to all replicas which execute the operation All updates ie operations need to be carried out in the same order at all replicas 9 the state of all replicas are updated in the same order totallyordered multicast is the underlying mechanism for active replication Scalability is an issue Clients Replicated Servers Active Replication problem of replicated invocations Client replicates f a invocation request Object receives the same invocation l i three times All replicas see the same invocation Replicated object o The problem of replicated invocations A invokes B which in turn invokes C What if B is replicated Multiple invocations of C for the same operation Active Replication Coordinator of object C Coordinator of object B m m Client replicates invocation request Result 8 Forwarding an invocation request from a replicated object b Returning a reply to a replicated object a Replicated Writes QuorumBased Protocols Use voting a client requests and acquires replies from multiple clients before reading or writing e g N replicated server a client must contact at least one half plus one servers to perform a read or update operation Quorum is more general than simple majority N replicas Nr read quorum servers NW write quorum servers Nr and NW are subject to 0 NrNW gt N prevent rW con icts 0 NW gt N2 prevent WW con icts Many variations QuorumBased Protocols Read quorum A B l l A B c D f39 E F G H i i E G H i J K L 39C39 L J K L c ax NR3 NW10 NR1 NW12 Write quorum a b C Three examples of the voting algorithm a b C A correct choice of read and write set A choice that may lead to writewrite con icts because NW lt N2 A correct choice known as ROWA read one write all 1 Epidemic Protocols Ensures eventual consistency Epidemic spreading of updates propagates updates to all replicas ef ciently Highly scalable approach Does not solve any update con icts directly Terminology Infective a server that holds an update and it is willing to spread Susceptible a server that has not been updated Removed a server that is not willing or able to update EECS 591 Winter 2003 Handout 4 The ClientServer Model Section 15 Tanenbaum Handout in class RPC Section 22 Tanenbaum Section 73 Tanenbaum The ClientServer Model Key Idea Structure a distributed system as a collection or group of cooperating processes called servers that offer services to users called clients 39 I request T I Examples The ClientServer Model Wait for result Client Req uest Server Prowde serwce Time 4 General interaction between a client and a server Processing Level 1 Userinterface User Interface J level HTML page Keyword expression conta39n39ng 5t HTML generator Processing Query Ranked list level generator of page titles RanMng Database queries component Web page titles L with metainformation Database Data level with Web pages The general organization of an Internet search engine into three different layers Multitiercd Architectures 1 Client machine I User interface i User interfacei i User interface i User interfacei i User interface i l xv Application Application i Application a quotquot Na L Database ser interface I quot i Application i i Application i ihApplication fir Ira i Database i i Database i i Database i i Database i i F Database Server machine a b C d 9 Alternative clientserver organizations a e Multitiered Architectures 2 User interface Wait for result presentation Request Return operation result Wait for data Application server Request data Return data Database server Time An example of a server acting as a client Modern Architectures Front end handHng incoming Replicated Web servers each requests containing the same Web pages Requests Q Q gra Disks handled In A gt roundrobin s E9 I fashion I I m r F d An example of horizontal distribution of a Web service Remote Procedure Call First suggested by Birrell amp Nelson in 84 Remote ops in the guise of a procedural interface Perform ops on other machines asif they were local No 10 no msg Visible to the programmer Middleware Protocols Application protocol Application 6 Middleware protocol M iddleware 39 5 Transport rotocol Transport quotquotquotquotquotquotquot quotB quotquotquotquotquotquotquot quot 4 Network prgtqqqln Network 3 DEEUIUE PIQIQQQL Data link 2 Rh igat protocol Physical 1 Network An adapted reference model for networked communication Conventional Procedure Call Stack pointer Main program39s Main program39s local variables local variables 9 bytes buf fd return address read39s local variables a b a Parameter passing in a local procedure call the stack before the call to read b The stack While the called procedure is active Client and Server Stubs Wait for result Client 4 k Call remote Return procedure from call Request Reply Server Call local procedure Time gt and return results Principle of RFC between a client and server program Steps of a Remote Procedure Call Client procedure calls client stub in normal way Client stub builds message calls local OS Client39s OS sends message to remote OS Remote OS gives message to server stub Server stub unpacks parameters calls server Server does work returns result to the stub Server stub packs it in message calls local OS Server39s OS sends message to client39s OS Client39s OS gives message to client stub 10 Stub unpacks result returns to client wwsgwewwr Issues Why is RPC more than a syntactic change Exchanging messages between different processors arch Littleendian vs bigendian Character representation Sending pointers What s parameter marshalling Exchanging data structures between programs in different languages on two different architectures Should the transport protocol be able to handle this issue Dynamic binding RPC semantics in the presence of failures Passing Value Parameters 1 Client machine Server machine Client process Server process 139 Client can to Implementation d proce ure of add k dd Serverstub k dd i I Chentsmb 2 Stub builds Int message Int vaj Client 08 int yam ServerOS k Int vaJ 6 Stub makes local call to quotaddquot 5 Stub unpacks message 4 Server 08 hands message to server stub 3 Message is sent across the network Steps involved in doing remote computation through RPC Passing Value Parameters 2 a Original message on the Pentium b The message after receipt 0n the SPARC c The message after being inverted The little numbers in boxes indicate the address of each byte Parameter Speci cation and Stub Generation foobar39s local a A procedure var39ables X b The corresponding message y 5 ZM ZW foobar char x float y intz5 z2 Z4 a b Note IDL to support application development Two Extensions to RPC Doors RPC for processes on he same machine Asynchronous RPC Doors Computer Client process Server process serverdoor q tloorreturn Enamo gnaino Lizrogglrlw fgjoor3 lame39 3 Register door fd door create fattachfd doorname v Operating system L X j A Invoke registered door at other process Return to calling process The principle of using doors as IPC mechanism Asynchronous RPC 1 Ghent Wait for result Client Wait for acceptance 1 K 1 k Call remote Return Ca remote Return procedure from call procedure from call Request Reply Request Accept request Server Ca local procedure Time gt Server Call local procedure Time gt and return results a b a The interconnection between client and server in a traditional RPC b The interaction using asynchronous RPC Asynchronous RPC 2 Wait for Interrupt client acce tance Client gt1 it Call remote Return R t du from call e um proce re results Acknowledge Accept RequeSt request Server r Mf Call local procedure K Time gt Call client with oneway RPC A client and server interacting through two asynchronous RPCs Binding a Client to a Server 3 Look up server Client machine Client 39 Directory machine Directory server VL 5 Do RPC 4 Ask for endpoint Locate the server s machine Locate the service on that machine Server machine twister service gt Server DCE a 7k daemon 1 Register endpoint Endpoint table RPC Semantics in the Presence of Failures The client is unable to locate the server The request message from the client to the server is lost The server crashes after receiving a request The reply message from the server to the client is lost The client crashes after sending a request Lost Request Messages Server Crashes 1 REQ Server Receive Execute REP Reply a REQ Server Receive Execute 0 ESEquot b REQ Server Receive N0 REP A server in clientserver communication a Normal case b Crash after execution c Crash before execution C 4 Group Membership Service EECS 591 Handout 5 part c Farnam Jahanian Department of EECS University of Michigan EECS 591 Lecture Notes httpwwweecsumichedufarnam Reading List 0 Section 139 in Building Reliable and Secure Network Applications by Ken Birman 1997 o Tanenbaum Section 72 Group Membership Problem 0 Agreement on the membership of a group of cooperating processes in a distributed system 0 Consistent systemwide view of the operational members in the presence of oz processor or process failure oz processor or process join oz processor or process departures communication failure 0 Group Membership Service maintains membership of a distributed system on behalf of processes that compose it GMP Informal Definition o All operational members see the same sequence of view transitions 1 Linear order on system view changes 0 See Figure 1 0 Several research papers formally define the problem beyond the scope P1 P2 P3 P4 Figure 1 GM View Changes I l P1 jOInS P4 jOInS P2j0nS F 3JOIns P1 fails I I P2 joins P3joinS P1 fails I P3 joins P P4joins P2joins P3 joins P P1 P1P4 P1P4P2 P1P4P2P3 P4P2P1 What is difficult about this problem 0 Main Challenge in Asynchronous Systems It is difficult to distinguish between a process that has crashed and a process that is very slow Perceived failure of processors due to message loss or communication delay Timeouts it is impossible to determine with absolute certainty whether a processor has crashed in an asynchronous distributed system 0 Related issues 2 Initial system startup bootstrap problem 2 Multiple concurrent failures Coordinator failurepartition handling 0 O O Precise meaning of a consistent view o Heartbeathardware multicast support 0 Coordinatorbased Approach 0 Used in many group communication systems including ISIS Horus RTCAST Amoeba 0 Unique identifier for each member eg lP addr processid 0 Linear ordering of member ids o Designate a coordinator or manager for maintaining and disseminating membership information 0 Two cases member noncoordinator failure 2 phase protocol coordinator failure 3phase protocol Case 1 Noncoordinator Failure failure 0 X X removeQ CommitQ coordinator Y V V Z Phase I Phase II Case 2 Coordinator Failure failure v Q coordinator X interrogation propose commit Y z V V Phase I Phase II Phase III Coordinator Failure x Heartbeat 4 gt Partition Handling 0 Primary partition group eg ISIS system majority partition continues membership of subsequent group should overlap with the membership of current group minority group suspends potential for singleton groups and lack of progress 0 Allow partitions and remerge eg Transis system 0 Allow nonoverlapping simultaneous groups Node1 Membership Daemon Service Model Node2 Membership Daemon Node3 Membership Daemon
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'