1、Distributed SystemInstructor: Dr. Ying ZhaoSci. Building 407 (Office location)64433221 (Phone)64414105 (Fax) (Email)Text: Distributed System, Nancy Lynch, Morgan-Kaufmann, 1996.1ExpectationsAttendance is expected, but not mandatoryIf you miss class, you are responsible for obtaining the lectures fro

2、m the website and/or notes from a classmateYou should come prepared to classRead ahead email me if you are unsure of what to readDownload lectures that are on PowerPoint take notes as well2Problem SetsAssignments related to the text and lecture materials not formally graded There will be due dates o

3、n which the answers to the assignments will be worked out in class You are strongly encouraged to discuss possible solutions with other class members to bring to class your solutions 3Project and ExamsThere will be one project worth 25% of your gradeTopics will be assigned by the instructorFormat, c

4、ontent, and due dates There will be three exams and a final.Each exam is worth 25% of your grade.You can drop the lowest exam grade.Tentative exam dates: Feb. 3rd, Mar. 2nd, Apr. 6th, Apr. 29th (final). 4The Rise of Distributed SystemsComputer hardware prices are falling and power increasing.Network

5、 connectivity is increasing.Everyone is connected with fat pipes.It is easy to connect hardware together.5Definition“A distributed system is a collection of independent computers that appears to its users as a single coherent system.” (Distributed Systems: Principles and Paradigms, written by Tanenb

6、aumImportant Points:The machines are autonomous.Users think they are dealing with a single system.6What is a Distributed System?Contains independent, autonomous components thatare located at networked computerscommunicate and coordinate through synchronous or asynchronous message passingare linked b

7、y software designed to produce an integrated computing facilityappear to the user of the system as a single component7What is Computer Network?The term computer network means a collection of autonomous computers interconnected by a single technology in this book.The key distinction is that in a dist

8、ributed system, a collection of independent computers appears to its users as a single coherent system.8Why a Distributed System?Functional distributioncomputers have different functional capabilities yet may need to share resourcesClient / serverData gathering / data processingInherent distribution

9、 in application domaincash register and inventory systems for supermarket chainscomputer supported collaborative work9Distributed Systems Middleware?10Distributed System ExamplesThe biggest example is the WWW.The model presented to users to somewhat uniform go to this URL and get a web page.Most use

10、rs are (or should be) unable to tell what kind of hardware or software is being used to deliver the web page.For the most part, the client should not make a difference either.11GoalsThere are four main goals for distributed systems to make them worth building.Connect users and resourcesMake the syst

11、em transparentMake the system openMake the system scalable12Connecting Users and ResourcesWe want to make it easier for users to access remote resources and to share resources with other users.Examples: printers, files, Web pages, etcA distributed system should also make it easier for users to excha

12、nge information.Easier resource and data exchange could cause security problems a distributed system should deal with this problem.13TransparencyTransparency is the ability of the distributed system to hide that fact that it is actually a distributed system.The more the distributed system looks like

13、 a single computer, the more transparent it is.There are several different types of transparency that we should consider14Transparency TypesTransparencyDescriptionAccessHide differences in data representation and how a resource is accessedLocationHide where a resource is locatedMigration Hide that a

14、 resource may move to another locationRelocationHide that a resource may be moved to another location while in useReplicationHide that a resource may be shared by several competitive usersConcurrencyHide that a resource may be shared by several competitive usersFailureHide the failure and recovery o

15、f a resourcePersistenceHide whether a (software) resource is in memory or on disk15An important goal of a distributed system is to hide the fact that its processesand resources are physically distributed across multiple computers. A distributedsystem that is able to present itself to users and appli

16、cations as if it were only asingle computer system is said to be transparent .For example, resources may be replicated to increase availability or to improve performance by placing a copy close to the place where it is accessed.16Degree of TransparencyWe may not be able to hide all distribution aspe

17、cts from the user and sometime we shouldnt.Physical limitations can cause situations where it is better for the user to know about the distributed system.We cant expect our morning paper to be in our mailbox at 7am if the paper is coming from a different time zone.17System OpennessOpenness describes

18、 how well a system offers services according to some standard rules for the distributed system.An open system will have a set of well-defined standards that describe the syntax and semantics for system services.If the system is not open, it will be difficult to expand.18System ScalabilityA distribut

19、ed system should be scalable. Scalability can be measured in three different ways:size (add more users and resources)geographically (add users and resources that are far away)administration (easily able to manage if scaled)19Scalability ProblemsSizewill present limitations on centralized resources s

20、uch as specialized servers, data and algorithmsWe should decentralize our servers, data and algorithms as much as possible.This causes issues with data consistency and data retrieval.20Decentralized AlgorithmsSuch algorithms should realize:No machine has complete information about the system stateMa

21、chine make decisions based only on local informationFailure of one machine does not ruin the algorithmThere is no implicit assumption that a global clock exists21Scaling TechniquesUse only asynchronous communicationDistribute the problem as much as possible to many machines in small chunksReplicate

22、components across the system (if possible)Cache data where possible (and then solve the cache consistency problems)22Why a Distributed System?Load balancingassign tasks to processors such that the overall system performance is optimizedReplication of processing powerindependent processors working on

23、 the same taskEconomics collections of microprocessors offer a better price/ performance ratio than large mainframes23Distributed System CharacteristicsConcurrencySoftware/hardware components are autonomous component is equivalent to “processor”Components execute concurrent tasks A and B are concurr

24、ent if either A can happen before B, or B can happen before A (interleaving semantics) Users work independently & share resourceshardware components (disks, printers)software entities (files, web pages, data objects)Typical problemsabsence of deadlock Program 1 requests resource A and receives it. P

25、rogram 2 requests resource B and receives it. Program 1 requests resource B and is queued up, pending the release of B. Program 2 requests resource A and is queued up, pending the release of A.liveness guarantees24No global clockCoordination is done by message exchangeClose coordination depends on a

26、 shared idea of the time at which the programs actions occurThere are limits to the accuracy with which computers in a network can synchronize their clocksNo global stateGenerally, there is no single process in the distributed system that would have a knowledge of the current global state of the sys

27、temDistributed System Characteristics25Independent failuresNetwork faults can result in the isolation of computers that continue executingA system failure or crash might not be immediately known to other systems Distributed System Characteristics26Example 1InternetHeterogeneous network of computers

28、and applicationsInteraction via message passing for a common means of communicationUsers in different physical locations can make use of services, such as email and ftpThe set of services is open-ended27intranetISPdesktop computer:backbonesatellite linkserver:%network link:%A Typical Portion of the

29、Internet 28Example 2IntranetsA portion of the Internet that is separately administeredusually proprietaryprovides internal and external servicescan be configured to enforce local security policiesmay use a firewall to prevent unauthorized messages leaving or enteringmay be connected to the internet

30、via a router29A Typical Intranet 30Other ExamplesMobile and ubiquitous computingMobile computingcontinuous service is available to the internet, company intranetsex. Cell phone can access simple informationUbiquitous computingcomputing devices will become so pervasive they will not be noticeablewear

31、ables, PDAs, digital camerasIssuesdiscovery of resources, eliminating reconfiguration of devices from movement, coping with limited connectivity, privacy and security31Portable and handheld devices in a distributed system32Challenges in Distributed System DesignHeterogeneitynetworks (protocols), har

32、dware (data types)operating systems (APIs)programming languages (characters and data structures)implementations by different developers (lack of standards)Middlewarecan mask heterogeneityprovides a uniform computational model for use by the programmers of servers and distributed applicationsMobile c

33、odetransparency from hard-, software and programming language heterogeneity through virtual machine concept33Challenges in Distributed System DesignOpennessThe degree to which new resource-sharing services can be added and be made available for use by a variety of client programsSpecification and do

34、cumentation of the key software interfaces of the components must be publishedExtension may be at the hardware level by introducing additional computers34Challenges in Distributed System DesignSecurity of information resourcesEncryption techniques have resolved many challenges with sending sensitive

35、 information in a message across a network in a secure mannerContinued challengesDenial of service attacksSecurity of mobile code35Challenges in Distributed System DesignScalabilitysystem remains effective when there is a significant increase in the number of resources and the number of userscontrol

36、ling the cost of physical resourcesadding servers to allow for increased controlling the cost of performance lossincreases in data storage and accesspreventing software resources from running outtrade-offs between allocating too much vs. too litleavoiding performance bottlenecksalgorithms should be

37、decentralized36Challenges in Distributed System DesignFailure handlingIn distributed systems, some components fail while others continue executingDetected failures can be hidden, made less severe, or toleratedmessages can be retransmitteddata can be written to multiple disks to minimize the chance o

38、f corruptionData can be recovered when computation is “rolled back”Redundant components or computations tolerate failure37Challenges in Distributed System DesignConcurrencySeveral clients may attempt to access a shared resource at the same timeebay bidsGenerally multiple requests are handled concurr

39、ently rather than sequentiallyAll shared resources must be responsible for ensuring that they operate correctly in concurrent environment38Challenges in Distributed System DesignTransparencythe system is perceived as a whole rather than as a collection of independent componentsExamples includeAccess

40、 transparency*: enables local and remote resources to be accessed using identical operations.Location transparency*: enables resources to be accessed without knowledge of their location.Concurrency transparency: enables several processes to operate concurrently using shared resources without interfe

41、rence between them.Mobility transparency: allows the movement of resources and clients within a system without affecting the operation of users or programs.39Distributed System ArchitecturesClient-server modelclient processes interact with individual server processes servers processes are in separat

42、e host computers clients access the resources the servers manageservers may be clients of other serversExamplesWeb servers are clients of the DNS serviceDNS translates Internet Domain Names to network addressesSearch engines are both servers (to browser clients) and clients (web crawlers) of other w

43、eb servers40Client-Server41Multiple ServersSeparate processors interact to provide a service 42Peer ProcessesAll processors play a similar role - eliminate servers 43Distributed AlgorithmsA definition of the steps to be taken by each of the processes of which the system is composed, including the me

44、ssages transmitted between themTypes of distributed algorithmsInterprocess Communication (IPC)Timing ModelFailure Model44Distributed AlgorithmsAddress problems ofresource allocation- deadlock detectioncommunication- global snapshotsconsensus- synchronizationconcurrency control- object implementation

45、Have a high degree ofuncertainty and independence of activitiesunknown # of processes & network topologyindependent inputs at different locationsseveral programs executing at once, starting at different times, operating at different speedsprocessor non-determinismuncertain message ordering & delivery timesprocessor & communication failures45Interprocess CommunicationDistributed algorithms run on a collection of processorscommunication methods may be shared memory, point-point or broadcast messages, and RPCMult