{small lecturenumber - heblocknumber :} Time in Distributed Systemsaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Logical clocksaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Global stateaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Synchronizationaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Distributed Computationaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Events and timeaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Distributed Computationaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Distributed Computationaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Cause and Effectaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Happens beforeaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Happens beforeaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Space-time diagramaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Space-time diagramaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Local and global stateaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Cutsaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Monitoring a distributed computationaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Monitoring a distributed computationaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Monitoring a distributed computationaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Monitoring a distributed computationaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Consistent cutsaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Passive monitoraddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Synchronous communicationaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Why does this work?addtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Logical clocksaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Logical clock exampleaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Logical clocksaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Adding livenessaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Causal deliveryaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Vector clocksaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Vector Clock exampleaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Vector clocksaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Using cutsaddtocounter {blocknumber}{1}{small lecturenumber - heblocknumber :} Summaryaddtocounter {blocknumber}{1}Distributed Software DevelopmentSynchronizationChris BrooksDepartment of Computer ScienceUniversity of San FranciscoDepartment of Computer Science — University of San Francisco – p.1/??4-0: Time in Distributed SystemsIn systems with multiple CPUs, the clocks are unlikely tohave the exact same time.Variations in manufacturing cause clock skew.Insight: often, it doesn’t matter exactly what time anoperation happens, but what order events occur in.(exception: hard real-time systems)Department of Computer Science — University of San Francisco – p.2/??4-1: Logical clocksA logical clock is just a counter(or set of counters)What’s important is that all processes in the system canuse it to produce a consistent ordering.This lets all processes in the system construct a globalview of the system state.Department of Computer Science — University of San Francisco – p.3/??4-2: Global stateMany interesting problems in distributed computing can beexpressed in terms of determining whether some propertyp is satisfied.ConsensusDeadlockTerminationLoad balancingThe general version of this problem is called the GlobalPredicate Evaluation ProblemDepartment of Computer Science — University of San Francisco – p.4/??4-3: SynchronizationFor example, to detect deadlock, we construct a wait-forgraph.Edge from process pito pjif piis waiting on a messagefrom pj.If this graph has a cycle, we have deadlock.How do we do this while the computation is running?We can’t pause the computation and collect all theinformation in one place.Department of Computer Science — University of San Francisco – p.5/??4-4: Distributed ComputationWe define a distributed computation to consist of a set ofprocesses p1, p2, ..., pn.Unidirectional channels exist between each process forpassing messages.We assume these channels are reliable, but notnecessarily FIFO.Messages may arrive out of order.Assume the communication channels are asynchronousNo shared clockNo bound on message delayDepartment of Computer Science — University of San Francisco – p.6/??4-5: Events and timeMost of the time, we don’t necessarily care about theexact time when each event happens.Instead, we care about the order in which events happenon distributed machines.If we do care about time, then the problem becomes oneof synchronizing about the global value of a clock.Department of Computer Science — University of San Francisco – p.7/??4-6: Distributed ComputationA process piconsists of a series of events e1i, e2i, ...There are three types of events:Local events - no communication with other processesSend eventsReceive eventsa local history is a sequence of events e1i, e2i, ... such thatorder is preserved.Department of Computer Science — University of San Francisco – p.8/??4-7: Distributed ComputationThe initial prefix of a history containing the first k events isdenoted: hki= e1i, e2i, ..., ekih0i=<>The Global history of a computation is the union of alllocal histories.h1∪ h2∪ ... ∪ hnNotice that this doesn’t say anything about order of eventsbetween processes.Since an asynchronous system implies that there is noglobal time frame between events, we need some otherway to order events on different processes.Department of Computer Science — University of San Francisco – p.9/??4-8: Cause and EffectCause and effect can be used to produce a partialordering.Local events are ordered by identifier.Send and receive events are ordered.If p1sends a message m1to p2, send(m1) must occurbefore receive(m1).Assume that messages are uniquely identified.If two events do not influence each
View Full Document
Unlocking...