CS 378Intro to Distributed ComputingLorenzo AlvisiAnurag AgarwalWhat is a distributed system?“A distributed system is one in which the failure of a computer you didn’t even know existed can render your own computer unusable.”Leslie LamportLocal OS Local OS Local OSNetworkMachine CMachine BMachine AMiddlewareWhat is a distributed system?A distributed system is software through which a collection of independent computers appears to its users as a single, coherent systemDistributed ApplicationsGoals (and auto-goals) of a Distributed SystemConnecting Resources and UsersTransparencyOpennessScalabilityTransparencyTransparencyDescriptionAccessHides differences in data representation and invocation mechanismsLocationHides where an object residesMigrationHides from an objec that object’s location RelocationHides from a client the change of location of an object to which the client is boundReplicationHides that an object may be replicated, with replicas at different locationsConcurrencyHides coordination of activities between objectsFailureHides the failure and recovery of objectPersistenceHides whether a resource is in memory or on diskOpennessEasily interact with other open systemsConform to well-defined interfacesAchieve independence in heterogeneity wrtHardwarePlatformLanguagesSupport different app/user-specific policiesOpennessEasily interact with other open systemsConform to well-defined interfacesAchieve independence in heterogeneity wrtHardwarePlatformLanguagesSupport different app/user-specific policiesideally, provide only mechanisms!ScalabilitySize scalability number of users and processesGeographical scalabilitymaximum distance between nodesAdministrative scalabilitynumber of administrative domainsScalingDistributepartition data and computation across multiple machineJava applets, DNS, WWWReplicatemake copies of data available at different machinesmirrored web sites, replicated fs, replicated dbCacheallow client processes to access local copiesWeb caches, file cachingConsistencyA first course in Distributed Computing...Two basic approachescover many interesting systems, and distill from them fundamental principlesfocus on a deep understanding of the fundamental principles, and see them instantiated in a few systems A few intriguing questionsHow do we talk about a distributed execution?Can we draw global conclusions from local information?Can we coordinate operations without relying on synchrony?For the problems we know how to solve, how do we characterize the “goodness” of our solution?Are there problems that simply cannot be solved?What are useful notions of consistency, and how do we maintain them?What if part of the system is down? Can we still do useful work? What if instead part of the system becomes “possessed” and starts behaving arbitrarily: All bets are off?Saving the worldbefore bedtimeTwo Generals’ ProblemS.P.Q.RS.P.Q.R• Romans win if attack simultaneously• Otherwise, Barbarians win• Romans must coordinate attackTwo Generals’ ProblemS.P.Q.RS.P.Q.R• only communication is by messenger• messengers must sneak through the valleyProblem:Save Western Civilization(i.e. design a protocol that ensures Romans always attack simultaneously)• they don’t always make itClaim There is no non-trivial protocol that guarantees that the Romans will always attack simultaneously Two Generals’ ProblemProof: Let P be shortest such protocol• consider last message mlast• P must work if mlast never arrives• so don’t send it• but now we have a new protocol shorter than P !Fundamental Limitation: Solution needs• unbounded number of messages or• guaranteed message deliveryOtherwise, attack may never take
View Full Document
Unlocking...