W distributed Computing 1 Introduction, 1.2 Examples of Distributed System. 1.2.1 Internet 1.2.2 Intranet 123 Mobile and Ubiquitous Computing... 13 Resource Sharing and the Web... 1.3.1 World Wide Web (WWW). 14 Issues and Goals. 141 Heterogencity..... 142 Making Resources Accessible, 143 Distribution ‘Transparency. 144 Scalability. 145 Openness... 15 Types of Distributed systems, 151 Distributed Computing System: 15.1(A) Cluster Computing Systems... 1.5.1(B) Grid Computing System: 15.2 Distributed Information systems, 15.2(A) Transaction Processing Systems. 15.3, Enterprise Application Integration 1.5.4 Distributed Pervasive Systems, 1.6 Hardware Concepts. 1.6.1 Multiprocessors,Distributed Oberating systems, Network Operating systems, 18 Middleware. Positioning Middleware, Models of Middleware 181 19 Imterprocess Communication (IPC) 24.1 Types of Communication, Remote Procedure Call (RPC). 22.1 RPC Operation... 2.2.2 Implementation Issues, 2.2.3 Asynchronous RPC. 224 — DCERPC. Remote Object Invocation,, 23.1 Distributed Objects (RMI: Remote Method Invocation)... Message-Oriented Communication. . 241 Persistence Synchronicity in Communication. 24.2 Combination of Communication Type: 24.3 Message-Oriented Transient Communication... 244 Message-Oriented Persistent Communication... 5 Stream-Oriented Communication.. 25.1 Continuous Media Support.Table of Contents 21g 2-19 2-20 2-20 st-Aarawale's Algorithm, d Algorithm, Comparative] W distributed Computing 36 37 38 1 Table of Contents san AG 35.2 Ricart-Agrawala’s Algorithm 353 Centralized Algorithm... 3.54 Maekawa's Algorithm. ‘Token Based Algorithms, 36.1 Suzuki-Kasami’s Broadcast Algorithm... 36.2 Raymond's Tree-Based Algorithtt .n.- Comparative Performance Analysis of Algorithms. 3.7.1 Response Time. 3.72 Synchronization Delay 3.73 Message Traffic. Deadlock... 3.8.1 Introduction.. 382 Resource Allocation Graphs. 383 Deadlock Prevention and Avoidance in Distributed System 3.84 Deadlock Detection. 3.8.4(A) Centralized Approach... 3.84(B) Fully Distributed Approach. 4110419 TT ‘Chapter 4: Resource and Process Management Desirable Features of global Scheduling algorithm, Task assignment approach, Load balancing approach, load sharing approach ntzoduction to poness management, process migration, Code Migration. 41 42 43 44 Introduction.. Desirable Features of Global Scheduling Algorithm ‘Task Assignment Approach. Load-Balancing Approach. 44.1 Classification of Load Balancing Algoriths smn 442 Issues in Designing Load-Balancing Algorithms... Load-Sharing Approach... 45.1 Issues in Designing Load-Sharing Algorithms. Introduction to Process Management Process Migration.W_bistributed computing 5 4.7.1 Desirable Features of Good Process Migration Mechanism. 4.7.2 Process Migration Mechanisms. 47.3 Process Migration in Heterogeneous System. 4.7.4 Advantages of Process Migration.. 415 48 Code Migration... 15, 4.8.1 Approaches to Code Migration.. 415 4.8.2. Migration and Local Resources. 17 4.8.3 Migration in Heterogeneous Systems. 4-18 Chapter 5: Replication, Consistency and Fault Tolerance 5-1 105-29 ee eatin, Constotoncy and Fault Toterance tt 5g Distributed Shared Memory: Architecture, design lesues. Introduction to replication and consistency, Data-Centric and Clent-Conal [Consistency Models, Replica Management. Fault Tolerance: Introduction, Process resilience, Recovery. 5.1 Introduction to Distributed Shared Memory... 5.1.1 Architecture of Distributed Shared Memory (DSM 5.1.2 Design Issues of Distributed Shared Memory (DSM). 5.2 Introduction to Replication and Consistency. 5.2.1 Reasons for Replication unum 5.2.2 Replication as Scaling Technique... 5.3 Data-Centric Consistency Models... 5.3.1 Continuous Consistency 5.3.2 Consistent Ordering of Operations. 5.4 Client-Centric Consistency Models. 5.4.1 Eventual Consistency nn. 5.4.2 Monotonic Reads.. 5.4.3 Monotonic Writes. 5.4.4 Read Your Writes. 5.4.5 Write Follows Reads 5.5 Replica Management 5.5.1 Replica-Server Placement. 5.5.2 Content Replication and Placement. 5.5.3 Content Distribution... 58 Chapter 6 Faulk 561 562 563 Proce 574 572 873 574 Recov 584 52 583 54 585 Dis troduction and fo system (NFS), Des 641 62 65 Introduc Desirabl File Mod 63a 632 File-Acce 644 642 File-cach 65.4 652 653 |W Distributed Computing 5.6 87 58 61 62 63 64 65 introduction and features of DFS, File models, system (NFS) Designing Distibuted Systems: Google Case Study. G Table of Contents Fault Tolerance. 5.6.1 Basic Concepts... 5.6.2 Failure Models.. 5.6.3 Failure Masking by Redundancy. Process Resilience.. 5.7.1 Design Issues. 5.7.2. Failure Masking and Replication. 5.7.3. _ Agreement in Faulty Systems 5.7.4 Failure Detectior Recovery. 58.1 _ Introductior 58.2 _ Stable Storage. 5-26 5.8.3 Checkpointing. ne 5-28 5.8.4 Message Logging, 585 Recovery-Oriented Computing. File Accessing models, File-Caching Schemes, File Replication, Introduction. Desirable Features of a Good Distributed File System. File Models... 63.1 Unstructured and Structured Files... 63.2 Mutable and Immutable Files. File-Accessing Models.. 64.1 Accessing Remote Files.. 64.2 Unit of Data Transfer File-Caching Schemes... 65.1 Cache Location. 65.2 Modification Propagation 65.3 Cache Validation Scheme:67 68 Replication and Caching... 6.6.2 Advantages of Replication... 663 Replication Transparency, 6.64 Multicopy Update Problem Google Applications and Services. 68.3 Google Infrastructure . ‘Qog—_—_ PReeRery 1 , Introduction to Distributed Systems Siesta Characterization of Distributed Systems : Issues, Goals, Types of distributed systems, Grid and Cluster computing Models, Hardware and Software Concepts: NOS, DOS. Middleware : Models of Middleware, Services offered by middleware, Characterization of Distributed Systems 1.1 __ Introduction The development of powerful microprocessors and invention of the high speed networks are the two major developments in computer technology. Many machines in the same organization can be connected together through local area network and information can be transferred between machines in a very small amount of time. As a result of these developments, it became easy and practicable to organize computing system comprising large number of machines connected by high speed networks. Over the period of last thirty years, the price of tions technology has constantly reduced in real terms. microprocessors and commu Because of this, the distributed computer systems appeared as a practical substitute to uniprocessor and centralized systems. The networks of computers are present all over. Internet is composed of many networks. All these networks separately and in combination as well, share the necessary characteristics that make them pertinent topics to focus under distributed system. In distributed system, components located on different computers in network communicate and coordinate by ics of the distributed system. passing messages. As per this argument, following are the characte © Internet © Intranet, which is small part of internet managed by individual organization. © Mobile and ubiquitous computing. Resources required for computation are not available on single computer. These resources which are distributed among many machines can be utilized for computation and it is main motivation behind distributed computing, Followings are some of the important issues that need to be considered. Concurrency © The different cooperating applications should run in parallel and coordinate by utilizing the resources which are available at different machines in network. wIntroduction w istributed Computing 1-2 aaa Distributeg 2. Global Clock not Available * Cooperation among applications running on different machines in network is achieved by rth messages. For cooperation, applications action at particular time is exchanged. But, i is not easy tg tees Machines clocks with same time. \ * _ Iis difficult to synchronize the different machines clock in network. Therefore, it is CES to Consideration that single global clock is not available and different machines in LAN, MAN or WAN have tig, clock time, 3. Independency in Failure of System Component * Any individual component failure should not affect the computation. It is obvious that, any Software oy | ath, component of the system may fall. * This failure should not affect the system from running and system should take appropriate action for recone, Definition of Distributed System * Acomputer network is defined as a set of communicating devices that are connected together by communica links. These devices include computers, printers and other devices capable of sending and/or receiving inom, ‘rom other devices om the network. These devices often called as node in the network. So computer neti interconnected set of autonomous computers. * A distributed system is defined as set of autonomous computers that appears to its users as a single cohen ‘stem. Users of distributed system fee that, they are working with a single system, Following are the main characteristics of distributed system. © A distributed system comprises computers with d dissimilarities and istinct architecture and data representation Te the ways all these machines communicate are hidden from users. © The manner in which distributed system is o ganized internally is also hidden from the users of the dist” system ° The interaction of users and applications with distrib uted system is in consistent and identical way, in spt where and when interaction occurs, © Addistributed system should allow for Scaling it, in spite of failures © Failure handling should be hidden from users and applications. facilities. © In Fig. 1.1.1, applications are running on three different machines A, B and C in network.1 Introduction to Distributed Systems istributed Computing Computer A. Computer B Computer C Distributed Applications 2 Examples of Distributed System 2.1 Internet Applications running on different machines communicate with each other by passing messages. This communication is possible due to different protocols designed for the same purpose Internet is a very large distributed system. User at any location’ in network can use services of World Wide Web, email file transfer etc. These services can be extended by addition of servers and new types of services. Internet Service Provider (ISP) provides internet connection to individual users and small organizations. Email and web hosting like local services are provided by ISP and it also enable the users to access services available at different locations in internet. .2.2 Intranet Intranet is small part of internet belonging to some organization and separately administrated to enforce local security policies. Intranet may comprise many LANs which are linked by backbone connection. Intranet can be administrated by administrator of single organization and its administration scope may vary ranging from LAN on single site connected to a connected. LANs that is part of many braches of companies. Router connects intranet to internet and user in intranet then can use services available in rest of the internet. Firewall which filters incoming and outgoing messages protects unauthorized messages to enter or leave the intranet. 2.3. Mobile and Ubiquitous Computing Many small and portable devices manufactured with advancement in technology is now integrated into distributed system. Examples of these devices are Laptop, PDAs, Mobile phones, Cameras, pagers, smart watches, devices embedded in appliances, cars and refrigerators etc. ‘As these devices are portable and easily gets connected, mobile computing became possible. Mobile users can easily use resources available in network and services available in internet. Ubiquitous computing ties together the many small chip devices in available physical environment of home, office or elsewhere. In mobile computing, user location can be anywhere but can use resources available everywhere. Whereas, in ubiquitous computing users are in same physical environment and gets benefited.Introduction to Distro, and exchange information, The mail, documents, audio, ang merce Permits us yo Py 1-6 ier to work together files, Electronic com Wistributed Computing * By connecting users and resources, the Internet is due to its straightforward P upware. worldwide spread people can work together by rans of 30 ‘pao it shop or even leavin: a and sell verity of goods without going to shop ak and to deal with iS equa ne ication. it becomes easi rotocols for exchanging securit) " or intrusion on communi fi rticular user. This clearly violate, favorite profile of @ pa ; papties oblem with increased connectivity can ay. called as spam. Special information fitter, the s ©The increase in connectivity and sharing also increases Presently, systems offer fewer defenses against eavesdropping * A communication can be tracked to | particularly if it is done without informing the user. A allied pr unnecessary communication, for example electronic junk mall used to select inward messages based on their content % 1.4.3. Distribution Transparency em is to hide the actuality of physical distribution of Process | of a distributed syst i The second main goal of a offers its feel to users and applications ag, resources across several computers. A transparent distributed system computer system. Following types of transparency is present in distributed system. similarities of data representation of different machines in the netyo, Intel machines use little endian format ty, in beginning and in, ‘* Access Transparency : It hidesthe dis: the manner in which remote resources are accessed by the user. bytes and SPARC uses big endian format. So Intel machines transfer high order bytes SPARC low order bytes are transmitted first. Different operating systems also have their own file name cones All these dissimilarities should be hidden from users and applications. / * Location Transparency : This transparency hides the location of the resources in distributed system. For URL used to access web server and file does not give any idea about its location. Also name of the r remains same although it changes the location when moved between machines in the distributed system. * Migration Transparency : It hides the fact that resources are moved from one location to other. It does not the way in which these resources are accessed. Processes or files often are migrated by system to improe performance. All this should remain the hidden from user of the distributed system. ‘* Relocation Transparency : If the user or application is using the resource and during use of it is if movedta location then it remains hidden from user. For example if user is traveling in car and changing the frequently, still he or she continuously uses the laptop without getting disconnected. * Replication Transparency : It hides the fact that many copies of the resource are placed at different | Often resources are replicated to achieve availability or placed its copy near to location of its access. This. the replication should be transparent to the user. * Concurrency Transparency : It hides the sharing of the resource by many users of the distributed system! user is using the resource then other should remain unknown about it. Many users can have stored their file server. It is essential that each user does not become aware of the fact that other is using the same This is called concurrency transparency. * Failure Transparency : It hides the failure and recovery of the resource from user. User does not become failure of resource to work appropriately, and that the system then recovers from that failure. It is not po achieve complete failure transparency, Because for example, if network fi user can notice this failure.Introduction to Distributed Systems tributed Computing ‘© Performance Transparency : In order to improve performance system automatically takes some action and it user remains unaware of this action taken by system. In case of overloading of processor jobs gets transfer to lightly loaded machine. If many requests are coming from users for a particular resource then resource gets placed to nearest server of those users. ‘© Scaling Transparency : The main goal of this transparency is to permit the system to expand in scale without disturbing the operations and activities of existing users of distributed system. 1.4.4 Scalability If system adapt to increased service load then it is said to be a scalable system. There are three ways to measure the scalability of the system. i) (ii) Geographically scalable Scalable with respect to its size i) Administratively scalable Practically, scalable system leads to some loss of performance as the system scales up. Following are the problems related with scalability. Scalable with respect to its size ‘+ system easily adapts addition of more users and resources to the system. * In order to supports for more number of users and resources, it is necessary to deal with centralized services, data and algorithms. If centralized server is used to provide services to more number of users and applications then server will become bottleneck. © In spite of having more processing power, large storage capacity with centralized server, more number of will restrict further growth. requests will be coming to server and increased communi Like the centralized services, centralized data also is not good idea. Keeping a single database would certainly saturate all the incoming and outgoing communication lines. ‘© Inthe same way above, centralized algorithms also a not good idea. If centralized routing algorithm is used, it will collect the information about load on machines and communication lines. The same information algorithm processes to compute optimal routes and distribute to all machines. Collecting such information and sending processed information will also overload the part of network. Therefore use of such centralized algorithms must be avoided, Preference should be given to only decentralized algorithms. i) Geographically scalable ‘+ Although users and resources may lie far distance apart geographically, stil system allows the users to use resources and system. ‘¢ Insynchronous communication client blocks until reply comes from server. Distributed system designed for local area networks (LANs) are based on synchronous communication due to small distances between machines. «Therefore itis hard to scale such systems. A care should be taken while designing interactive applications using synchronous communication in wide area systems as machines are far apart and time required for communication is three orders magnitude slower with compare to LAN. ay latenttrodui Woistribute Computing 18 = Oa, (ii) Administratively Scalable Scaling Techniques Following are the three techniques for scaling : | 1. Hiding communication latencies * further problem that get in the way of geographical scalability is that communication in Wideares intrinsically unreliable, and virtually always point-to-point. On the contrary, local-area networks ben highly reliable communication facilities based on broadcasting, which ease development of the 4 systems, If system has several centralized components then geographical scalability will be restricte Performance and reliability problems resulting from wide-area communication. Use of centralized com, will lead to waste of network resources. Although system spans many independent administrative organizations, still its management is easy, In order to scale a distributed system across multiple, independent administrative domains, a key pe requires to be resolved is that of conflicting poli and security. 3s with respect to resource usage (and payment), m, Distributed system components residing in one domain can always be trusted by users that work ig Same domain. In this scenario, system administration may have tested and authorized applications, ang taken special measures to make sure that such components cannot be tampered with. Here, the users val system administrators. But, this trust does not cross domain boundaries naturally. Ifa distributed system crosses the domain boundaries, two forms of security measures require to be taken, is, the distributed system on its own must protect against m: ious attacks from the other new domain the other new domain on its own must protect against malicious attacks from the distributed system, Distribution Replication Geographical scalability can be achieved by hiding communication latencies. In this case, waiting by di! response from geographically remote server can be avoided by using asynchronous communicatitt’ implementation of requester's application. In asynchronous communication instead of blocking cient 2 other work until response is received. Batch-processing systems and parallel applications make use of asynchronous communication, in whid'l task is waiting for communication to finish, some independent tasks can be scheduled for execution. On the other hand, a new thread of control can be started to Carry out the request. Even though it blocks| for the reply, other threads in the process can carry on. In case of interactive applications, asynchronous communication cannot be used effectively. In this minimize the communication cost, server side computation of the request can be moved to the client ste side validation of form is the best example of this approach. Instead of carrying out validation at server better to shift it at client side.Woistributed Computing 19 Introduction to Distributed Systems 2. Distribution © Distribution is important scaling technique. In distribution component of the system divided into smaller parts, and then kept those parts across the system by spreading it. A good example of distribution is the Internet Domain Name System (DNS). © There is hierarchical organization of DNS name space into a tree of domains. These domains are divided into non- ‘overlapping zones. The names belonging to each zone are managed by a single name server. Replication «Although problems related to scalability degrade the performance, it is in general a good thought in fact to ity of the component, replicate components across a distributed system. Apart from increasing availa replication also balances the load between components which result in achieving the better performance. In WAN based system, placing a copy close to accessing location hides much of the communication latency problems described above. «Similar to replication, caching leads to make a copy of a resource in the near to the client accessing that resource. But, contrary to replication, caching decision is taken by the client of a resource instead of owner of a resource. «Caching is carried out on demand while replication is often planned in advance. The disadvantage of caching and replication that may have negative effect on scalability. Since multiple copies of a resource exist, making change in one copy makes that copy different from the others. As a result, caching and replication leads to consistency problems. 1.4.5 Openness Openness is the important goal of the distributed system. An open distributed system provides services as per standard rules thattell the syntax and semantics of those services. As, in computemetworks, standard rules state the message format, its contents and meaning of sent and received messages. All these rules are present in protocols. ‘Similar to above, in distributed systems, services are usually specified through interfaces, which are expressed in an Interface Definition Language (IDL). The definitions of the interfaces written in an IDL almost capture only the syntax of these services. They state exactly the names of the available functions together with parameters type; return values, exceptions likely to be raised etc. The semantics of interfaces means specification of what these interfaces can perform. Actually, these specifications are specified in an informal way through natural language. Processes make use of interfaces to communicate with each other. There can be different implementation of these interfaces leading to different distributed system that function in the same manner. Appropriate specifications are complete and neutral. Complete specifications specify the whole thing that is essential to make an implementation. But, many interface definitions does not obey completeness. So that itis required for a developer to put in implementation-specific details. If specifications do not impose what ‘an implementation should look like: they should be neutral. Completeness and neutrality are significant for interoperability and portability. An open distributed system should allow configuring the system out of different components from different developers. Also, it should be trouble-free to put in new components or replace existing ones without disturbing Ey tat awitWhistributed computing 2 aributed those components that stay in place. t means 2° = | systems interfaces are published. a te : | " im: Jet tor bug ag ul gould be able tO make a Sr set it dynamically , Monolithic approach should be 2¥0 ocuments PY PON Hieto mechanism. For example, apart from ston the d mr bea which documents are stored and fr POW much duration cn jagged into te DOE | ‘ompone’ ont © User should be able to implement his o“" policy 25 2 or ros recognize 5° that it can call Pree implemented component must ave an inertace tat © nce mechanism and it is also pased on published int, «Open distributed system provides uniform communication oot a ent es fy im order to access the common vesources. It iso consiaee software. 15 Types of Distributed Systems 5 Thereisacifferent distributed computing systems 1 istributed information Stems 2. Distributed Embedded Systems: i ji «The following discussion describes these systems. 15.1 Distributed Computing systems «sone dass of distributed system is intended for high-performance computing tasks. Cluster computing cor: the hardware that consists of 2 Set of similar workstations or PCS running ‘same operating systems and. eed local-area network. tems. Here adminite connected through a high sP' in case of grid computing, di domain of each system may be technology. 1.5.1(A) Cluster Computing Systems ¢ a group of computer sys! yuilt as feware, and deployed 1: tributed systems are bt ry dissimilar in hardware, So distinct, and may be ver se of reduced cost and improved performance of comput supercomputer using off. peed network ym is run in ‘Cluster computing systems were accepted becau: int of view, it became reliable to bul le computers in a high: workstations, From technical and cost p technology by simply connecting a set of comparatively simp! «In-almost al cass, luster computing is used for parallel programming in which @ single progra on several machines. iration of Linux-t zs n of Linux-based Beowulf clusters is shown in Fig. 1.5.1. Each cluster comprises? The common configut le master node. compute nodes. All these compute nodes are controlled and accessed through a si a sing The master node characteristicall ly manages the allocatic o resect submited ot, andes an interfer the in st to a specific parallel program, hots! rs of the system. «The master in fact fact runs the middleware required for the execution of p rograms and management of te” whereas the compute nodes requit quires only communication fais. iva standard operating system. Libraries offer advanced mess ww” SJWooistributed Computing Lit Introduction to Distributed Systems Masternode _ Compute node Compute node Parallel Application ‘Component Local OS access Network High speed Network Fig. 1.5.1: Cluster computing system 15.1(6) Grid Computing Systems In contrast to homogeneous environment of cluster computing systems, degree of heterogeneity. n this case hardware, operating systems, networks, administrative domains, security policies are different. grid computing systems includes a high «Ina grid computing system, resources from distinct associations are brought together to let the collaboration of a group of people or institutions. This collaboration leads to virtual organization. The people from same virtual organization are given access rights to the resources that are offered to that organization. © These resources comprise compute servers (together with supercomputers, probably implemented as cluster computers), storage facilities, and databases. Also, special networked devices like telescopes, sensors, etc, can be made available as well. A layered architecture for grid computing systems is shown in following Fig. 1.5.2. Fig. 1.5.2: A layered architecture for grid computing systems Fabric Layer : It is a lowest layer and offers interfaces to local resources at a specific site. These interfaces are customized to permit sharing of resources within a virtual organization. Connectivity layer : This layér contains communication protocols to offer support for grid transactions that span the usage of multiple resources. Protocols are required to send data among resources or to access a resource from a distant location. Also, this layer will have security protocols to authenticate users and resources. Instead of user, if users program is authenticated then the handover of rights from user to program is carried out by connectivity layer.Introduction to Dist buteg Resource layer: This layer manages a single resource It makes use of functions offered by the con and calls straight way the interfaces made available by the fabric layer. AS an example, this layer way functions for getting Configuration information on a particular resource or generally, to cany «Moy SPerations such as process creation or reading data, Hence this layer is responsible for access contr) an ‘willbe dependent on the authentication carried out as part of the connectivity layer. Collective Layer : It handles access to multiple resources and contains services for resource discovery, all and scheduling of tasks onto multiple resources, data replication, and so on. This layer contains many 0 Protocols for verity of functions, reflecting the broad range of services it may provide to a virtual organiza, Application Layer : This layer contains applications that functions within a virtual organization ang Which the grid computing environment. 1.5.2 Distributed Information Systems Many organizations deal with networked applications facing the problems in feroperabilty. Many 9, middleware solutions provide easy way to integrate applications into an enterprise-wide information system, In most of the cases networked application is a client server application in which server run the hea, (database) and clients sends request to it. After processing request server sends reply to client. If integration is done at lowest level, it would permit clients to enclose a many requests, perhaps for Ci Servers, into a single larger request and let it be executed as a distributed transaction. The basic scheme was, either all or none of the requests would be executed. Such integration should also happen by allowing applications to communicate straight way with each other has shown the way to enterprise application integration (EAl) Above two forms of distributed systems is en below. 1.5.2(A) Transaction Processing Systems Programming using transactions involves primitives that are either provided by underlying distributed systema the language runtime system. Following are the examples of primitives for transactions. BEGIN_TRANSACTION : For marking the start of transaction. END_ TRANSACTION : For terminating the transaction and try to commit. ABORT_TRANSACTION : For killing the transaction and restore the previous state. READ : To read the data from table or file. WRITE : To write the data to table or file. The main property of a transaction is either all of its operations are executed or none are executed, The that are present in the body of transaction can be system calls, library procedures, or programming lst statements. Following are the ACID properties of transaction. individual. Atomic : Execution of transaction i Consistent : There is no violation of system invariants by transaction. Isolated : Concurrent transactions do not interfere with each other. Durable : After commit is done by transaction, the changes are permanent. wmIntroduction to Distributed Systems Distributed Computing 1 Nested Transaction + In nested transactions, top level transaction fork off children, which run in parallel to one another on different computers for improving the performance. Every forked child may also execute one or more subtransa fork off its own children, Fig. 1.5.3 shows nested transaction. |-_— Nested Transaction +4 ‘Sub transaction -—-‘Subtransaction ‘Sub transaction -—4 el ——" Database 1 Database 2 Database 3 Three independent DBs Fig. 1.5.3 : A nested Transaction Consider that, out of several subtransactions running in parallel one of the commits and:submit the result to the parent transaction. If parent aborts ater further computation and restores entire system to the previous state it had before the top-level transaction began. In this case the committed result of subtransaction must nevertheless be undone. Therefore the permanence referred to above applies only to top-level transactions Any transaction or subtransaction basically works on a private copy of all data in the entire system. , They manipulate the private copy only. If transaction or subtransaction aborts then private copy disappears. fi commits, its private copy replaces the parent's copy. Hence, if after commit of subtransaction a new subtransaction is started, then new one notice results created by the first one. Similarly, if higher-level transaction aborts then all its underlying subtransactions have to be aborted as,well. Nested transactions present a natural means of distributing a transaction across multiple machines in distributed system. They exhibit logical splitting up of the work of the original transaction. 5.3. Enterprise Application Integration ies to integrate applications independent from their databases. The reason It became obvious to have some facil behind this was the decoupling of applications from databases. There is requirement of straightway communication among application components instead of using the request/reply pattern that was supported by transaction processing systems.4 Introdueti Wistibitea Computing Lit SON Distr There are many examples of communication middleware. Using Remote procedure calls (Rpc), ana SomPonent at client side can efficiently send a request to another application component at server sig, 8 local procedure call, This request at client side is packed as a message and sent to the called applica, SSM way, the result will be packed as message and sent back to the calling application as the Procedure call, Like RPG, itis also possible to call the remote objects using remote method invocations (RMI. An RMLig is similar to RPC, except that it operates on objects rather than applications. While communicating Using RMI both caller and calle have to be up and running, This is the drawback of it oo) 4 Im case of message-oriented middleware, applications just send messages to logical contact points, 4 means of a subject. Similarly, applications can demand for a specific type of message and come middleware ensure that those messages are delivered to those applications 1.5.4 Distributed Pervasive Systems ‘The distributed system discussed above is stable and nodes are fixed and permanent in it. The distribute in which mobile and embedded computing devices are present, instability is default behavior. These devices, system called as distributedpervasive systems are small in size with battery-powered, mobile, and through wireless connection. An important characteristic of this system is absence of human administrative control. One po: ‘overing their environment automatically. le best soa owner configures their devices. These devices require In pervasive systems devices usually connect to the system with the intention of accessing and proba Providing the information. This calls for means to without difficulty read, store, manage, and share i Considering irregular and altering connectivity of devices, the memory space where accessible information will most likely alter continually. Hardware Concepts Hardware concepts illustrate the organization of hardware, their interconnection and the manner in vit communicates with each other. Multiple CPUs exist in distributed system. The machines are basically divided in two groups Multiprocessors : Processors share the memory. Multicomputers : Each processor has its own private memory. Both multiprocessors and multicomputers further divided in two categories on the basis of architedit interconnection network. The basic organization is shown in Figs. 1.6.1 and 1.6.2. Bus-based : Machines are connected by single cable or processors are connected by bus and share the me communicating over the bus. | Switch-based : Machines are connected with different wiring patterns and messages are routed along oi” line by switching the switch. Multicomputers can be homogeneous or heterogeneous. Homogeneous multicomputers use same tecino! interconnection network and all processors are similar, accessing the same amount of private memory: : om JWhistributed computing 1-15 Introduction to Distributed Systems (e GIG) Gl Gl [ CL Pl fe T P P| [rl Lr ; Bus-based shared memory multiprocessor _Bus-based multicomputer. Each Processors share the memory processor has its private memory Fig. 1.6.1 Heterogeneous multicomputers have different architecture for different machines. Machines are connected by different types of networks using different technology. Processors share the memory and Processors have private memory interconnected through switch and interconnected through switch Fig. 1.6.2 6.1 Multiprocessors Multiple CPUs and memory modules are connected through bus. Single memory is available. CPU1 writes memory ‘and CPU2 reads written value, CPU2 gets the same value which was written by CPU1. Memory having such property is said to be coherent. ‘The disadvantage of the scheme is that if few numbers of processors are connected then bus becomes overloaded and performance degrades. To overcome the problem, a high cache memory is placed between CPU and bus. If referenced word is in cache then it is accessed by CPU and bus is avoided. Typical size of cache is 512 KB to 1 MB. ‘Again memory can be incoherent if updated word in one cache is not propagated to other copies of the word present in different cache memory: otherwise other copies will have old values. A bus-based multiprocessor provides less scalability. Bus Fig. 1.6.3 :A bus-based multiprocessor To allow for more number of processors, processors and memory modules are connected by crossbar-switch. ‘When CPU wants to access particular memory, a crosspoint switch gets closed. Several CPU can access different memory simultaneously but for two CPUs to access same memory at ‘the same time, one has to wait. It is shown in Fig. 1.6.4. Here for n CPUs and n memories, n2 crosspoint switches are required, ¥> Wistrbutea Computing Introduction Dita, Cross point switch 2x2switch Fig. 1.6.4 : A crossbar switch Fig. 1.6.5 : An omega switching network * Omega network contains 2 X 2 switches, each switch having 2 inputs and 2 outputs. For any input any ote ‘wo output line can be selected. Any memory can be accessed by any switch. To reduce latency between, ou, memory, fast switching is needed and it is costly. 1 * — Non-uniform memory access architecture allows the CPU to access its local memory fast and other cpu's ena is slowly accessed, 1.6.2. Homogeneous Multicomputer Systems * Nodes are connected through high speed interconnection network. Processors communicate thro interconnection network; therefore traffic is low with compare to traffic between processor and memory, * If nodes are connected through interconnection networks like fast Ethernet then it is bus-based multicompity has limited scalability and performance is low if few number of processors (25-100 nodes) added. * Instead of broadcasting like in bus based multicomputers, routing of messages can be done thax interconnection network. A grid is shown in Fig. 1.66 (a) and suitable for graph theory related probie: A 4-dimentional hypercube is shown in Fig. 1.6.6 (b). Vertices represent CPU and edges represent connec: between CPUs. oy Ch (@) Grid * Massively parallel processors (MPPs) and Cluster of workstations are the examples of the switched multicom 1.6.3 Heterogeneous Multicomputer Systems Today most of the distributed systems are built on the top of multicomputers having different processors size etc. Interconnection network also have a different technology. These are called as hetet multicomputers. In large scale heterogeneous multicomputer environment, services to application a performance varies at different locationsDi smpul Whistributed Computing 1-17 Introduction to Distributed Systems trinsic heterogeneity, scaling are the factors due to which there is a requirement ‘© Absence of global system view, of sophisticated software to built the distributed applications for heterogeneous multicomputers. 1.7 _ Software Concepts Distributed systems and traditional operating systems provides the similar services such as: Both play the role of resource managers for the underlying hardware. Both permit the sharing of resources like CPUs, memories, peripheral devices, the network, and data of all kinds among multiple users and applications. ‘+ Distributed systems try to hide the details and heterogeneous nat Virtual machine on which applications can be executed without trouble. fe different operating system installed on it. Operating systems for ure of the underlying hardware by offering @ © In a network multiple machines may hav distributed computers are categorized as: «Tightly coupled systems : It keeps a single, global view of the resources it manages. Such tightly coupled operating system is called as distributed operating system (DOS). It is useful for the management of multiprocessors and homogeneous multicomputer. DOS hides details of underlying hardware, This hardware can be shared by many processes and details remains hidden. = Loosely-coupled systems : In a set of computers, each has its own OS and there is coordination between operating systems to make their own services and resources available to the others. This loosely coupled OS is called as network operating system (NOS) and is used for heterogeneous multicomputer systems. . Apart from above operating systems middleware is used to provide general purpose Services and itis installed on the top of NOS. It offers distribution transparency. 1.7.1 Distributed Operating Systems There are two types of distributed operating systems. , Multiprocessor Operating System : Itmanages resources of multiprocessor. , Multicomputer operating system : It is d Distributed operating system is similar in functions the multiple processors. Jniprocessor Operating Systems ‘These are traditional operating systems and dev the different resources available in system. It allows the di taneously several applications executing on the same machine 9 data of one application from the other application if both are si s provided by OS. To send the messages, applications should use fesigned for homogeneous multicomputer. to the traditional uniprocessor operating system. DOS handles eloped for single CPU. It permits the user and applications to share ifferent applications to use same hardware in isolated ets their required resources. manner. Simul Operating system protects ‘Applications should use only facil communication primitives offered by OS. imultaneously executing in which hardware resources are used and shared. For this purpose CPU Operating system takes care of the way i el mode and user mode. supports for two modes of operation, kern v¥ Distributed Com, a mode, execution of all instructions is allowed to be carried out, and the entre memory ang i -_ STS is accessible throughout execution. On the contrary, in user mode, there is a rest riction on a Tegister access When CPU executes operating system code, it switches to kernel mode. This switching toa Mode to kemel mode ‘occurs through system calls that are implemented by the operating system, Puting ¥f virtually all o, architecture ay Perating system code is executes in kernel mode then operating system is said to have mo, flexibility. tn th nd it runs in single address space. The disadvantage of monolithic design PProach ig i is design, itis difficult to replace the components. nolithic ©Perating systems are not a good scheme from point of view of openness, software engi, SF maintainability. If the operating system is organized into two parts, it can pro Mor reliability, ert set of modules for managing the hardware is kept which can uniformly w the first p. mode, wide more fle ell be executed , For example, memory mana: 'gement module keeps track allocated and free space tothe processes. It ig execute in kernel mode at t he time when registers of the Memory Management Unit (MMU) are set 'No direct data exchange between modules "hig OS intertace " ea User mode kemel mode System call Microkemel Hardware Fig..7.1: cute in kernel mode. It is the second part of the open! the code for, context switching, ipts. system. Actually, @ microkernel require only cont setting device regi manipulating the MMU, and capturing hardware interru; Multiprocessor Operating Systems * Unlike the uniprocessor operating systems, multi Processors having access to a shared memory. In this deal with the hardware, processor operating systems offers support for case, all data structures required by the operating syste’ together with the multiple CPUs, are placed into shared Memory. Multiple process0s' access these data. Hence protection against simultaneous * Such transparency can be attained and is relatively straightforward as different parts of applications commu by using same primitives as those in mu erating systems. All the communication 6 red protect that data against concurrent maphores and monitors. Ce isking uniprocessor ope by manipulating data at shared memory locations, and it is requir This protection is achieved through synchronization primitives: ce1419 Introduction to Distributed Systems Distributed Computing Lee Semaphores ‘A semaphore S is an integer variable that, apart from initialization, is accessed only through two standard atomic and signal. These operations were firstly termed P (for wait) and V (for signal) ‘A semaphore S is integer variable whose value can be accessed and changed only By two operation: and signal (V or wakeup or up). Wait an signal are atomic operations. operations: wait 1s wait (P or sleep or down) Binary semaphores do not assume all the integer values. It assumes only two values 0 and 1. On the contrary, counting semaphores (general semaphores) can assume only non-negative values. The wait operation on semaphores S, written as wait(S) or P(S), operates as follows : it(S): IF S>0 THEN S: ELSE (wait onS) ‘The signal operation on semaphore S, written as signal(s) or VS), operates 2£ follows : al(S): IF (one or more process are waiting on S) ‘THEN (let one of these processes proceed) ELSE S:=S+1 : The two operations wait and signal are don« operation has initiated, no other process can access t -ed within wait(S) and signal(S). only one process will be permitted to proceed. The other Jes that processes will not means, once a semaphore .e as single indivisible atomic operation. It inished. Mutual exclusion he semaphore until operation has fir ‘on the semaphore S is enforc If many processes attempt a wait(S) at the same time, processes will be kept waiting in queue. The implementation of wait and signal promis undergo indefinite delay. Semaphores solve the lost-wakeup problem. jonitors used incorrectly, it can produce timing errors that are hard to detect These errors occur only if do not always occur. constructs called as monitor. If semaphores are lar execution sequences results and these sequences researchers have developed high-level language ¢ uctures that are all grouped together in a particular type of cess to the monitor's some particul In order to handle such errors, variables, and data str lures in a monitor if required, but direct ac processes. ‘A monitor is a set of procedures, module or package. Processes may call the proced internal data structures from procedures declared outside the monitor s restricted to the Following is the example of the monitor. onitor example-_ Woistriburea Computing 1-20 Inrroduction to Distribie, 4 s in, Monitors can achieve the mutual exclusion: only one process can be active in a monitor ata time, AS monitors are a programming language construct, the compiler manages the calls to monito, Prog differently from other procedure calls * Normally, when a process calls a monitor procedure, if any other process is currently executing within the it gets checked, * * Tso, the caling process wil be blocked until the other process has left the monitor. Ifno other process iy: Monitor, the calling process may enter. " * The characteristics of a monitor are the following © _ Only the monitor’s procedures can access the local data variables. External procedures cannot access © A process enters the monitor by calling one of its procedures. © Only one process may be running in the monitor at a time; any other process that has called the mp, blocked, waiting for the monitor to become available. Synchronization is supported by monitor with the use of condition variables that are contained vith, Monitor and accessible only within the monitor. Condition variables are a special data type in monitors, wi operated on by two functions: wait (c): the calling process's execution gets suspended on condition c. The monitor is now accessible fous. another process. signal (¢): blocked process after a cwait (on the same condition) resumes its execution. If there are man: Processes, choose one of them; if there is no such process, do nothing. issimilar from those for the semaphore. If a process in a monitors. * Monitor wait and signal operations are and no task is waiting on the condition variable, the signal is lost. When one process is executing in monitor, processes that trying to enter the monitor join a queue of poz blocked waiting for monitor availability. Once a process is in the monitor, it may temporarily block itself on condition x by issuing cwait (x); itis thens= in a queue of processes waiting to reenter the monitor when the condition changes, and resume execution point in its program following the cwait (x) call. t }f a process that is executing in the monitor detects a change in condition variable x, it issues csignl alerts the corresponding condition queue that the condition has changed. A producer can add characters to the buffer only by means of the procedure append inside the moni producer does not have direct access to buffer. The procedure first-checks the condition not full to determine if there is space available in the buffer. If process executing the monitor is blocked on that condition, Multicomputer Operating Systems In multicomputer operating systems data structures for systemwide resource management cannot simp! ® by keeping them in physically shared memory. In its place, the only way of communication is through passing. Following is the organization of multicomputer operating systems shown in Fig. 1.7.2.Introduction to Distributed Systems $F Distributed Computing Machine A Machine C Distibuted Applications =— Distributed Operating System Sorvices Kernel | | TI Kemel Kernel [Tf Network General structure of a multicomputer operating system | CPU, a local disk and others. Each Fig. 1. Kemel on each machine manages local resources, for example memory, the local machine contains separate module for sending and receiving messages to and from other machines. On the top of each local kernel there is a common software layer that implements the operating system as a virtual machine supporting parallel and concurrent execution of various tasks. This software layer offers a complete software implementation of shared memory. Further facilities usually implemented in this layer are, such as, assignment of task to processor, masking hardware failures, providing transparent storage, and general interprocess communication. Some multicomputer operating systems offers only message-passing facilites to applications and do not offer shared memory implementation. But different system can have different semantics of message-passing primitives. Their dissimilarities can be explained by taking into consideration whether or not messages are buffered, When should be blocking of sending or receiving proces: also need to be considered as well. Buffering of the messages can be done at the sender's side or at the receiver's side. There are four synchronization points at which a sender or receiver can possibly block At the senders side, sender is blocked if buffer is ful. sender buffer is not present then three other points to block the sender are © The message has been sent by sender. © The message has arrived at the receiver side. ©The message has been delivered to the receiver application. ‘Another issue that is significant to know message-passing semantics is whether or not communication is reliable. tion, a assurance of receiving the message by receiver is given to the sender. In reliable commu stributed Shared Memory Systems (DSMs) Programming for multicomputers is complex with compare to multiprocessors. AS only message passing iS available with multicomputers, programming becomes difficult with multicomputers. On the other hand, multiprocessor uses semaphores and monitors to access the shared data, So programming with multiprocessors 's simple. In multicomputer case buffering, blocking, and reliable communication needs to be consider as well which leads to complex task of programming. Implementing the shared memory on multicomputers offers a virtual shared memory machine, running on a inulticomputer, This shared memory model can be used to write the applications on multicomputers. The role of multicomputer operating system is important in this case.Introduction to Distr isribey 322 each individual node, With tis .d. In DSM system the address space is broken, i . processor reference fails to an ada. having th is ring system fetches the page Teving We ‘oferencd a tes successfull " pages and four proc ys the backing store inst Wistributea computing memory of irtual m' * Allarge virtual address space can be created by using V realize page based distributed shared memory (DSM) is mm. fa of size 4 KB or 8 KB and kept overall the nodes inthe S72 locally unavailable, a trap takes place, and the opera and i , which now compl starts again the faulting instruction, essors are avaiable, * Following Fig.2.7.3 shows an address space divided 19 16 tead of the focal dis normal paging. Here RAM of other machine is being used as ‘Shared global address SPACE 49] 12]13]14] 15} 7] 819119 0] [2] 914] 51 [ysite} |e [ells [ral4) Memory cPut cpu2 cpus cpu Fig. 1.7.3 : Pages are spread over 4 machines «As shown in Fig. 1.73, if processor 4 references the instruction or data belonging to the pages 13 and 15 they, hich are in the pages placed on other machines then. done locally. If references to instructions and data are w! to the operating system will occur. that references will be done locally and performance can be impo : ified other copies should also reflect thes jing write other copies Allread only pages can be replicated so read-write pages are replicated then if one of the copies gets mo changes. Write invalidate can be used to perform write.on the page. Before perform invalidated. «If size of the pages kept large then it can reduce the total number of transfers when large section of conan data needs to be accessed. Conversely, if @ page comprises data needed by two independent process: different processors, the operating system may need to repetitively transfer the page between those: processors. This is called as false sharing. 1.7.2 Network Operating Systems Network operating systems assumes underlying hardware as heterogeneous. Whereas DOS assumes uundet? alled on * hardware as homogeneous. In heterogeneous environment, machines and operating systems inst may be different. All these machines are connected to each other in computer network. ‘© NOS permit users to use services available on a particular machine in the network. Remote login service pon by NOS allows the user to log in remote machine from his/her terminal. Using command for remote copy copy the file from one machine to other. Information sharing can be achieved by providing a shared, global file system accessible from all the Wo The file system is implemented by file servers, The file servers accept requests to read and write files 0” programs running on ¢lient machines. Each request of client request is executed by file server, and the sent back to client. eA f |&F Distributed Computing 1-23 Introduction to Distributed Systems Machine A Machine B Machine C Distributed Applications Network OS Network OS Services Services Kernel] Kernel | _[ Network Fig. 1.7.4 :General structure of a network operating system File servers usually supports hierarchical file systems, each with @ root directory including subdirectories and files. Workstations can import or mount these file systems by augmenting their local file systems with those located on the servers. Distributed operating system attempts to achieve complete transparency in order to offer a single system view to the user. Whereas achieving full transparency with network operating system is not possible. As we have seen for remote login, user has to explicitly log into remote machine. In remote copy user knows the machine to which he/she is copying the files. The main advantage of network operating system is that it provides scalability .8 Middleware Both DOS and NOS do not full the criteria required for distributed system. A distributed operating system cannot manage a set of independent computers, while a network operating system does not provide transparency. A distributed system consisting of advantages of both DOS and NOS: the scalability and openness of network operating systems (NOS) and the transparency and related ease of use of distributed operating systems (009) is possible to realize by using middleware ‘A middleware layer can be added on the top of network operating systems which hide the heterogeneity of the collecion of underlying platforms but as well get the better distribution transparency. The most of the modem distributed systems are build by means of such an additional layer of what is called middleware. 8.1 Positioning Middleware cy as many distributed applications make direct use of the It is not possible to achieve distribution transparen the programming interface provided by network operating systems. Applications always make use of interfaces to local file system as well If additional layer of software is placed betw transparency can be achieved and higher level of abstraction is provi in Fig. 18.1. jeen applications and the network operating system then distribution ided. This layer is called middleware as shown ment is handled by NOS. It also provides simple communication means is to hide heterogeneity of the underlying platforms of services. In this organization local resource manage! to connect to other computers in the network, A major goal from applications. As a result, many middleware systems offer an essentially complete setstoked Comping Distributed Applications Middleware Services = Network OS. Network OS Network OS Services Services. Savin’, Kernel Ker [_emet_] Fig. 1.8.1 : Organization of distributed system as 1.9 Models of Middleware In order to ease the development and integration of distributed applications most middleware is uses some to express distribution and communication. A relatively simple model is that of treating everything as a fie * The approach of treating everything as a file is introduced in UNIX and also followed in plan 9. Here, aj 4 such as keyboard, mouse, disk, network interface, etc, are treated as files. In essence, whether a file isn, remote makes no difference, For reading or writing bytes in file, an apy ion first opens the file and then ce: read or write operation. Once the operation is done it closes file again. As files can be shared by many pro. communication reduces to just accessing the same file. * Another model of middleware is based on distributed file systems, This model supports distribution transpas only for files that only stores data. This model became popular as it is reasonably scalable. * In Remote Procedure Calls (RPCs) based middleware model, a client side process calls a procedure implens on a remote machine. In this call, parameters are transparentlysent to the remote machine (servet) wher procedure actually executed. The result of execution then server sent back to the caller. Although called prec is executed on remotely, it appears as call was executed locally. In this case the communication with process remains hidden from calling process. Similar to calling the remote procedure in RPC, it is also possible to invoke objects residing on remote compe in a transparent manner. Many middleware systems offer a concept of distributed objects. The main idea distributed objects is that each object implements an interface that hides all the internal details of the objet! its users. An interface contains the methods that the object implements. The process notices of an objec interface. In the implementation of distributed objects, object resides on single machine and its interface is kept 0" ‘other machines. The available interface of the object on invoking process's machine converts its method inv into a message that is sent to the object. After receiving method invocation message of process, objet & the invoked method and sends back the result. The interface implementation then converts the reply mes" a return value, and submits to the invoking process. Similar to RPC, the invoking process remains totally “ of the network communication. |87 Distributed Computing 1-25 Introduction to Distributed Systems The World Wide Web became successful due to the very simple but very much effective model of distributed documents. In web model, information is organized in the form of documents. Each of the document is kept on a machine transparently sited anywhere in the wide area network. Links in the documents refer to other documents. By using link referring to particular document, that document is obtained {rom its location and gets displayed on the user's machine. Apart from textual documents, web also supports for audio, video and interactive graphic-based documents. 1.10 Services Offered by Middleware {All middleware implements access transparency. For this, they provide high-level communication facilities to hide the low-level message transmitting through computer networks. How communication is supported depends very much on the model of distribution the middleware offers to users and applications. Naming service is offered by almost al middleware. Due to name services offered by middleware itis possible to share and search for the entities. Naming service becomes complex to deal with if scalability is considered. For efficient searching of a name in a large-scale system, the place ofthe entity that is named must be assumed to be fixed. This main difficulty which is needed to be handled. In World Wide Web (WWW), URL is used to refer to the document. Server on which this document is stored, its name is present in URL, Therefore, if the document is migrated to another server, its URL fails to search the document. Persistence service is offered for storage purpose. Persistence service is provided through a distributed filesystem in simple way, but many advanced middleware have integrated databases into their systems If not it provides facilities for applications to connect to databases. Many middleware offers facility for distributed transactions if data storage is important Transactions permit multiple read and write operations to take place atomically. Atomicity is the property where either transaction commits so all its write operations are actually performed, or it fails, leaving all referenced data unchanged. Distributed transactions operate on data which is distributes across multiple machines. ‘The important service provided by middleware is security. Instead of depending on the underlying local operating «ystems to sufficiently support security for the entire network, security has to be partly implemented additionally in the middleware layer itself. jiddleware and Openness Modern distributed systems are built as middleware for different operating systems. Due to this. applications developed for a specific distributed system become operating system independent and more dependent on specific middleware. The difficulty arises due to less openness of middleware. Actual open distibuted system is specified through interfaces that are complete. Completeness states that the details required for implementing the system, has surely been specified, If interfaces are not complete then system developers must add their own interfaces. As a result, situation arses in which two middleware systems developed by different teams follow the same standard, but applications developed for one system cannot ported to the other without trouble. Due to incompleteness although two different implementations implement precisely the same set of interfaces but different underlying protocols, they cannot interoperate. ttnCommunication | sybus| —_ _ _ —— — Interprocess communication (IPC) : Remote Procedure Call (RPC), Remote Object Invocation, Remote i | _Invocation (RMD, Message Oriented Communication, Seam Oriented Communication, Group Communication, 2.1 _ Interprocess Communication (IPC) 2.1.1 Types of Communication * Synchronous Communication : In this type of communication, client application waits after sending requ reply sent request comes from server application. Example is Remote Procedure Calls (RPC), Remote, Invocation (RMD, * Asynchronous Communication : In this type of communication, client application continues other, sending request until reply of sent request comes from server application. RPC can be implemented jis. communication type. Other examples can be transferring amount from one account to other, updating =. entries and so on. * Transient Communication : In this type of communication, sender application and receiver applcati should be running to deliver the messages sent between them. Example is Remote Procedure Calls RPC) = Method Invocation (RM). + PersistentCommunication : In this type of communication, either sender application or receiver appli need not be running to deliver the messages sent between them. Example is email 2.2 Remote Procedure Call (RPC) | |Q. Define remote procedure call (RPC)? Describe the working of RPC indetail Ces Program executing on machine A calls procedure or function that is located at machine B is called 8 Procedure Call (RPC). Although this definition semps to be simple but involves some technical issues. he (send and receive) used in sending and receiving the messages do not hide communication, In RPC, cling calls remote procedure by sending parameters in call and callee returns the result of procedure. 2.2.1 RPC Operation + In Remote Procedure Calls (RPCS) model, a cient side process calls a procedure implemented 0”? machine. In this call, parameters are transparentiysent to the remote machine (server) where the pro” ~ we J22 Communication Distributed Computing executed. The result of execution then server sent back to the caller, Although called procedure is executed on remotely, it appears as call was executed locally, In this case the communication with remote process remains hidden from calling process. While calling a remote procedure, the client program binds with a small library procedure called the client stub Client stub stands for the server procedure in the client's address space. In the same way, the server program binds with a procedure called the server stub. Fig. 2.2. 1 shows the steps in making an RPC. Step 1: Client calls the client stub. As client stub is on client machine, this call isa local procedure call (LPC), and the parameters pushed onto the stack in the normal manner. Step 2: Client stub packs the parameters into a message and issue a system call to send the message. This process is called marshalling. Step 3: Kernel sends the message from the client machine to the server machine. Step 4: The kernel on server machine, send the incoming packet to the server stub. Step 5: Server stub calls the server procedure. Client CPU Server CPU Fig. 2.2.1 : Steps in RPC The server then handover the result to server stub which packs it into message. Kernel then send the message to client where kernel at client handover it to client stub, Client stub unpack the message and handover result to client. 2.2 Implementation Issues Machines in large distributed system are not of same architecture and hence data representation of these machines is different. For example, IBM mainframe uses EBCDIC character code representation, Whereas IBM PC use ASCII code. Hence, passing character code between these pair of machines will not be possible. In the same wway, Intel Pentium machines numbers their bytes from MSB to LSB (litte endian). SPARK machine stores bytes from LSB to MSB (big endian). ‘As client and server applications are in different address space in client and server machine, passing pointer as parameter is not possible. Instead of pointer to data itis possible to send data as parameter. In C language, array is passed to the function as reference parameter. Hence, itis necessary to send complete array as a parameter to server as array address will be different at server machine. ¥2.2.3. Asynchronous RPC 2.2.4 DCERPC 0 Security Service © Distributed Time Servic! 23 Lor, this data (passed array from client side) in ap ms hich in turn sends to cli b whi client Stub ij Ser soon Stub at server machine then creates poi tu rer applicati : Thies vPlcation. Server then sends modified data back to sent st Wie ale, ie i S Works for simple data type not for complex data structure like 9} Se qUeney ~Lat by reference is replaced by copy-restore. - Im weakly typed languages like C, it is entirely legal to write a procedure that crap ie Poti arrays without specifying how large either on Each could be terminated by a specs value known ony, calling and called procedures. In this case, it is basically impracticable for the client stub to marsha, Parameters as it has no way to know how large they are. even from a formal specification or the Sometimes it is difficult to infer the types of the parameters, takes any number of parameters ang. Calling printf remotely in C language is practically impossible as it types. If called procedure shifted to remote machine then calling and called procedure cannot share Variables and hence code will fail. By considering all above limitations and taking care of above things, sity used widely Sometimes it is not necessary for client application to block when there is no reply to return from application. For example, transferring amount from one account to other, updating database entries. in 4, client can continue to carry out its useful work after sending request to server without waiting for reply, Asynchronous RPC allows client to continue its work after calling procedure at server. Here, client im, continue to perform its other useful work after sending RPC request. Server immediately sends acknowled to client the moment request is received. Server then immediately calls the requested procedure. After acknowledgement, client continue its work without further blocking. Here client waits till acknowed ofreceipt of request from server arrives. In one-way RPC, client immediately continues its work without waiting for acknowledgement from sere: receipt of sent request. Distributed Computing Environment RPC is one of the examples of RPC system developed by Open Foundation (OSF). Its specifications have been adopted in Microsoft base system for distributed computing true middleware system initially designed for UNIX. Now, it has been ported to all major operating systems. DCE uses client server model as programming model where user Processes are clients to access services: from server processes at server machine. Some services are in built in DCE and other are implement application programmers. Client and server communication takes place through RPC. Services provided by DCE are: © Distributed File Service : It offers transparent way to access any file in the system in same manne. © Directory service : It keeps track on all resources distributed worldwide including machines, printe®' files, servers and many more. It offers access to the resources to only authorised persons. t To synchronize the clocks of different machines.Distributed Computing 24 Is and Working of DCE RPC Communication RPC system allows client to call local procedure in order to access remote service from server. RPC system can automatically locate the server and establishes connection between client and server application (binding). It can fragment and reassemble the messages, handle transport in both directions and converts data types between client and servers if machine on which they running have different architecture and hence, different data representation. Clients and servers can be independent of one another. Implementation of client and servers in different languages is supported. OS and hardware platform can be different for client and server applications. RPC system hides all these dissimilarities. DCE RPC system contains several components such as libraries, languages, daemons, utility programs etc. Interface definitions are specified in interface definition language (IDL). IDL files contains type definitions, constant declarations, function prototypes, and information to pack parameter and unpack the result. Interface definitions contains syntax of call not its semantics Each IDL file contains globally unique identifier for specified interface. This identifier client sends to server in first RPC message. Server then checks its correctness for binding purpose otherwise it detects error. ps in Writing a Client Server Application in DCE RPC First, call uuidgen program to generate prototype IDL file which contains unique interface identifier not generated anywhere by this program. This unique interface identifier is 128 bit binary number represented in ASCII string in hexadecimal, It encodes location and time of creation to guarantee the uniqueness. Next step is to edit this IDL file, Write the remote procedure names and parameters in file. This IDL file then is compiled by using IDL compiler. After compilation, three files are generated: header file, Client stub and server stub. Header file contains type definitions, constant declarations, function prototypes and unique identifier. This file is included (#include) in client and server code. The client stub holds procedures. which client will call from server. These procedure collects and marshals parameters and convert it outgoing message. It then calls runtime system to send this message. Client stub also is responsible for unmarshaling the reply from server and delivering it to client application. The server stub at server machines contains procedures which are called by runtime system there when message from client side arrives. This again calls actual server procedure. Write server and client code. Client code and client stub both are compiled to convert it in object files which are linked with runtime library to produce executable binary for client. Similarly at server machine, server code and server stub both are compiled to convert it in object files which are linked with runtime library to produce executable binary for server. jing Client to Server in DCE RPC Client should be able to call to server and server should accept the clients call. For this purpose, registration of server is necessary. Client locates first server machine and then server process on that machine. Port numbers are used by OS on server machine to differentiate incoming messages for different processes. DCE daemon maintains table of server-part number pairs. Server first asks the OS about port number and registers this ith DCE daemon. Server also registers with directory service and provide it network address of server end point wi machine and name of server. Binding a client to server is carried out as shown in Fig. 22.2.Wo) SHbuted Computing 25 Lor, Directory machine directory 2, Server registers service with Dirwctory ‘Sov Server machine | 3. Look up server / 1. Register the. | acct ort number in tal Client machine DCE 4. Ask for port number to DCE daemon Fig. 2.2.2 Glen Passes name of server to directory server which returns network address of server. Client IRE ng Seemon to get port number of server running on server machine. Once client knows both Network adds, Port number, RPC takes place. 2.3 Remote Object Invocation Objects hides its internal details from external world by means of well-defined interface. CORBA and Dcoy, i Sxamples of object based distributed systems. 2.3.1 Distributed Objects (RMI: Remote Method Invocation) . * — Objects encapsulates data, called the state and operations on those data, called as methods. Methods aren, through interface. Process can access or manipulate state only through object's interface. Sin implements several interfaces. Similarly, for it le objen impleme> for given interface definition, several objects may provide Client invokes method Same interface as object Skeleton invokes same ‘method at object Marshalled invocation is passed ‘Across the network.istributed Computing 2-6 Communication invocation in message and unmarshal reply messages which contains result of Proxy marshals clients method it skeleton is method invocation by client, This result, proxy then returns to client, Similar to server stub in RPC, present on server machine Skeleton unmarshals incoming method invocation requests to proper method invocations at the object's interface at the server application, It also marshals reply messages and forward them to client side proxy. Objects remains con single machine and their interfaces only made available on different machines. This is also called as remote object. pile-time Versus Runtime objects Language-level objects called as compile-time objects. These objects are supported by object oriented languages uch as Java, C++ and other object oriented languages. Object is an instance of class. Compile time objects makes it easy to build the distributed applications in distributed system. In Java, objects are defined by means of class and interfaces that class implements. After compiling interfaces, we at server stub and client stub. The generated code after compiling the class definition permits to instantiate the java objects, Hence, Java objects can be invoked from remote machine. The disadvantage of the compile- timeobjects is its dependency on particular programming language. programming language and explicitly constructed during run time. Many Runtime objects are independent of cistributed object-based system uses this approach and allows construction of applications from objects written in multiple languages. Implementation of runtime objects basically is left open. per around implementation so that it appears to be object and its methods can be Here, objects aré defined in terms of interfaces they implements. This 1 interface for remote Object adapter is used as wrapy invoked from the remote machine. implementation of interface then registered with object adapter which makes available th invocation istent and Transient Objects persistent object continue to exist although server exits. Server at present managing persistent object stores object sate on secondary storage before it ext. f newly started address needs this object then it reads object state from secondary storage. In contrast to persistent object, transient object exist till server manages that object exists. Once server exit the transient object also exit. ject References Client invokes the method of remote object. The client binds with an object using object reference which must contain sufficient information to permit this binding, Object reference includes network address of machine on which object is placed, plus port number (endpoint) of server assigned by its local operating system ‘he limitation of above approach is that, when server crashes, it will be assigned different port number by OS after recovery. In this case, all the object references become invalid. The solution to this problem to have local daemon process on machine which listens to a well-known port number and records server-to-port number assignment in endpoint table. In this case, server ID is encoded in object reference is used a index into endpoint table. While binding client to object, daemon process is asked for server's current port number. Server should always register with local daemon.Wistributea Computing 27 <4, h encoding network address in object reference is that i joes 0 othe, SS all the object references becomes invalid, This problem can be solved by keeping location «. *hn.\ Ver keep track ©n machine where server is currently running. In this case, object reference contains Retwor, ~ The problem wit agi locati ay, "on Server and systemwide identifier for server. * Object reference may also include more information such as identification of protocol that is Used ty lect and the protocol supported by object server, for example TCP or UDP. Object reference ma, akg LnPlementation handle which refers to complete implementation of proxy which client can Symamicay binding with object. * Parameter Passing Objects can be accessed from remote machines. ‘Object references can be used as parameter to Method ing and these references are passed by value. As a result object references can be copied from one Machine other. If process has object reference then it can bind to the object whenever required, My Itis not efficient to use only distributed or remote objects. Some objects such as Integers and Booleans ay , Fs Therefore it is important to consider references to local objects and remote objects. For remote method in object reference is passed as parameter if object is remote object. This reference is copied and assed og Parameter. Whereas, if object is in the same address space of client then entire object is passed alon 19 With method invocation. That means, object is passed by value. As a example, suppose client code is running on Machine 1 having reference to local object 01, Sener running on Machine 2. Let the remote object 02 resides at machine 3. Suppose client on Machine 1 aly, Program with object O1 as a parameter to call. Client on machine 1 also holds reference to emote object machine 3. Client also uses O2 as a parameter to call. In this invocation, copy of object O1 and copy reference to O: Passed as parameter while calling server on Machine 2. Hence, local objects are passed, and remote objects are passed by reference. Example: Java RMI In Java, distributed objects have been integrated in language itself and goal was to keep semantics as mucho nondistributed objects. The main focus is given on high degree of distribution transparency. The java Distributed Object Model h Java supports distributed object as a remote object which resides on remote machines, Interfaces of he «© objects is implemented by means of proxy which is local object in client interface. Proxy offers preci interface as remote object Cloning of object creates exactly same copy of object and its state. Cloning the remote object. Cloning te object also requires cloning of proxies which currently are bound with object. Therefore cloning is cated >" by server which creates exact copy of object in server address space. In this case, no need to clone proves object, only client has to bind to cloned object in order to access it In Java, method can be declared as synchronized, I two processes try to call synchronizedmethod at te i “act's inte then only one process is permitted to proceed and other is blocked. In this manner, access to object's is entirely serialized. ow” |Distributed Computing 2-8 Communication fed method can be at client side or server side. At client side, client is This blocking of process on synchronizé chines are blocked at blocked in client-side stub which implements object interface. As every client on other ma client side, synchronization among them is required which is complex to implement. process is possible. But, if client crashes while server is executing its invocation then Server side blocking of client ct is restricted to proxies. protocol is needed to handle this situation. In Java RMI blocking on remote objes ‘a Remote Object Invocation In Java, any primitive or object type can be the objects are serializable. Most of the object types are serial are passed by value and remote objects are passed by reference. passed as parameter to RMI if it can be marshaled. Then it is said that lizable except platform dependent objects. In RMI local objects e includes network address, port number of server and object identifier. Server class lass contains implementation of remote object tation of methods that works on this state. In Java RMI, object referenc ‘and client class are two classes used to build remote object. Server cl that runs on server. It contains description object state, implement Skeleton is generated from interface specification of the object. Client class contains implementation of client-side code. This class contains implementation of proxy. This class is generated from interface specification of the object. Proxy builds the method invocation in message which then it sends to server. The reply from server is converted in result of method invocation by proxy. Proxy stores network address of server machine, port number and object identifier. In Java, proxies are serializable. Proxies can be passed to remote process in terms of message. This remote process then can use this proxy for method invocation of remote object. Proxy can be used as reference to remote object. Proxy is treated as local object and hence can be passed as parameter in RMI. As size of proxy is large, implementation handle is generated and used to download the classes to construct Prov. Hence, implementation handle replaces marshaled code as part of remote object reference. Java virtual machine is on every machine. Hence, marshaled proxy can be executed after unmarshaling it on remote or other machine. ication Message-Oriented Commu In Remote Procedure Call (RPC) and Remote method invocation (RMI), communication is inherently synchronous re client blocks till reply from server arrives. For communication between client and server, both sending and iving sides should be executing, Messaging system assumes both side applications are running while munication is going on. Message queuing-system permits processes to communicate although receiving side is not jing at the time communication is initiated. 1 Persistence Synchronicity in Communication In message-oriented communication, we assume that applications executes on hosts, These hosts offer interface to the communication system through which messages are sent for transmission. All the hosts are connected through network of communication servers. These communication servers are responsible for routing the messages between the hosts connected in network. Buffer is available at each host and communication server. Consider Email system with above configuration of hosts and communication servers. Here, user agent program runs on host using which users can read, compose, sends or receive the messages. User agent sends message permits to send message at destination.emission. Host then forward this mess, utput buffer and look UP transport jeg eto destination mail server and forwarg a m Us Ser agent program at host submits message to host for tran’ mail server. This mail server stores the received message in 0! destination mail server, It then establishes the connection with Femoving it from output buffer. in order to deliver to designated receiver, ervices of interface available thee b) ar} At destination mail server, message is put in input buffer Teceiving host can check incoming messages on regular basis by using at case, messages are buffered at communication servers (mail servers). * Message sent by source host is buffered by communication server 95 long as it is SUCceSstully deliver, ing message for transmission, sending application neeg may it is not necessary for receiving Poke n is called as persistent comm, communication server. Hence, after submi execution as message is stored by communication server. Als0, executing when message was submitted. This form of communicatio Email is example of persistent communication. in above * In transient communication, communication system (communication server USSION) sea message if both sender and receiver applications are executing. Otherwise message is discarded. tn the. r message to next communication server gr. | discussed above, if communication server is not able to deliver then message is discarded. All the transport-level communication services offer transient communication and in this communication plays the role of communication server. Router simply drops message if it is not able to forward it to nex rai destination host. © In asynchronous communication, sender continues execution after submitting message for transmisseg sent message either remains in buffer of sending host or at first communication server. In communication, sender is blocked until message is stored in local buffer of destination host or deiv: receiving application. 2.4.2. Combination of Communication Types + Following are the combinations of different types of communication stion,message is persistently stored in «Persistent Asynchronous Communication: In this type of commut of local host or in buffer of first communication server. Email is the example of persistent asynctiot communication. Fig. 2.4.1 shows this type of communication in which process A continues its execution’ sending the message. After this, B receives the message when it will start running. Asends message Astopped and continues runningDistributed Computing 210 Communication Persistent Synchronous Communication : In this communication sender is blocked unti its message is stored at receiver's buffer. In this case, receiver side application may not be running at the time message is stored. In Fig, 2.4.2, Process A sends message and is blocked till message is stored in buffer of receiver. Note that. process 8 starts running after some time and receives the message. Asends message Astopped ‘and waits until accepted running A Message is stored ‘8 B's location for Fig. 2.4.2 Transient Asynchronous Communication : In this type of communication, sender immediately continues its execution after sending the message. Message may remain in local buffer of sender's host. Communication system the routes the message to destination host, If receiver process is not running at the time message is received then Example is transport-level datagram services such as UDP. In Fig. 24.3, Process A sends message transmission ‘execution, While at receiver host, if process B is executing at the time message is arrived then B and continues receives the message. Example is one way RPC. B receives message Fig. 24.3 Receipt-Based Transient Synchronous Communication : In this type of communication, sender is blocked until message is stored at local butter of receiver host. Sender continues its execution after it receives acknowledgement of receipt of message. It is shown in Fig. 24.4. Send request and wait until received Running, buidoing Process ‘something else request Fig. 244 Delivery-Based Transient Synchronous Communication : In this type of communication, sender is blocked until message is delivered to the target process. It is shown in Fig, 2.4. Asynchronous RPC is example of this type of communication Wy mation:Woistributea Computing i Send requ nti es and wan — q . mn this type of COMMUNICATION, SENder is bg PC and RMI StiCKS to this ty, Response-Based Transient Synchronous Communicatior Until response is received from receiver process, It is shown in Fig 2 AG. communication ‘Send request and wait for reply Running, but doing Process something else request Fig. 2.4.6 «In distributed system, there is need of all communication types a5 Per requirements of applications 1p developed. 2.4.3. Message-Oriented Transient Communication ich several applications and distributed systems ae Transport layer offers message-oriented model using whi as per needs. Berkley sockets are transport-level sockets which is the example of messaging. Berkley Sockets «Transport layer offer programm possible due to focus given on standardizing the interfaces. The standard interfaces also allow to pr application on different computers. Socket interface is introduced in Berkley UNIX. ers to use all the messaging protocols through simple set of primitives «Socket is communication endpoint to which application writes data to be sent to applications running ong machines in the network. Application also reads the incoming data from this communication endpoint Foloe are socket primitives for TCP. «Socket : This primitive is executed by server to create new communication endpoint for particular 4 protocol. The local operating system internally reserve resources for incoming and outgoing messages *! specified protocol. This primitive is also executed by elient to create socket at client side. But, here binding address to this socket is not required as operating system dynamically allocate port when connection is set © Bind : This primitive is executed by i a y Server to bind IP address of the machine and port number to create? Port number may be possibly well-known port. This bindi 1 L inding informs the OS ill receive mest on specified IP address and port number. hat sive wl receve ww JDistributed Computing 2412 Communication Listen:Server calls this primitive only in connection-oriented communication. This call permits operating system to reserve sufficient required buffers for maximum number of connections that caller wanted to accept. It is nonblocking call Accept : This is executed by server and call to these primitive blocks the caller until connection request ial one. This new socket is arrives.Local operating system then creates new socket with same properties like ori then retumed to the caller which permits the server to fork off the process to handle actual communication through this new connection, After this, server goes back and waits for new connection request on original socket. Connect : This primitive executed by client to get transport-level address in order to send connection request. The client is blocked till the connection is set up successfully. Send : This primitive executed byboth client and server to send the data over the established connection. Receive : This primitive executed byboth client and server to receive the data over the established connection. itive which establish sending and Both client and server exchange the information through write and read pri receiving of the data. Close : Client and server both calls close primitive to close the connection ¢ Passing Interface The message passing interface (MPI) uses messaging primitive to support transient communication. Following are ‘some of the messaging primitives used. PI_bsend : This primitive is executed by sender of the message to put outgoing message to local send buffer of PI runtime system. Here, sender continues after copying message in buffer. Transient Asynchronous ‘ommunication in Fig. 2.4.3 is supported through this primitive. PLsend : This primitive is executed by sender to send the message and then waits either until message is copied local buffer of MPI runtime or until receiver has initiated receive operation. First case is given by Fig. 2.5.4 and econd case is given in Fig. 245. iPI_ssend : This primitive is executed by sender to send the message and then waits until receipt of the message rts by receiver. This case is given in Fig. 2.4.5. PLsendrecy : This primitive supports synchronous communication given in Fig. 2.4.6 Sender is blocked until ly from receiver. PI_isend : This primitive avoids the copying of message to MPI runtime buffer from user's buffer. Sender passes inter to message and after this MPI runtime system handles the communication. PI_issend : Sender passes pointer to MPI runtime system. Once message processing is done by MPI runtime tem , sender guaranteed that receiver accepted the message for processing. PI_recv : It is called to receive a message. It blocks caller until message arrives. PI_irecy : Same as above but here receiver indicates that it is ready to accept message. Receiver checks whether jessage is arrived or not. It supports asynchronous communication.2.13 Lom istributed Computing ‘4 Message-Oriented Persistent Communication ‘ iddleware Message-queuing systems or Message-oriented Mi thee %, i iver of Communication. In this type of communication, sender or rece! \ ‘ransmission. Message is stored in intermediate storage. Message-Queuing Model 2 (MOM) supports persistent ay ed not be a ssage ne Ve ding yy communication Servers. Each apy, Je. In this system, guarantee is give, * be delivered at any time. ‘ man} * In message-queuing system, messages are forwarded through a its own private queue to which other application sends the messag} : Je can that its sent message will be delivered to recipient queue. Messagi a ri its queue from sender, A\; + In this system, receiver need not be executing when message arrives in its al 50, Seri of messages betwee not be exe: it is delivered to the receiver. In exchange ig sendy cuting after its message cution modes. receiver, message is delivered to receiver with following exe © Sender and receiver both are running. © Sender running but receiver passive. © Sender passive but receiver running. © Both sender and receiver are passive, * System wide unique name is used as address for destination queue. If message size is large then underyg, fragments and assembles the message in the manner transparent to communicating applications. Ths le having simple interface to offer to applications. Following are the primitives offered. © Put: Sender calls this primitive to pass the message to system in order to put in designated queue Ths non-blocking © Get: It is blocking call by which process having rights removes message from queue. If queue s emp process blocks. Poll: It is nonblocking call and process executing it polls for expected message. If queue is empty message not found then process continues. © Notify : With this primitive, installed handler is called by receiver to check queue for message. General Architecture of a Message-Queuing System * In the message-queuing system, source queue is present either on the local machine of the sender or ant LAN. Messages can be read from local queue, The message put in queue for transmission contains speci ° RSVP-enabled host ‘other RSVP hosts Fig. 2.5.2 : RSVP Protocol Besides above network protocol, intemet classifies the data in terms of differential services which decides priority of packets to be forwarded by current router. Forwarding class is also provided in which traffic is divided in four istinguish time- classes and three ways to drop packets if network is congested. In this way applications may sensitive packets from nonsignificant ones. Distributed system also offers buffers to reduce jitter. The delayed packets are stored in buffer at receiver side for maximum time which will be delivered to application at regular rate. Error detection and correction techniques also used for which allows retransmission of erroneous packets. The lost packets can be distributed over time while delivering to applications. 5.3. Stream Synchronization In case of complex stream, it is necessary to maintain temporal relations between different data stream. Consider example of synchronization between discrete data stream and a continuous data stream. Web server stores slide show presentation which contains slides and audio stream. Slides come from server to client in terms of discrete data stream. The client should play the same audio with respect to current slide. Audio stream here gets synchronized with slide presentation.Synchronization Mechanisms | Wistrivited computing 2 io stream, The data un In playing @ movie, video stream need to be synchronized with auch ing actually ate synchronized. The meaning of data unit depends on Considered. It is necessary to display video frames at a rate of 25 Hz Standard of 29.97 Hz, we could group audio samples into logical displayed (33 msec) level of abstraction at whign 4 or more. If we consider baa, ah units that last as long ag 5 Wie For actual synchronization we have to consider following two issues. . © Mechanisms to synchronize two streams. © Distribution of these mechanisms in network environment. At lowest level, synchronization is carried out on data items of simple streams. In this approach, applica. 4 implement synchronization which is not possible as only it has low-level facilities available. Other bette, ted Could be to offer an application an interface which permits it to control stream and devices in simple yg | At receiver side of complex stream, diferent substeams needs tobe synchroized, To any out sch synchronization specification should be available locally. Common approach is to offer this information by multiplexing the different steams into a single steam having all data units, including those for seh MPEG streams are synchronized in this manner. - Another important issue is whether synchronization should handle by sender or receiver. In case of se synchronization, it may be possible to merge streams into a single stream with a different type of data unit | 2.6 Group Communication In distributed system, it is necessary to have support for sending data to multiple receivers, Ths x communication is called multicast communication. To support multicast communication, many networiee transport-level solutions have been implemented. The issues in these solutions were to setup the pt disseminate the information. Alternative to these solutions is application level multicasting techniques as peer to peer solutions #ew deployed at application layer. It now became easier to set up communication paths. Multicast messages offer good solution to build distributed system with following characteristics. © Fault tolerance based on replicated services : Replicated service is available on group of seves° requests are multicast to all these servers in group, Each server performs the same operation on thiste¥* some member of group fails stil cient will be served by other active members (servers) © Finding discovery servers in spontaneous networking : Servers and clients can use multicast im find discovery services to register their interfaces or to search the interfaces of other services in the system. 5 © Better performance through replicated data : Replication impraves performance. If in some 58 ¢ i ;, i data is placed in client machine then changes in data item is multicast to all the processes ™™ replicas. © Event Notification lulticast to group to not Some event accurs,Communication Distributed Computing 2-20 .6.1 Application-Level Multicasting nodes are organized into an overlay networklt is then used to disseminate In application-leve! multicasting, not assigned to network routers. Hence, network level routing is information to its members. Group membership is the better solution with compare to routing messages within overlay. ere exists a unique path between every pait of nodes. In overlay network nodes are organized into tree, hence th there are multiple paths between every pair of nodes Nodes also can be organized in mesh network and hence, which offers robustness in case of failure of any node. ribe: an Application Level Mutticasting Scheme Its built on top of Pastry which is also a DHT (distributed hash table) based peer-to-peer system. In order to start a multicast session, node generates multicast identifier(mid). It is randomly chosen160 bit key. It then findsSUCC{mid), which is node accountable for that key and promotesit to be the root of the multicast tree that will be used to send data to interested nodes. ¥F node X wants to join tree, it executes operation LOOKUPImig), This lookup message now with request to join MID (multicast group) gets routed to SUCC(mid) node. While traveling towards the root, this join message passes many nodes. Suppose this join message reaches to node Y. If Y had seen this join request for mid frst time, it will become a forwarder for that group. Now node X will become child of Ywhereas the latter will carry on to forward the join request to the root. If the next node on the root, say Zis also not yet a forwarder, it will become one and record Y as its child and persist to send the join request Alternatively if ¥ (or 2) is already a forwarder for mi it wil also note the earlier ‘sender as its child (ie, X or Y, respectively), but it will not be requirement to send the join request to the root anymore, as Y(or Z) will already be a member of the multicast tree. In this way, multicast tree across the overlay network with two types of nodes gets created. These nodes are: pure forwarder that works as helper and nodes that are forwarders as well, but have clearly requested to join the tree. erlay Construction 1t is not easier to build efficient tree of nodes in overlay. Actual performance is merely based on the routing of messages through the overlay. There are three metric to measure quality of an application-level multicast tree. These are link stress, stretch, and tree cost. Link stress is per link and counts how frequently a packet crosses the same link. If at logical level although packet is forwarded along two different connections, thepart of those connectionsmay in fact correspond to the same physical link. In this case, link stress is greater than 1. The stretch or Relative Delay Penalty (RDP) measures the ratio in the delay between two nodes in the overlay and the delay that those two nodes would experience in the underlying network.Tree cost is a global metric, generally related to minimizing the aggregated link costs. .2. Gossip-Based Data Dissemination ‘As there are large number of nodes in large distributed system, epidemic protocols can be used effectively to disseminate the information among many nodes. There is no centralized component to coordinate the information dissemination. Only local information can be used for the same.