MLM-III

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERINGAlpha college of engineering Department Of Computer science and engineering Minimum learning materialFor the third year B.E (CSE) Degree Course (R-2013) Semester-VI 1

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING TABLE OF CONTENTS LIST OF SUBJECTS PAGE NO.CURRICULUM 3CS6601 DISTRIBUTED SYSTEMS 4IT6601 MOBILE COMPUTING 58CS6660 COMPILER DESIGN 102CS6659 ARTIFICIAL INTELLIGENCE 147IT6004 SOFTWARE TESTING 196 246CS6611 MOBILE APPLICATION DEVELOPMENTLABORATORY 255 265CS6612 COMPILER LABORATORYGE6674 COMMUNICATION AND SOFT SKILLS-LABORATORY BASEDIT6502 DIGITAL SIGNAL PROCESSING 2

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING ANNA UNIVERSITY, CHENNAI AFFILIATED INSTITUTIONS R-2013 B.E. COMPUTER SCIENCE AND ENGINEERING VI SEMESTER CURRICULUM AND SYLLABIS.No Course Course Title L T PC CodeTHEORY1. CS6601 Distributed Systems 3 0 032. IT6601 Mobile Computing 3 0 033. CS6660 Compiler Design 3 0 034. IT6502 Digital Signal Processing 3 1 045. CS6659 Artificial Intelligence 3 0 036. IT6004 Software Testing 3 0 03PRACTICAL7. CS6611 Mobile Application Development 0 0 32 Laboratory8. . CS6612 Compiler Laboratory 0 0 32 Communication And Soft Skills -9. GE6674 0 0 42 Laboratory Based TOTAL 18 1 10 25 3

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING CS6601 - DISTRIBUTED SYSTEMSCS6601 DISTRIBUTED SYSTEMS LTPC 3 003UNIT I INTRODUCTION (7)Introduction – Examples of Distributed Systems–Trends in Distributed Systems – Focuson resource sharing – Challenges. Case study: World Wide Web.UNIT II COMMUNICATION IN DISTRIBUTED SYSTEM (10)System Model – Inter process Communication – the API for internet protocols –External data representation and Multicast communication. Network virtualization:Overlay networks. Case study: MPI Remote Method Invocation And Objects: RemoteInvocation – Introduction Request-reply protocols – Remote procedure call – Remotemethod invocation. Case study: Java RMI – Group communication – Publish-subscribesystems – Message queues – Shared memory approaches -Distributed objects – Casestudy: Enterprise Java Beans -from objects to components.UNIT III PEER TO PEER SERVICES AND FILE SYSTEM (10)Peer-to-peer Systems – Introduction – Napster and its legacy – Peer-to-peer –Middleware – Routing overlays. Overlay case studies: Pastry, Tapestry- Distributed FileSystems –Introduction – File service architecture – Andrew File system. File System:Features-File model -File accessing models – File sharing semantics Naming:Identifiers, Addresses, Name Resolution – Name Space Implementation – Name Caches– LDAP.UNIT IV SYNCHRONIZATION AND REPLICATION (9)Introduction – Clocks, events and process states – Synchronizing physical clocks-Logical time and logical clocks – Global states – Coordination and Agreement –Introduction – Distributed mutual exclusion – Elections – Transactions and ConcurrencyControl– Transactions -Nested transactions – Locks – Optimistic concurrency control –Timestamp ordering – Atomic Commit protocols -Distributed deadlocks – Replication –Case study – Coda.UNIT V PROCESS & RESOURCE MANAGEMENT (9)Process Management: Process Migration: Features, Mechanism – Threads: Models,Issues, Implementation. Resource Management: Introduction- Features of SchedulingAlgorithms –Task Assignment Approach – Load Balancing Approach – Load SharingApproach. TOTAL: 45 PERIODSTEXT BOOK:1. George Coulouris, Jean Dollimore and Tim Kindberg, “Distributed Systems Conceptsand Design”, Fifth Edition, Pearson Education, 2012. 4

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERINGREFERENCES:1. Pradeep K Sinha, “Distributed Operating Systems: Concepts and Design”, PrenticeHall of India, 2007.2. Tanenbaum A.S., Van Steen M., “Distributed Systems: Principles and Paradigms”,Pearson Education, 2007.3. Liu M.L., “Distributed Computing, Principles and Applications”, Pearson Education,2004.4. Nancy A Lynch, “Distributed Algorithms”, Morgan Kaufman Publishers, USA,2003. 5

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING CS6601 - DISTRIBUTED SYSTEM Index SheetUNIT PAGE NUMBER No. TOPIC Notes PART- A PART-BI Introduction 78 11II Communication in 13 19 23 distributed systemIII Peer-to-Peer services and file 27 30 35 systemIV Synchronization and 37 40 45 replication Process and resource 47 49 52V management 56ANNA UNIVERSITY QUESTION PAPER 6

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING UNIT I INTRODUCTIONIntroduction – Examples of Distributed Systems–Trends in Distributed Systems – Focuson resource sharing – Challenges. Case study: World Wide Web. KEY NOTESDISTRIBUTED SYSTEMS A distributed system is one in which components located at networkedcomputers communicate and coordinate their actions only by passing messages. Thisdefinition leads to the following especially significant characteristics of distributedsystems: concurrency of components, lack of a global clock and independent failures ofcomponents. What are the challenges done here and focus on sharing the resources.EXAMPLES OF DISTRIBUTED SYSTEMS  The Internet  Intranet  Mobile and ubiquitous computing  Web Search  Massively Multiplayer Online Games  Financial TradingTRENDS IN DISTRIBUTED SYSTEMS  Pervasive networking and the modern Internet  Mobile and ubiquitous computing  Distributed Multimedia systemsFOCUS ON RESOURCE SHARING  Search Engine  Computer-Supported cooperative working  Client server computing  Remote invocationCHALLENGES  Heterogeneity  Openness  Security  Scalability  Failure Handling  Concurrency  Transparency  Quality of serviceCASE STUDY: WORLD WIDE WEB  HTML  URL 7

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING  Publishing a resource  HTTP  Request-reply interactions  Content Types  Once resource per request  Simple Access control  Dynamic pages  Dynamic code  Web Services  Discussion of the web PART-A1 . Define distributed systems? A distributed system is a piece of software that ensures that: A collection ofindependent computers that appears to its users as a single coherentsystem or single system.Two aspects:  Independent computer  Single system=>Middleware2. Give examples of distributed systems?  Financial trading  Massively multiplayer online games (MMOGs)  Web search  Network of workstations  Automatic banking (teller machine) system  Automotive system (a distributed real-time system)  Distributed Real-Time Systems  Synchronization of physical clocks  Scheduling with hard time constraints  Real-time communication  Fault tolerance.3. Write the following (i ) HTTP (ii) HTML (iii) URL HTTP:The Hyper Text Transfer Protocol defines the ways in which browsersand other types of client interact with web servers. HTTP is a „request-reply‟ protocol.The client sends a request message to the server containing the URL of the requiredresource. The server looks up the path name and, if it exists, sends back the resource‟scontent in a reply message to the client. Otherwise, it sends back an error response suchas the familiar „404 Not Found‟. HTML: The Hyper Text Markup Language is used to specify the text andimages that make up the contents of a web page, and to specify how they are laid out 8

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERINGand formatted for presentation to the user. A web page contains such structured items asheadings, paragraphs, tables and images.URL: The purpose of a Uniform Resource Locator is to identify a resource.Browsers examine URLs in order to access the corresponding resources. Sometimes the usertypes a URL into the browser. More commonly, the browser looks up the correspondingURL when the user clicks on a link or selects one of their „bookmarks‟; or when the browserfetches a resource embedded in a web page, such as an image. For example,mailto:[email protected] identifies a user‟s email address; ftp://ftp.downloadIt.com/software/aProg.exe identifies a file that is to be retrieved using the File Transfer Protocol(FTP) rather than the more commonly used protocol HTTP.4. What are the uses of web services?A Web service is a method of communication between two electronic devicesover the Web(Internet).Web services are intrinsically integrated into the World WideWeb, using web standards to represent and discover services. The World WideWeb consortium (W3C).5. Define heterogeneity?Internet enables users to access services and run applications over aheterogeneous collection of computers and networks. Heterogeneity (that is, variety anddifference) applies to all of the following:  Networks;  Computer Hardware;  Operating Systems;  Programming Languages;  Implementations by different developers.6. What are the characteristics of heterogeneity?When event notifications are used as a meansof communication, components in a distributed system that were not designed tointeroperate can be made to work together.All that is required is that event-generating objects publish the types of eventsthey offer, and that other objects subscribe to patterns of events and provide an interfacefor receiving and dealing with the resultant notifications.For example, publish subscribe systems describes how to connect heterogeneouscomponents in the Internet.7. What is the purpose of heterogeneity mobile code?Several recently developed programming languages have been designed toenable Programs to be loaded into a process from a remote server and then executedlocally. In that case, the internal interfaces and objects within an executing process maybe exposed to attack by mobile code. 9

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING8. Why we need openness? The openness of a computer system is the characteristic that determines whetherthe system can be extended and reimplemented in various ways. The openness ofdistributed systems is determined primarily by the degree to which new resource-sharingservices can be added and be made available for use by a variety of client programs.9. How we provide security? Many of the information resources that are made available and maintained indistributed systems have a high intrinsic value to their users. Their security is thereforeof considerable importance. Security for information resources has three components: confidentiality(protection against disclosure to unauthorized individuals), integrity (protection againstalteration or corruption), and availability (protection against interference with the meansto access the resources).10. Define scalability? Distributed systems operate effectively and efficiently at many different scales,ranging from a small intranet to the Internet. A system is described as scalable if it willremain effective when there is a significant increase in the number of resources and thenumber of users. The number of computers and servers in the Internet has increased dramatically.11. What are the types of transparencies?Various transparencies types are as follows,  Access transparency  Location transparency  Concurrency transparency  Replication transparency  Failure transparency  Failure transparency  Performance transparency  Scaling transparency12. Define transparencies? Transparency is defined as the concealment from the user and the applicationprogrammer of the separation of components in a distributed system, so that the systemis perceived as a whole rather than as a collection of independent components. Theimplications of transparency are a major influence on the design of the system software.13. what are the objectives in distributed systems?(may/jun2012)  Local autonomy  No reliance on a central site  Continuous operation  Location transparency  Distributed Query processing 10

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING  Distributed transaction management 14. What are the characteristics of distributed systems?  Shared resources  Openness  Concurrency  Scalability  Fault tolerance  Transparency 15. What are the challenges used in distributed systems?  Heterogeneity  Openness  Security  Scalability  Failure handling  Concurrency  Transparency 16. List out the various goals of distributed systems?  Efficiency  Flexibility  Consistency  Robustness  Connecting resources and users  Distribution transparency  Openness  Scalability17. Significance of distributed system?  Concurrency  No global clock  Independent failures18. Write the consequences of distributed system?  Concurrency  No global clock  Independent Failures PART-B1 . State and explain the challenges of distributed systems?  Heterogeneity  Openness  Security  Scalability  Failure handling 11

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING  Concurrency  Transparency2. Define the term distributed system. Explain with two examples? (May/jun2012) A distributed system is one in which component located at networked computerscommunicate and coordinates their actions only by passing messages. This definitionleads to the following characteristics of distributed system.Examples of distributed system:  Financial trading  Massively multiplayer online games (MMOGs)  Web search3. Explain the Differences between intranet and internet?  Internet  Internet is wide network of computers and is open for all.  Internet itself contains a large number of intranets.  The number of users who use internet is Unlimited.  The Visitors traffic is unlimited.  Internet contains different source of information and is available for all.  Intranet  Intranet is also a network of computers designed for a specific group of users.  Intranet can be accessed from Internet but with restrictions.  The number of users is limited.  The traffic allowed is also limited.  Intranet contains only specific group information.Therefore the Internet is an open, public space, while an intranet is designed to be aprivate space. An intranet may be accessible from the Internet, but it is protected by apassword and accessible only to authorized users.4. State and explain the various challenges of distributed systems? (May/jun2012)  Heterogeneity  Openness  Security  Scalability  Failure handling  Concurrency  Transparency5. Write in detail about www?  HTML  URL  HTTP  Dynamic pages & Web service 12

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING UNIT II COMMUNICATION IN DISTRIBUTED SYSTEMSystem Model – Inter process Communication – the API for internet protocols –External data representation and Multicast communication. Network virtualization:Overlay networks. Case study: MPI Remote Method Invocation And Objects: RemoteInvocation – Introduction Request-reply protocols – Remote procedure call – Remotemethod invocation. Case study: Java RMI – Group communication – Publish-subscribesystems – Message queues – Shared memory approaches -Distributed objects – Casestudy: Enterprise Java Beans -from objects to components KEYNOTES System model of a distributed system is communication between processes andachieved by means of message. Characteristics of protocols for communication betweenprocess in a distributed system, both in its own right as support for communicationbetween distributed objects. Parameters in remote invocations. Second half of the portion for the remote procedure call (RPC) approach extendsthe common programming abstraction of the procedure call to distributed environments,allowing a calling process to call a procedure in a remote node as if it is local. Remote method invocation (RMI) is similar to RPC but for distributed objects,with added benefits in terms of using object-oriented programming concepts indistributed systems and also extending the concept of an object reference to the globaldistributed environments, and allowing the use of object references as parameters inremote invocations.SYSTEM MODEL  INTRODUCTION  Difficulties and threats for distributed systems  PHYSICAL MODELS  Baseline Physical model  Early distributed Systems  Internet Scale distributed System  Contemporary distributed system  Distributed systems of Systems  ARCHITECTURAL MODELS  Architectural Elements  Communicating Entities  Communication Paradigms  Roles and responsibilities  Mapping of services to multiple server  Architectural Patterns  Layering 13

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING  Tiered Architecture  The role of AJAX  Thin Clients  Other commonly occurring patterns  Associated Middleware solutions  Categories of Middleware  Limitations of Middleware  FUNDAMENTAL MODELS  Interaction Model  Performance of communication channels  Two variants of interaction model  Computing clocks and timing events  Agreement in pepperland  Event Ordering  Failure Model  Omission Failures  Communication omission Failures  Arbitrary Failures  Failure detection  Timing Failures  Masking Failures  Reliability of one-to-one communication  SECURITY MODELS  Protecting objects  Securing processes and their interactions  The enemy  Threats to processes  Threats to communication channel  Defeating security threats  Cryptography and shared secrets  Authentication  Secure channel  Other Possible Threats From An Enemy  Denial Of service  Mobile code  The uses of security ModelsINTER PROCESS COMMUNICATION  INTRODUCTION  Message passing abstraction 14

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING  DatagramTHE API FOR INTERNET PROTOCOLS  The Characteristics Of Inter process Communication  Synchronous and asynchronous communication  Message destinations  Reliability  Ordering  Sockets  Java API for internet addresses  UDP datagram communication  Failure model for UDP datagrams  Omission failures  Ordering  Use of UDP  Java API for UDP datagrams  TCP stream communication  Failure Model  Use of TCP  Java API for TCP streamEXTERNAL DATA REPRESENTATION AND MULTICASTCOMMUNICATION  CORBA common data representation  Java Object Serialization  Extensible Markup Language  XML elements and attributes  Remote Object and references  Multicast communication  IP multicast- An implementation of multicast communication  Reliability and ordering of multicastNETWORK VIRTUALIZATION: OVERLAY NETWORKS  Overlay Networks  Skype: An example of an overlay network  Skype Architecture  User connection  Search for users  Voice connectionCASE STUDY: MPI REMOTE METHOD INVOCATION AND OBJECTSREMOTE INVOCATION  INTRODUCTION  REQUEST –REPLY PROTOCOLS 15

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING  Request-reply protocols  Message identifier  Failure model of request-reply protocol  Timeouts  Discarding duplicate request message  Lost reply messages  History  Styles of exchange protocols  Use of TCP streams to implement the request-reply protocol  HTTP methods  Message contentsREMOTE PROCEDURE CALL  Design issues for RPC  Programming with interfaces  Interfaces in distributed systems  Interface definition Languages  RPC call semantics  Maybe semantics  At-least once semantics  At-most once semantics  Transparency  Implementation of RPC  Case study : Sun RPC  Interface definition language  Binding  AuthenticationREMOTE METHOD INVOCATION  Design issues for RMI  The object model  Object references  Interfaces  Actions  Exceptions  Garbage collection  Distributed objects  The distributed object model  Remote object references  Remote interfaces  Actions in a distributed – object system 16

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING  Exceptions  Implementation of RMI  Communication module  Remote reference module  Servants  The RMI software  Generation of the classes for proxies, dispatchers and skeletons  Dynamic invocation: An alternative to proxies  Dynamic skeletons  Server and client programs  Factory methods  The binder  Server threads  Activation of remote objects  Distributed garbage collectionCASE STUDY: JAVA RMI  Remote interfaces in Java RMI  Parameter and result passing  Downloading of classes  RMI registry  Building client and server program  Client program  Callbacks  Design and implementation of Java RMI  Use of reflection  Java classes supporting RMIGROUP COMMUNICATION  The programming model  Process groups and object groups  Other key distinctions  Implementation issues  Reliability and ordering in multicast  Group membership management  Case study: the JGroups toolkit  Channels  Building blocks  The protocol stackPUBLISH-SUBSCRIBE SYSTEMS  Applications of publish-subscribe systems  Dealing room system 17

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING  Characteristics of publish-subscribe systems  The programming model  Implementation issues  Centralized versus distributed implementations  Overall systems architecture  Examples of publish-subscribe systemsMESSAGE QUEUES  The programming model  Implementation issues  Case study: WebSphere MQ  Case study: The Java Messaging Service (JMS)  Programming with JMS  A simple exampleSHARED MEMORY APPROACHES  Distributed shared memory  Message passing versus DSM  Tuple space communication  The programming model  Properties associated with tuple spaces  Variations on a theme  Implementation issues  Replication  Other approaches  Case study: Java Spaces  Programming with Java Spaces  A simple exampleDISTRIBUTED OBJECTS  INTRODUCTION  Distributed object middleware  Component-based middleware  Distributed objects  The differences  The added complexitiesCASE STUDY: ENTERPRISE JAVA BEANS  Enterprise java beans  The EJB component model  POJOs and annotations  Enterprise Java Bean containers in EJB  Dependency injection  Enterprise Java Bean Interception 18

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING  Interception of methods  Interception of lifecycle events From objects to components  Issues with object-oriented middleware  Implicit dependencies  Interaction with the middleware  Lack of separation of distribution concerns  Lack of separation of distribution concerns Essence of components  Components and distributed systems  Containers  Support for deployment PART-A1. Define System model?The system under consideration contains a collection of processes, which cancommunicate reliably over one-to-one channels. As before, processes may fail only bycrashing. System model includes a collection of processes pi( i = 1, 2,…..,N )communicating by message passing. An important requirement that applies in manypractical situations is for consensus to be reached even in the presence of faults.2. What is the architectural model?Architectural models describe a system in terms of the computational andcommunication tasks performed by its computational elements; the computationalelements being individual computers or aggregates of them supported byappropriate network interconnections. Client-server and peer-to-peer are two of themost commonly used forms of architectural model for distributed systems.3. What is the fundamental model?Fundamental models take an abstract perspective in order to describe solutions toindividual issues faced by most distributed systems. Fundamental model should containonly the essential ingredients that we need to consider understanding and reasoningabout some aspects of a system‟s behaviour. The purpose of such a model is:  To make explicit all the relevant assumptions about the systems we are modeling. possible or impossible To make generalizations concerning what isgiven those assumptions. The generalizations may take the form of general-purpose algorithms or desirable properties that are guaranteed. The guaranteesare dependent on logical analysis and, where appropriate, mathematical proof.4. Define Middleware?The term middleware applies to a software layer that provides a programmingabstraction as well as masking the heterogeneity of the underlying networks, hardware,operating systems and programming languages. 19

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING In addition to solving the problems of heterogeneity, middlewareprovides a uniform computational model for use by the programmers of servers anddistributed applications.5. What are the different types of model? Each type of model is intended to provide an abstract, simplified but consistentdescription of a relevant aspect of distributed system design:  Physical models are the most explicit way in which to describe a system; they capture the hardware composition of a system in terms of the computers (and other devices, such as mobile phones) and their interconnecting networks.  Architectural models describe a system in terms of the computational and communication tasks performed by its computational elements; the computational elements being individual computers or aggregates of them supported by appropriate network interconnections.  Fundamental models take an abstract perspective in order to examine individual aspects of a distributed system.6. Which type of network can be used by distributed system? The networks used in distributed systems are built from a variety of transmissionmedia, including wire, cable, fiber and wireless channels; hardware devices, includingrouters, switches, bridges,hubs, repeaters and network interfaces; and software components,including stacks, protocol communication handlers and drivers. The resulting functionality and performance available to distributed system andapplication programs is affected by all of these. The computers and other devices that usethe network for communication purposes are referred to as hosts. The term node is used torefer to any computer or switching device attached to a network.7. What are the different types of network? The main types of network that are used to support distributed systems:  Personal area networks  Local area networks  Wide area networks  Metropolitan area networks and the wireless variants of them.Internetworks such as the Internet are constructed from networks of all these types.8. Define latency? The delay between the start of a messages transmission from one process andthe beginning of its receipt by another is referred to as latency.The latency includes:  The time taken for the first of a string of bits transmitted through a network to reach its destination. For example, the latency for the transmission of a message through a satellite link is the time for a radio signal to travel to the satellite and back. 20

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING The time taken by the operating system communication services at both thesending and the receiving processes, which varies according to the currentload on the operating systems.9. What is meant by networking?Networking is the practice of linking two or more computing devices together forthe purpose of sharing data. Networks are built witha mix of computer hardware and computer software. Where at least one process in onedevice is able to send/receive data to/from at least one process residing in a remote device,then the two devices are said to be in a network.10. What is meant by internetworking?Internetworking is the practice of connecting a computer network with othernetworks through the use of gateways that provide a common method of routinginformation packets between the networks. The resulting system of interconnectednetworks is called an internetwork, or simply an internet .The most notable example ofinternetworking is the Internet.11.What is meant by interprocess Communication?Interprocess communication consists of transmitting a message between a socketin one process and a socket in another process for a process to receive messages, itssocket must be bound to a local port and one of the Internet addresses of the computeron which it runs.Messages sent to a particular Internet address and port number can be receivedonly by a process whose socket is associated with that Internet address and port number.12. What is the difference between RMI and RPC?In RMI, a calling object can invoke a method in a potentially remote object. As WithRPC, the underlying details are generally hidden from the user RMI allows the programmerto pass parameters not only by value, as input or output parameters, but also by objectreference The remote procedure call approach was a significant breakthrough distributed insystems, providing higher level support for programmers by extending the concept of aprocedure call to operate in a networked environment13.Define Datagram? The term „datagram‟ refers to the similarity of this delivery mode to the way inwhich letters and telegrams are delivered. The essential feature of datagram networks is thatthe delivery of each packet is a „one-shot‟ process; no setup is required, and once the packetis delivered the network retains no information about it.14. What is the use of UDP?For some applications, it is acceptable to use a service that is liable to occasionalomission failures. For example, the Domain Name System, which looks up DNS names inthe Internet, is implemented over UDP. Voice over IP (VOIP) also runs over UDP. UDPdatagrams are sometimes an attractive choice because they do not suffer from the overheadsassociated with guaranteed message delivery. 21

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING15. What are the methods provides by datagram socket? For a process to receive messages, its socket must be bound to a local port and oneof the Internet addresses of the computer on which it runs. Messages sent to aparticular Internet address and port number can be received only by a process whose socketis associated with that Internet address and port number. Processes may use the same socketfor sending and receiving messages. Each computer has a large number (216) ofpossible port numbers for use by local processes for receiving messages. Any process maymake use of multiple ports to receive messages, but a process cannot share ports with otherprocesses on the same computer.16. What are the characteristic of network hidden by stream abstraction? The following characteristics of the network are hidden by the streamabstraction:  Message sizes Lost messages  Flow control  Message duplication and ordering  Message destinations17. What is the use of remote object references? When a client invokes a method in a remote object, an invocation message is sent tothe server process that hosts the remote object. This message needs to specifywhich particular object is to have its method invoked. A remote object reference is an identifier for a remote object that is valid throughouta distributed system. A remote object reference is passed in the invocation message tospecify which object is to be invoked..18. What is meant by client server communication? Client-server communication, with a different (private) region between theserver and each of its local clients. Such a region contains one or more A (for argument)stacks to support client-server communication. SOAP specifies how to use the HTTP POST Method for the request message and itsresponse for the reply message. The combined use of XML and HTTP provides a standardprotocol for client-server communication over the Internet.19. What is meant by group communication? Group communication is particularly useful for achieving fault tolerance, whichdescribes techniques for high availability, including disconnected operation. It includes case studies of the gossip architecture, Bayou and the Coda file system.It also examines how to support transactions on replicated data.20. What is the use of RMI registry? The RMI registry is the binder for Java RMI. An instance of RMI registry shouldnormally run on every server computer that hosts remote objects. It maintains a tablemapping textual, URL-style names to references to remote objects hosted on that computer.It is accessed by methods of the Naming class, whose methods take as an argument a URL- 22

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERINGformatted string of the form: //computer Name: port/object Name where computer Nameand port refer to the location of the RMI registry.21. Explain the use of Reflection in RMI? Reflection is a pattern that is increasingly being used in distributed systems as ameans of supporting both introspection (the dynamic discovery of properties of thesystem) and intercession (the ability to dynamically modify structure or behaviour). Forexample, the introspection capabilities of Java are used effectively inthe implementation of RMI to provide generic dispatching. PART-B1. Briefly explain group communication?(may/jun2012)  The programming model  Process groups and object groups  Other key distinctions  Implementation issues  Reliability and ordering in multicast  Group membership management  Case study: the JGroups toolkit  Channels  Building blocks  The protocol stack2. Explain how inter process communication is handled in UNIX?(may/jun2012)  Datagram communication  Stream communication3. What is RMI? How it is implemented?  Implementation of RMI  Communication module  Remote reference module  Servants  The RMI software  Generation of the classes for proxies, dispatchers and skeletons  Dynamic invocation: An alternative to proxies  Dynamic skeletons  Server and client programs  Factory methods  The binder  Server threads  Activation of remote objects 23

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING4. Describe remote object and its remote interface?  The object model  Object references  Interfaces  Actions  Exceptions  Garbage collection  Distributed objects  The distributed object model  Remote object references  Remote interfaces  Actions in a distributed – object system5. Write note on the design issues from RMI?(may/jun2012)  Remote Method Invocation  Design issues for RMI  Interfaces in distributed system  Interface definition languages  RPC call semantics  Maybe semantics  Atleast once semantics  Atmost once semantics  Transparency6. With a neat sketch explain remote procedure call?REMOTE PROCEDURE CALL  Design issues for RPC  Programming with interfaces  Interfaces in distributed systems  Interface definition Languages  RPC call semantics  Maybe semantics  At-least once semantics  At-most once semantics  Transparency  Implementation of RPC  Case study : Sun RPC  Interface definition language  Binding  Authentication 24

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING7. Write short note on: i) External data representation and marshalling ii) Client- Server Communication? i) External data representation and marshalling  CORBA common data representation  Java Object Serialization  Extensible Markup Language  XML elements and attributes  Remote Object and references  Multicast communication  IP multicast- An implementation of multicast communication  Reliability and ordering of multicast ii) Client-server communication  The request-reply protocol.  Message identifier.  Failure model of the request-reply protocol.  Timeouts.  Discarding duplicate request message.  Lost reply message.  History.  RPC exchange protocols.  HTTP methods and message contents.8. Explain about fundamental model?  FUNDAMENTAL MODELS  Interaction Model  Performance of communication channels  Two variants of interaction model  Computing clocks and timing events  Agreement in pepperland  Event Ordering  Failure Model  Omission Failures  Communication omission Failures  Arbitrary Failures  Failure detection  Timing Failures  Masking Failures  Reliability of one-to-one communication  SECURITY MODELS  Protecting objects  Securing processes and their interactions 25

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING  The enemy  Threats to processes  Threats to communication channel  Defeating security threats  Cryptography and shared secrets  Authentication  Secure channel  Other Possible Threats From An Enemy  Denial Of service  Mobile code  The uses of security Models9. Explain about architectural model?  Architectural Elements  Communicating Entities  Communication Paradigms  Roles and responsibilities  Mapping of services to multiple server  Architectural Patterns  Layering  Tiered Architecture  The role of AJAX  Thin Clients  Other commonly occurring patterns  Associated Middleware solutions  Categories of Middleware  Limitations of Middleware10. Write about API for the Internet Protocols?  The Characteristics Of Inter process Communication  Synchronous and asynchronous communication  Message destinations  Reliability  Ordering  Sockets  Java API for internet addresses  UDP datagram communication  Failure model for UDP datagrams  Omission failures  Ordering  Use of UDP 26

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING  Java API for UDP datagrams  TCP stream communication  Failure Model  Use of TCP  Java API for TCP stream UNIT III PEER TO PEER SERVICES AND FILE SYSTEMPeer-to-peer Systems – Introduction – Napster and its legacy – Peer-to-peer –Middleware – Routing overlays. Overlay case studies: Pastry, Tapestry- Distributed FileSystems –Introduction – File service architecture – Andrew File system. File System:Features-File model -File accessing models – File sharing semantics naming: Identifiers,Addresses, Name Resolution – Name Space Implementation – Name Caches – LDAP. KEYNOTES Peer-to-peer systems represent a paradigm for the construction of distributedsystems and applications in which data and computational resources are contributed bymany hosts on the Internet, all of which participate in the provision of a uniform service.Their emergence is a consequence of the very rapid growth of the Internet, embracingmany millions of computers and similar numbers of users requiring access to sharedresources. A file system is a subsystem of an operating system that performs filemanagement activities such as organization, storing, retrieval, naming, sharing andprotection of files. It is designed to allow programs to use a set of operations thatcharacterize the file abstraction and free the programmers from concerns about thedetails of space allocation and layout of a secondary storage device.PEER TO PEER SYSTEMS  INTRODUCTION  Peer to peer middleware  Overlay routing versus IP routing  Distributed computation  Napster and its legacy  Limitations  Application dependencies  Peer to peer middleware  Functional requirements  Non-functional requirements  Global scalability  Load balancing  Optimization for local interactions between neighbouring peers  Security of data in an environment with heterogeneous trust 27

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING  Anonymity, deniability and resistance to censorship  Routing Overlays  Routing of requests to objects  Insertion of objects  Deletion of objects  Node addition and removal  Overlay Case Studies: Pastry, Tapestry  Pastry  Routing algorithm  Host integration  Host failure or departure  Locality  Fault tolerance  Dependability  Evaluation work  Optimizing overlay lookup latency  Tapestry  From structured to unstructured peer-to-peer  Strategies for effective search  Case study: GnutellaDISTRIBUTED FILE SYSTEMS  Introduction  Characteristics of file systems  File system operations  Distributed file system requirements  Transparency  Concurrent file updates  File replication  Hardware and operating system heterogeneity  Fault tolerance  Consistency  Security  Efficiency  Case studies  File service architecture  SUN NFS  Andrew File SystemFILE SERVICE ARCHITECTURE  Flat file service 28

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING  Directory service  Client module  Flat file service interface  Comparison with UNIX  Access control  Directory service interface  Hierarchic file system  File groupsANDREW FILE SYSTEM  Scenario  Implementation  Cache consistency  Update semantics  Other aspects  Unix kernel modifications  Location Database  Threads  Read-only replicas  Bulk transfer  Partial file caching  Performance  Wide-area supportFILE SYSTEMS  Features  File –Accessing models  Accessing remote files  Remote service model  Data caching model  Unit of data transfer  File-level transfer model  Block level transfer model  Byte level transfer model  Record level transfer model  File sharing semantics  Unix semantics  Session semantics  Immutable shared-files semantics  Transaction-like semantics 29

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERINGNAMING  Names, Identifiers and Addresses  Flat Naming  Simple solutions  Broadcasting and multicasting  Forwarding pointers  Home based Approaches  Distributed hash tables  General mechanism  Exploiting Network Proximity  Hierarchical approaches  Structured Naming  Name spaces  Name resolution  Name resolution  Closure mechanism  Linking and mounting  Name Space Implementation  Name Space Distribution  Implementation of Name resolution  Name Caches  Types of Name caches  Directory cache  Prefix cache  Full-Name cache  Approaches for Name cache Implementation  Multicache consistency  Immediate Invalidate  LDAP  Directory Information Tree(DIT) PART-A1. Define peer –to- peer systems? Peer –to-peer systems is represent a paradigm for the construction of distributedsystems and applications in which data and computational resources are contributed bymany hosts on the internet, all of which participate in the provision of a uniform service.2. What are the properties of peer to peer applications? Peer-to-peer applications have been used to provide file sharing, web caching,information distribution and other services exploiting the resources of tens of thousandsof machines across the internet. They are at their most effective when used to store very 30

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERINGlarge collections of immutable data. Their design diminishes their effectiveness forapplications that store and update mutable data objects.3. What are the characteristics of peer-to-peer systems? Peer-to-peer systems following the characteristics are given below. Their design ensures that each user contributes resources to the system. Although the may differ in the resources that they contribute, all the nodes in a peer to peer system have the same functional capabilities and responsibilities. Limited degree of anonymity to the providers and users of resources. Correct operation does not depend on the existence of any centrally-administered systems.4. Distinguish between IP and overlay routing for peer-to-peer applications? IP Application-level routing overlayLoad Loads on routers are Object locations can bebalancing determined by network randomized and hence traffic topology and associated patterns are divorced from the traffic patterns. network topology.Target Each IP address maps to Messages can be routed to theIdentification exactly one target node. nearest replica of a target objectSecurity Addressing is only secure Security can be achieved even when all nodes are trusted. in environments with limited trust5. Define peer-to-peer middleware and mention some application for peer-to-peermiddleware? Peer-to-peer middleware systems are designed specifically to meet the need forthe automatic placement and subsequent location of the distributed objects managed bypeer-to-peer system and applications.  Functional requirements.  Non Functional requirements.  Load balancing.  Optimization for local interactions between neighbouring peers.  Accommodating to highly dynamic host availability.6. Define nearest neighbouring algorithm? Nearest neighbouring algorithm is to find a nearby node by recursivelymeasuring the round-trip delay for a probe message sent periodically to each member ofthe leaf set of the nearest currently known pastry node. 31

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING7. Distinguish between pastry and tapestry? Tapestry Pastry Tapestry is the Ocean StorePastry is the Archival file storage system Storage system.It is effective design It is more complex designIt can be used to implement distributed It can be used to implementhash table with API. distributed hash table.8. Define Distributed file systems?A distributed file system enables programs to store and access remote filesexactly as they do local ones, allowing users to access files from any computer on anetwork. The performance and reliability experienced for access to files stored at aserver should be comparable to files stored on local disks.9. What are the requirements of distributed file systems?  Transparency  Concurrent file updates  File replication  Hardware and operating system heterogeneity  Fault tolerance  Consistency  Security  Efficiency10. List out the important goals achieved in NFS?  An important goals of NFS is to achieve a high level of support for hardware and operating system heterogeneity. The design is operating system independent: client and server implementationsexist for almost all operating systems and platforms, including all versions of windows, Mac OS, Linux and every other version of UNIX. Implementations of NFS on high-performance multiprocessor hosts have beendeveloped by several vendors, and these are widely used to meet storagerequirements in intranets with many concurrent users.11. Define Andrew file System?Andrew is a distributed computing environment developed at Carnegie MellonUniversity (CMU) for use as a campus computing and information system. The designof the Andrew file system (AFS) reflects an intention to support information sharing ona large scale by minimizing client-server communication. This was achieved bytransferring whole files between server and client computers and caching tem at clientsuntil the server receives a more up-to-date version. 32

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING12. What are responsibilities between the modules in file service architecture?  Flat file service  Directory service  Client module13. Draw a diagram for file service architecture?14. Define file system? A file system is a subsystem of an operating system that performs filemanagement activities such as organization, storing, retrieval, naming, sharing andprotection of files. It is designed to allow programs to use a set of operations thatcharacterize the file abstraction and free the programmers from concerns about thedetails of space allocation and layout of a secondary storage device.15. What are the features of distributed file system?  Transparency  User mobility  Performance  Simplicity and easy of use  Scalability  High availability16. What are the services provide in distributed file system?  Storage service  True file service  Name service17. Define Name spaces? A name space is the collection of all valid names recognized by a particularservice. The service will attempt to look up a valid name, even though that name mayprove not to correspond to any object. i.e., to be unbound. Name spaces require asyntactic definition to separate valid names from invalid names. For example, „...‟ is notacceptable as the DNS name of a computer, whereas www.cdk99.net is valid (eventhough it is unbound). 33

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING18. Define domain name?  The DNS translates Internet domain and host names to IP addresses.DNS automatically converts the names we type in our Web browser address bar to the IP addresses of Web servers hosting those sites.  DNS implements a distributed database to store this name and address information for all public hosts on the Internet. DNS assumes IP addresses do not change (are statically assigned rather than dynamically assigned).19. Advantages & Disadvantage distributed system?  Incremental growth: Computing power can be added in small increments.  Reliability: If one machine crashes, the system as a whole can still survive.  Speed: A distributed system may have more total computing power than a mainframe.  Open system: This is the most important point and the most characteristic point of a distributed system. Since it is an open system it is always ready to communicate with other systems. An open system that scales has an advantage over a perfectly closed and self-contained system.  Economic: Microprocessors offer a better price/performance than mainframesDisadvantages of Distributed Systems over centralized ones  Distributed systems will have an inherent security issue.  Networking: If the network gets saturated then problems with transmission will surface.  Software: There is currently very little less software support for Distributed system.  Troubleshooting: Troubleshooting and diagnosing problems in a distributed system can also become more difficult, because the analysis may require connecting to remote nodes or inspecting communication between nodes.20. What are the Issues in designing Distributed System?  Secure communication over public networks ACI: who sent it, did anyone see it, did anyone change it.  Fault-tolerance: Building reliable systems from unreliable components nodes fail independently; a distributed system can “partly fail” [Lamport]: “A distributed system is one in which the failure of a machine I have never heard of can prevent me from doing my work.”  Replication, caching, naming Placing data and computation for effective resource sharing, hiding latency, and finding it again once you put it somewhere. Coordination and shared state.  What should the system components do and when should they do it? Once they have all done it, can they all agree on what they did and when? 34

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING PART-B1. Explain about peer-to-peer system and characteristics of peer to peer system?  Introduction  Characteristics of peer-to-peer system  Peer-to-peer middleware  Overlay routing versus IP routing  Distributed computation2. Explain about peer-to-peer middleware and mention its applications?  Peer to peer middleware  Functional requirements  Non-functional requirements  Global scalability  Load balancing  Optimization for local interactions between neighbouring peers  Security of data in an environment with heterogeneous trust Anonymity, deniability and resistance to censorship3. Explain briefly about pastry, tapestry?  Pastry  Routing algorithm  Host integration  Host failure or departure  Locality  Fault tolerance  Dependability  Evaluation work  Optimizing overlay lookup latency  Tapestry  From structured to unstructured peer-to-peer  Strategies for effective search  Case study: Gnutella4. Briefly explain the file service architecture?  Flat file service  Directory service  Client module  Flat file service interface  Access control  Directory service interface  Hierarchic file system  File groups 35

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING5. Explain the requirements of Distributed file system?  Transparency  Concurrent file updates  File replication  Hardware and operating system heterogeneity  Fault tolerance  Consistency  Security & Efficiency6. Write in detail about distributed file system?  Introduction  Characteristics of file systems  File system operations  Distributed file system requirements  Transparency  Concurrent file updates  File replication  Hardware and operating system heterogeneity  Fault tolerance  Consistency  Security  Efficiency  Case studies  File service architecture  SUN NFS  Andrew File System7. Explain in details the characteristics of file system? (May/jun2012)  Location transparency: file name should not reveal its location  Location independence: file name should not be changed when its physical location changes.  User mobility: access to file from anywhere  Fault tolerance  Scalability  File mobility: move files from one place to another in a running system  File attribute record structure  File system operations  UNIX file system operation8. Explain in detail about naming and how it is implemented?  Names, Identifiers and Addresses  Flat Naming  Simple solutions 36

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING  Broadcasting and multicasting  Forwarding pointers  Home based Approaches  Distributed hash tables  General mechanism  Exploiting Network Proximity  Hierarchical approaches  Structured Naming  Name spaces  Name resolution  Name resolution  Closure mechanism  Linking and mounting  Name Space Implementation  Name Space Distribution  Implementation of Name resolution  Name Caches  Types of Name caches  Directory cache  Prefix cache  Full-Name cache  Approaches for Name cache Implementation  Multicache consistency  Immediate Invalidate  LDAP  Directory Information Tree(DIT) UNIT IV SYNCHRONIZATION AND REPLICATIONIntroduction – Clocks, events and process states – Synchronizing physical clocks-Logical time and logical clocks – Global states – Coordination and Agreement –Introduction – Distributed mutual exclusion – Elections – Transactions and ConcurrencyControl– Transactions -Nested transactions – Locks – Optimistic concurrency control –Timestamp ordering – Atomic Commit protocols -Distributed deadlocks – Replication –Case study – Coda. KEYNOTES The absence of global physical time makes it difficult to find out the state of ourdistributed programs as they execute. We often need to know what state process A is inwhen process B is in a certain state, but we cannot rely on physical clocks to know what 37

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERINGis true at the same time. The second half of the chapter examines algorithms todetermine global states of distributed computations despite the lack of global time. The second half of the chapter examines the related problems of groupcommunication, consensus, Byzantine agreement and interactive consistency. In thecontext of group communication, the issue is how to agree on such matters as the orderin which messages are to be delivered.SYNCHRONIZATION AND REPLICATION  Introduction  Clocks, events and process states  Synchronizing physical clocks  Synchronization in a synchronous system  Cristian‟s method for synchronizing clocks  The Berkeley algorithm  The Network Time protocol  Logical time and logical clocks  Logical clocks  Totally ordered logical clocks  Vector clocks  Global states  Global states and consistent cuts  Global state predicates, Stability, Safety and liveness  The „snapshot‟ algorithm of chandy and lamport  Coordination and Agreement  Introduction  Failure assumptions and failure detectors  Distributed mutual exclusion  Algorithm for mutual exclusion  The central server algorithm  A ring-based algorithm  An algorithm using multicast and logical clocks  Maekawa‟s voting algorithm  Fault tolerance  Elections  A ring- based election algorithm  The bully algorithm  Transactions and concurrency control  Introduction  Simple synchronization  Failure model for transactions  Transactions 38

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING  Concurrency control  Inconsistent retrievals  Serial equivalence  Conflicting operations  Recoverability from aborts  Dirty reads  Recoverability of transactions  Cascading aborts  Premature writes  Strict executions of transactions  Tentative versions Nested transactions Locks  Lock implementation  Locking rules for nested transactions Optimistic concurrency control  Validation of transactions  Forward validation  Comparison of forward and backward validation  Starvation Timestamp ordering  Multiversion timestamp ordering Atomic commit protocol  The two-phase commit protocol  Two-Phase commit protocol for nested transactions  Hierarchic two-phase commit protocol  Flat two-phase commit protocol  A comparison of the two approaches  Timeout actions Distributed deadlocks  Phantom deadlocks  Edge chasing  Transaction priorities Replication  Introduction  System model and group communication  System model  Group communication  Fault tolerant services  Passive replication 39

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING  Active replication  Case study: Coda  The coda architecture  The replication strategy  Update semantics  Accessing replicas  Disconnected operation  Performance PART-A1. What is meant by distributed garbage collection?  An object is considered to be garbage if there are no longer any references to it anywhere in the distributed system. The memory taken up by that object can be reclaimed once it is known to be garbage. To check that an object is garbage, we must verify that there are no references to it anywhere in the system.  For example process p1 has two objects that both have references – one has a reference within p1 itself, and p2 has a reference to the other. Process P 2 has one garbage object, with no references to it anywhere in the system. It also has an object for which neither p1 nor p 2 has a reference, but there is a reference to it in a message that is in transit between the processes.2. Define clock synchronization?  Clock synchronization is a problem from computer science and engineering which deals with the idea that internal clocks of several computers may differ. Even when initially set accurately, real clocks will differ after some amount of time due to clock drift, caused by clocks counting time at slightly different rates.  There are several problems that occur as a repercussion of rate differences and several solutions, some being more appropriate than others in certain contexts. In a centralized system the solution is trivial; the centralized server will dictate the system time.  Cristian's algorithm and the Berkeley Algorithm are some solutions to the clock synchronization problem in a centralized server environment.3. Define Clock Skew? (May/jun2012)  The operation of most digital circuit systems, such as computer systems, is synchronized by a\"clock\"that dictates the sequence and pacing of the devices on the circuit. Ideally, the input to each element has reached its final value before the next clock movement occurs so that the behaviour of the whole circuit can be predicted exactly.  The maximum speed at which a system can run must account for the variance that occurs between the various elements of a circuit due to differences in physical composition, temperature, and path length. 40

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING4. Define Cristian's algorithm?  Cristian's algorithm relies on the existence of a time server. The time server maintains its clock by using a radio clock or other accurate time source, then all other computers in the system stay synchronized with it.  A time client will maintain its clock by making a procedure call to the time server. Variations of this algorithm make more precise time calculations by factoring in network propagation time.5. Define Berkeley algorithm?  This algorithm is more suitable for systems where a radio clock is not present, this system has no way of making sure of the actual time other than by maintaining a global average time as the global time.  A time server will periodically fetch the time from all the time clients, average the results, and then report back to the clients the adjustment that needs be made to their local clocks to achieve the average.  This algorithm highlights the fact that internal clocks may vary not only in the time they contain but also in the clock rate. Often, any client whose clock differs by a value outside of a given tolerance is disregarded when averaging the results. This prevents the overall system time from being drastically skewed due to one erroneous clock.6. Define Network Time Protocol (NTP)?  This algorithm is a class of mutual network synchronization algorithm in which no master or reference clocks are needed. All clocks equally participate in the synchronization of the network by exchanging their timestamps using regular beacon packets.  CS-MNS is suitable for distributed and mobile applications. It has been shown to be scalable, accurate in the order of few microseconds, and compatible to IEEE 802.11 and similar standards.7. What are the aims and features are available in Network Time Protocol?  To provide a service enabling clients across the internet to be synchronized accurately to UTC.  To provide a reliable service that can survive lengthy losses of connectivity.  To enable clients to resynchronize sufficiently frequently to offset the rates of drift found in most computers.  To provide protection against interference with the time service whether malicious or accidental.8. Explain about the Logical time and logical clocks? A logical clock is a mechanism for capturing chronological and causalrelationships in a distributed system.Logical clock algorithms of note are:  Lamport timestamps, which are monotonically increasing software counters. 41

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING  Vector clocks, that allow for partial ordering of events in a distributed system.  Version vectors, order replicas, according to updates, in an optimistic replicated system.  Matrix clocks, an extension of vector clocks that also contains information about other processes' views of the system.9. What are the limitations of Lamport’s clock? If c(a)<c(b) or time - stamp(e) < time - stamp(e`) , then we cannot tell whichone are executed first , with the vector , we may able to determine the precedence. ORa->b implies c (a) < c (b) But c (a) <c (b) does not implies a ->b!! So not a true clock.10. Define Mutual Exclusion?Assumptions  The system consists of n processes; each process Pi resides at a different processor each process has a critical section that requires mutual exclusion Basic Requirement If Pi is executing in its critical section, then no other process Pj is executing in its critical section. The presented algorithms ensure the mutual exclusion execution of processes in their critical sections.  Mutual exclusion must be enforced: only one process at a time is allowed in its critical section A process that hales in its non critical section must do so without interfering with other processes.11. Explain Election Algorithm.  An election algorithm is an algorithm for solving the coordinator election problem. By the nature of the coordinator election problem, any election algorithm must be a distributed algorithm. a group of processes on different machines need to choose a coordinator.  Peer to peer communication: every process can send messages to every other process.  Assume that processes have unique IDs, such that one is highest  Assume that the priority of process Pi is i.12. Explain Ring Algorithm?Assume that processes form a ring: each process only sends messages to the nextprocess in the Ring.  Active list: its info on all other active processes  Assumption: message continues around the ring even if a process along the way has crashed.Background: any process Pi sends a message to the current coordinator; if no responsein T time units, Pi initiates an election  Initialize active list to empty.  Send an “Elect (i)” message to the right. + add i to active list.If a process receives an “Elect (j)” message 42

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING(a) This is the first message sent or seen initialize its active list to [i,j]; send “Elect(i)” +send “Elect(j)”.(b) If i! = j, add i to active list + forward “Elect(j)” message to active list.(c) Otherwise (i = j), so process i has complete set of active processes in its active list.=>choose highest process ID + send “Elected (x)” message to neighbor If a processreceives “Elected(x)” message, set coordinator to x.13. Define transaction? A transaction defines a sequence of server operations that is guaranteed by theserver to be atomic in the presence of multiple clients and server crashes.14. Define optimistic concurrency control? Optimistic concurrency control allows transactions to proceed until they areready to commit, whereupon a check is made to see whether they have performedconflicting operations on objects.15. Define ACID properties?  Atomicity: a transaction must be all or nothing.  Consistency: a transaction takes the system from one consistent state to another consistent state.  Isolation,  Durability. We have not included „consistency‟ in our list of the properties of transactions because it is generally the responsibility of the programmers of servers and clients to ensure that transactions leave the database consistent.16. What is a deadlock? Suppose a process request resources; if the resources are not available at thattime the process enters into a wait state. A waiting process may never again changestate, because the resources they have requested are held by some other waitingprocesses. This situation is called deadlock.17. What are necessary conditions for dead lock?  Mutual exclusion (where at least one resource is non-sharable)  Hold and wait (where a process hold one resource and waits for other resource)  No preemption (where the resources can‟t be preempted).  Circular wait (where p[i] is waiting for p[j] to release a resource. i= 1,2,…n j=if (i!=n) then i+1 else 1 ). 18. List the advantages of nested transactions?  Sub transactions at one level may run concurrently with other sub transactions at the same level in the hierarchy. This can allow additional concurrency in a transaction.  Sub transactions can commit or abort independently. In comparison with a single transaction, a set of nested sub transactions is potentially more robust. 43

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING 19. Define timestamp ordering?  Each operation in a transaction is validated when it is carried out. If the operation cannot be validated, the transaction is aborted immediately and can be restarted by the client.  Each transaction is assigned a unique timestamp value when it start.  The timestamp defines its position in the time sequence of transactions. Request from transactions can be totally ordered according to their timestamp. 20. Explain about the Atomic commit protocol? An atomic commit protocol is a cooperative procedure used by a set of servers involved in a distributed transaction. It enables the servers to reach a joint decision as to whether a transaction can be committed or aborted. 21. Explain about the two phase commit protocol?  Two-phase commit protocol (2PC) is a type of atomic commitment protocol (ACP). It is a distributed algorithm that coordinates all the processes that participate in a distributed atomic transaction on whether to commit or abort the transaction.  The protocol achieves its goal even in many cases of temporary system failure, and is thus widely utilized.  The protocol results in either all nodes committing the transaction or aborting, even in the case of site failures and message losses.22. Define Edge chasing?  Edge-chasing is an algorithm for deadlock detection in distributed systems. Whenever a process A is blocked for some resource, a probe message is sent to all processes A may depend on.  The probe message contains the process id of A along with the path that the message has followed through the distributed system.  If a blocked process receives the probe it will update the path information and forward the probe to all the processes it depends on.  Non-blocked processes may discard the probe. If eventually the probe returns to process A, there is a circular waiting loop of blocked processes, and a deadlock is detected.  Efficiently detecting such cycles in the “wait-for graph” of blocked processes is an important implementation problem.23. What is phantom deadlock?  In distributed deadlock detection, the delay in propagating local information might cause the deadlock detection algorithms to identify deadlocks that do not really exist. Such situations are called phantom deadlocks and they lead to unnecessary aborts. 44

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING24. Define starvation? A thread may wait indefinitely because other threads keep coming in and gettingthe requested resources before this thread does. Note that resource is being actively usedand the thread will stop waiting if other threads stop coming in.25. Define clock drift? (May/jun2012) Clock drift is when a clock does not run at the exact same speed as another. Ifyou have two clocks running at slightly different speeds and no time adjustments aremade, the time displayed by the two clocks would drift further apart over time. PART-B 1. What is the goal of an election algorithm? Explain it detail?(may/jun2012)  Elections  A ring based election algorithm  The bully algorithm 2. Explain how mutual exclusion is handled in distributed system?(may/jun 2012)  Distributed mutual exclusion  Algorithm for mutual exclusion  The central server algorithm  A ring based algorithm  An algorithm using multicast and logical clocks  Maekawa‟s voting algorithm  Fault tolerance 3. Describe the internal and external synchronization of Physical clocks?(may/jun2012)  Synchronizing physical clocks  Synchronization in a synchronous system  Cristian‟s method for synchronizing clocks  The Berkeley algorithm  The Network Time protocol 4. Explain the Chandy and Lamport snapshot algorithm for determining the global states of distributed systems?(may/jun2012)  The „snapshot‟ algorithm of chandy and lamport  Termination of the snapshot algorithm  Characterizing the observed state  Stability and reachability of the observed state 5. Explain in detail about concurrency control in transaction?  Transactions and concurrency control  Introduction  Simple synchronization  Failure model for transactions  Transactions 45

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING  Concurrency control  Inconsistent retrievals  Serial equivalence  Conflicting operations  Recoverability from aborts  Dirty reads  Recoverability of transactions\  Cascading aborts  Premature writes  Strict executions of transactions  Tentative versions6. Discuss in detail about deadlock and locking schemes in concurrency control?  Deadlocks  Definition of deadlocks  Deadlock prevention  Upgrade locks  Deadlock Detection  Timeouts  Increasing concurrency in locking schemas7. Explain optimistic concurrency control?  Optimistic concurrency control  Validation of transactions  Backward validation  Forward validation  Comparison of forward and backward validation  Starvation8. Explain Time stamp ordering in detail?  Timestamp ordering  Operation conflicts for timestamp ordering  Multiversion Timestamp Ordering9. Explain the concurrency control in distributed transactions?  Concurrency control in distributed transactions  Locking  Timestamp ordering concurrency control  Optimistic concurrency control10. Explain about distributed deadlocks?  Distributed deadlocks  Phantom deadlocks  Edge chasing 46

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING 11. Explain about clocks, events and process state?  Clock, event and process states  Clocks  Clock skew and clock drift  Coordinated Universal Time UNIT-V PROCESS AND RESOURCE MANAGEMENTProcess Management: Process Migration: Features, Mechanism – Threads: Models,Issues, Implementation. Resource Management: Introduction- Features of SchedulingAlgorithms –Task Assignment Approach – Load Balancing Approach – Load SharingApproach. KEYNOTES Process management deals with mechanisms and policies for sharing theprocessor of the system among all processes. The main goal of process management isto make the best possible use of the processing resources of the entire system by sharingthem among all processes. Threads are used in programs and what are the operations performed and basicgoal of almost all the load balancing algorithms is to maximize the total systemthroughput. Load sharing approach, which simply attempts to conserve the ability of thesystem to perform work by assuming that no node is idle while processes wait for beingprocessedPROCESS MANAGEMENT  Introduction  Process migration  Features  Transparency  Minimal interference  Minimal residual dependencies  Efficiency  Robustness  Mechanisms  Address space transfer mechanism  Message forwarding mechanisms  Origin site mechanism  Link traversal mechanism  Process migration in heterogeneous systems  Advantages of process migration 47

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERINGTHREADS  Motivations for threads  Models for organizing threads  Dispatcher-workers model  Team model  Pipeline model  Issues in designing a threads package  Threads creation  Threads termination  Threads synchronization  Threads scheduling  Implementation  Thread management  Threads synchronization  Threads scheduling  Signal handling  Error handlingRESOURCE MANAGEMENT  Introduction  Task assignment approach  Load balancing approach  Load sharing approach  Features of scheduling algorithms  No a priori knowledge about the processes  Dynamic in nature  Quick decision-making capability  Balanced system performance and scheduling overhead  Stability  Scalability  Fault tolerance  Fairness of service  Task Assignment approach  The basic idea  Finding an optimal assignment  Load balancing approach  A taxonomy of load-balancing algorithms  Static versus Dynamic  Deterministic versus probabilistic  Centralized versus distributed 48

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING  Cooperative versus Noncooperative  Issues in designing load-balancing algorithms  Load estimation Policies  Process Transfer policies  Location Policies  State information Exchange policies  Priority Assignment policies  Migration Limiting policies  Loan sharing Approach  Issues in designing load-sharing algorithms  Load estimation Policies  Process Transfer policies  Location Policies  State information Exchange policies PART-A1. Define Process Management? Process management deals with mechanisms and policies for sharing theprocessor of the system among all processes. The main goal of process management isto make the best possible use of the processing resources of the entire system by sharingthem among all processes.2. What are the three concept used in distributed operating system?  Process allocation deals with the process of deciding which process should be assigned to which process should be assigned to which processor.  Process Migration deals with the movement of a process from its current location to the processor to which it has been assigned.  Threads deals with fine-grained parallelism for better utilization of the processing capability of the system.3. Define Process Migration? Process migration is the relocation of a process from its current location toanother node. The flow of execution of a migrating process is given below. 49

SEMESTER – VI COMPUTER SCIENCE AND ENGINEERING4. What are the steps involved in process migration?  Selection of a process that should be migrated  Selection of the destination node to which the selected process should be migrated.  Actual transfer of the selected process to the destination node. 5. List out the features of process migration?  Transparency  Minimal Interference  Minimal Residual Dependencies  Efficiency  Robustness 6. What are the major sub activities involved in process migration?  Freezing the process on its source node and restarting it on its destination node.  Transferring the process address space from its source node and its destination node.  Forwarding message meant for the migrant process.  Handling communication between cooperating processes that have been separated as a result of process migration.7. List the various mechanisms used in process migration?  Freezing and restarting process  Address transfer mechanism  Message forwarding mechanism  Mechanism for handling coprocesses. 50