{small lecturenumber - hepage :} Previously on CS 682{small lecturenumber - hepage :} Cause and Effect{small lecturenumber - hepage :} Happens before{small lecturenumber - hepage :} Happens before{small lecturenumber - hepage :} Space-time diagram{small lecturenumber - hepage :} Space-time diagram{small lecturenumber - hepage :} Monitoring a distributed computation{small lecturenumber - hepage :} Synchronous communication{small lecturenumber - hepage :} Why does this work?{small lecturenumber - hepage :} Logical clocks{small lecturenumber - hepage :} Logical clock example{small lecturenumber - hepage :} Logical clocks{small lecturenumber - hepage :} Adding liveness{small lecturenumber - hepage :} Causal delivery{small lecturenumber - hepage :} Vector clocks{small lecturenumber - hepage :} Vector Clock example{small lecturenumber - hepage :} Vector clocks{small lecturenumber - hepage :} Using cuts{small lecturenumber - hepage :} Applying causal delivery{small lecturenumber - hepage :} Consensus and agreement{small lecturenumber - hepage :} Coordination via email{small lecturenumber - hepage :} Failure models{small lecturenumber - hepage :} Failure detection{small lecturenumber - hepage :} Failure detection{small lecturenumber - hepage :} Failure detection{small lecturenumber - hepage :} Multicast: a brief digression{small lecturenumber - hepage :} What is multicast?{small lecturenumber - hepage :} Multicast groups{small lecturenumber - hepage :} Mutual exclusion{small lecturenumber - hepage :} Mutual exclusion{small lecturenumber - hepage :} Mutual exclusion: centralized server{small lecturenumber - hepage :} Mutual exclusion: centralized server{small lecturenumber - hepage :} Mutual exclusion: token ring{small lecturenumber - hepage :} Mutual exclusion: token ring{small lecturenumber - hepage :} Mutual exclusion: multicast{small lecturenumber - hepage :} Mutual exclusion: multicast{small lecturenumber - hepage :} Mutual exclusion: multicast{small lecturenumber - hepage :} Mutual exclusion: multicast{small lecturenumber - hepage :} Dealing with failures{small lecturenumber - hepage :} Election algorithms{small lecturenumber - hepage :} Choosing a leader{small lecturenumber - hepage :} Ring-based election algorithms{small lecturenumber - hepage :} Ring-based election algorithms{small lecturenumber - hepage :} Ring-based election algorithms{small lecturenumber - hepage :} Bully algorithm{small lecturenumber - hepage :} Bully algorithm{small lecturenumber - hepage :} Consensus{small lecturenumber - hepage :} Consensus{small lecturenumber - hepage :} Consensus{small lecturenumber - hepage :} Byzantine generals{small lecturenumber - hepage :} Consensus in synchronous systems{small lecturenumber - hepage :} Byzantine generals in a synchronous system{small lecturenumber - hepage :} Byzantine generals in an asynchronous system{small lecturenumber - hepage :} What do we do in practice?{small lecturenumber - hepage :} Summarizing{small lecturenumber - hepage :} SummaryDistributed Software DevelopmentConsensus and AgreementChris BrooksDepartment of Computer ScienceUniversity of San FranciscoDepartment of Computer Science — University of San Francisco – p. 1/??6-2: Previously on CS 682•Time is a big challenge in systems that don’t share a clock.•Insight: we often don’t need to know the exact time that eventsoccur.•Instead, we need to know the order in which they happened.Department of Computer Science — University of San Francisco – p. 2/??6-3: Cause and Effect•Cause and effect can be used to produce a partial ordering.•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 other, even indirectly, wewon’t worry about their order.Department of Computer Science — University of San Francisco – p. 3/??6-4: Happens before•The happens before relation is denoted →.•Happens before is defined:◦If eki, eliand k < l, then eki→ eli◦(sequentially ordered events in the same process)◦If ei= send(m) and ej= receive(m), then ei→ ej◦(send must come before receive)◦If e → e′and e′→ e′′, then e → e′′◦(transitivity)•If e 6→ e′and e′6→ e, then we say that e and e′are concurrent.(e||e′)•These events are unrelated, and could occur in either order.Department of Computer Science — University of San Francisco – p. 4/??6-5: Happens before•Happens before provides a partial ordering over the globalhistory. (H, →)•We call this a distributed computation.•A distributed computation can be represented with aspace-time diagram.Department of Computer Science — University of San Francisco – p. 5/??6-6: Space-time diagramp1p2p3e11e21e31e41e12e22e32e42e13e23e33e43Department of Computer Science — University of San Francisco – p. 6/??6-7: Space-time diagram•Arrows indicate messages sent between processes.•Causal relation between events is easy to detect•Is there a directed path between events?•e11→ e43•e21||e13Department of Computer Science — University of San Francisco – p. 7/??6-8: Monitoring a distributed computation•Recall that we want to know what the global state of the systemis at some point in time.•Active monitoring won’t work◦Updates from different processes may arrive out of order.•We need to restrict our monitor to looking at consistent cuts•A cut is consistent if, for all events e and e′◦(e ∈ C and e′→ e) ⇒ e′∈ C•In other words, we retain causal ordering and preserve the’happens before’ relation.Department of Computer Science — University of San Francisco – p. 8/??6-9: Synchronous communication•How could we solve this problem with synchronouscommunication and a global clock?•Assume FIFO delivery, delays are bounded by δ◦send(i) → send(j) ⇒ deliver(i) → deliver(j)◦Receiver must buffer out-of-order messages.•Each event e is stamped with the global clock: RC(e).•When a process notifies p0of event e, it includes RC(e) as atimestamp.•At time t, p0can process all messages with timestamps up tot − δ in increasing order.•No earlier message can arrive after this point.Department of Computer Science — University of San Francisco – p. 9/??6-10: Why does this work?•If we assume a delay of δ, at time t, all messages sent beforet − δ have arrived.•By processing
View Full Document
Unlocking...