1-intro-zy 分布式計(jì)算簡(jiǎn)介

1、分布式計(jì)算系統(tǒng)Distributed Computing Systems趙 洋 (zy.)2010年秋季學(xué)期本課件來源于Jennifer Welch教授Distributed Algorithms and Systems(CPSC 668)課程1教材: 分布式計(jì)算（第二版），Distributed Computing: Fundamentals, Simulations and Advanced Topics (2nd Edition).Hagit Attiya，Jennifer Welch 著駱志剛 等譯2Distributed SystemsA distributed system is

2、a collection of individual computing devices that can communicate with each other.Distributed systems have become ubiquitous:share resources (computation, storage)communicate (www, email, p2p)increase performancespeedfault toleranceCharacterized byindependent activities (concurrency)loosely coupled

3、parallelism (heterogeneity)inherent uncertainty3Uncertainty in DSUncertainty comes fromdiffering processor speedsdiffering computer architectures varying communication delays(partial) failuresmultiple input streams and interactive behaviormultiple usershuman intrusion4Reasoning about DSUncertainty m

4、akes it hard to be confident that system is correctTo address this difficulty:identify and abstract fundamental problemsstate problems preciselydesign algorithms to solve problemsprove correctness of algorithmsanalyze complexity of algorithms (e.g., time, space, messages)prove impossibility results

5、and lower bounds5Potential Payoff of Theoretical Paradigmcareful specifications clarify intentincreased confidence in correctnessif abstracted well then results are relevant in multiple situationsindicate inherent limitations cf. NP-completeness6Application AreasThese areas have provided classic pro

6、blems in distributed/concurrent computing:operating systems(distributed) database systemssoftware fault-tolerancecommunication networksmultiprocessor architecturescloud computing and grid computingp2pnetwork of things (a network of objects, such as household appliances)7Course Overview: Part I (Fund

7、amentals)two basic communication models:message passingshared memorytwo basic timing models:synchronousasynchronous8Course Overview: Basic ModelsMessage passing Shared memorysynchronousasynchronousYesNoYesYes(Synchronous shared memory model is PRAM)9Course Overview: Part ICovers the canonical proble

8、ms and issues:graph algorithms (Ch 2)leader election (Ch 3)mutual exclusion (Ch 4)fault-tolerant consensus (Ch 5)causality and time (Ch 6)10Course Overview: Part II (Simulations)Here simulations means abstractions, or techniques for making it easier to program, by making one model appear to be an ea

9、sier model. For example:broadcast and multicast (Ch 8)distributed shared memory (Ch 9)stronger kinds of shared variables (Ch 10)more synchrony (Chs 11, 13)more benign faults (Ch 12)11Course Overview: Part IIFor each of the techniques:describe algorithms for implementing itanalyze the cost of these a

10、lgorithmsexplore limitationsprovide applications that use the techniques12Course Overview: Part III (Advanced Topics)Push further in some directions already introduced:randomized algorithms (Ch 14)stronger kinds of shared objects of arbitrary type (Ch 15)what kinds of problems are solvable in asynch

11、ronous systems (Ch 16)failure detectors (Ch 17)self-stabilization13Relationship of Theory to Practicetime-shared operating systems: issues relating to (virtual) concurrency of processes such asmutual exclusiondeadlock also arise in distributed systemsMIMD multiprocessors:no common clock = asynchrono

12、us modelcommon clock = synchronous modelloosely coupled networks, such as Internet, = asynchronous model14Relationship of Theory to PracticeFailure models:crash: faulty processor just stops. Idealization of reality.Byzantine (arbitrary): conservative assumption, fits when failure model is unknown or

13、 maliciousself-stabilization: algorithm automatically recovers from transient corruption of state; appropriate for long-running applications15Message-Passing Modelprocessors are p0, p1, , pn-1 (nodes of graph)bidirectional point-to-point channels (undirected edges of graph)each processor labels its

14、incident channels 1, 2, 3,; each processor might not know who is at other end of any channel16Message-Passing Model11221132p3p2p0p117Modeling Processors and ChannelsProcessor is a state machine includinglocal state of the processormechanisms for modeling channelsChannel directed from processor pi to

15、 processor pj is modeled in two pieces: outbuf variable of pi andinbuf variable of pjOutbuf corresponds to physical channel, inbuf to incoming message queue18Modeling Processors and Channelsinbuf1p1s localvariablesoutbuf1inbuf2outbuf2p2s localvariablesPink area (local vars + inbuf) is accessible sta

16、te for a processor.19ConfigurationVector of processor states (including outbufs, i.e., channels), one per processor, is a configuration of the systemCaptures current snapshot of entire system: accessible processor states (local vars + incoming msg queues) as well as communication channels.20Deliver

17、EventMoves a message from senders outbuf to receivers inbuf; message will be available next time receiver takes a stepp1p2m3 m2 m1p1p2m3 m2 m121Computation EventOccurs at one processorStart with old accessible state (local vars + incoming messages)Apply transition function of processors state machin

18、e; handles all incoming messagesEnd with new accessible state with empty inbufs, and new outgoing messages22cComputation Eventd eoldlocalstateabnewlocalstate23ExecutionFormat is config, event, config, event, config, in first config: each processor is in initial state and all inbufs are emptyfor each

19、 consecutive (config, event, config), new config is same as old config except:if delivery event: specified msg is transferred from senders outbuf to receivers inbufif computation event: specified processors state (including outbufs) change according to transition function24AdmissibilityDefinition of

20、 execution gives some basic syntactic conditions.usually safety conditions (true in every finite prefix)Sometimes we want to impose additional constraintsusually liveness conditions (eventually something happens)Executions satisfying the additional constraints are admissible. These are the execution

21、s that must solve the problem of interest.25Asynchronous ExecutionsAn execution is admissible for the asynchronous model ifevery message in an outbuf is eventually deliveredevery processor takes an infinite number of stepsNo constraints on when these events take place: arbitrary message delays and r

22、elative processor speeds are not ruled outModels reliable system (no message is lost and no processor stops working)26Example: FloodingDescribe a simple flooding algorithm as a collection of interacting state machines.Each processors local state consists of variable color, either red or greenInitial

23、ly:p0: color = green, all outbufs contain Mothers: color = red, all outbufs emptyTransition: If M is in an inbuf and color = red, then change color to green and send M on all outbufs27Example: Floodingp1p0p2MMp1p0p2MMdeliver eventat p1 from p0computationevent by p1deliver eventat p2 from p1p1p0p2MMM

24、Mp1p0p2MMcomputationevent by p228Example: Flooding (contd)deliver eventat p1 from p2computationevent by p1deliver eventat p0 from p1etc. to deliverrest ofmsgsp1p0p2MMMMp1p0p2MMMMp1p0p2MMMp1p0p2MMM29NondeterminismThe previous execution is not the only admissible execution of the Flooding algorithm on

25、 that triangle.There are several, depending on the order in which messages are delivered.For instance, the message from p0 could arrive at p2 before the message from p1 does.30TerminationFor technical reasons, admissible executions are defined as infinite.But often algorithms terminate.To model algo

26、rithm termination, identify terminated states of processors: states which, once entered, are never leftExecution has terminated when all processors are terminated and no messages are in transit (in inbufs or outbufs)31Complexity MeasuresThese are worst-case normally.Message complexity: maximum numbe

27、r of messages sent in any admissible executionTime complexity: maximum time until termination in any admissible execution.But how is time measured in an asynchronous execution?32Time ComplexityProduce a timed execution from an execution by assigning non-decreasing real times to events such that time

28、 between sending and receiving any message is at most 1.Essentially normalizes the greatest message delay in an execution to be one time unit; still allows arbitrary interleavings of events.Time complexity: maximum time until termination in any timed admissible execution.33Complexity of Flooding Alg

29、orithmDefine terminated states to those in which color = green.Message complexity: one message is sent over each edge in each direction. So number is 2m, where m = number of edges.Time complexity: diameter + 1 time units. (A node turns green once a chain of messages has reached it from p0.)34Synchro

30、nous Message Passing SystemsAn execution is admissible for the synchronous model if it is an infinite sequence of roundsWhat is a round?It is a sequence of deliver events that move all msgs in transit into inbufs, followed by a sequence of computation events, one for each processor.35Synchronous Message Passing Sys