6.852: Distributed Algorithms Fall, 2009Today’s planSelf-stabilizationToday…Self-Stabilization: DefinitionsSelf-stabilizationLegal execution fragmentsSelf-stabilization: DefinitionStronger vs. weaker definition of self-stabilizationNon-terminationSelf-Stabilizing Algorithm 1: Self-Stabilizing Breadth-First Spanning Tree ConstructionBreadth-first spanning treeIn terms of legal sets… BFS Algorithm strategyRoot process P1Non-root process PiNon-root process Pi CorrectnessCorrectnessProof of lemmaProof, cont’dSelf-Stabilizing Algorithm 2: Self-Stabilizing Mutual ExclusionSelf-stabilizing mutual exclusionMutual exclusionLemma 1Lemma 2Lemma 3Lemma 4Putting the pieces togetherReducing the atomicityReducing the atomicityComposing Self-Stabilizing AlgorithmsComposing self-stabilizing algorithmsComposing SS algorithmsWeaker definition of SSComposing SS algorithmsApplying the composition theoremMutual exclusion in a rooted treeSelf-Stabilizing EmulationsSelf-stabilizing emulations [Dolev, Chapter 4]Self-stabilizing emulationsSelf-stabilizing emulationsMaking Non-Self-Stabilizing Algorithms Self-StabilizingMaking non-self-stabilizing algorithms self-stabilizingExample: ConsensusExample: ConsensusExample: ConsensusExtensionsMaking non-SS algorithms SS: Monitoring and Resetting [Section 5.2]Other stuff in the bookNext time…6.852: Distributed AlgorithmsFall, 2009Class 24Today’s plan• Self-stabilization• Self-stabilizing algorithms:– Breadth-first spanning tree– Mutual exclusion• Composing self-stabilizing algorithms• Making non-self-stabilizing algorithms self-stabilizing• Reading: – [ Dolev, Chapter 2 ] • Next time:– Partially synchronous distributed algorithms– Clock synchronization– Reading: • Chapters 23-25 • [Attiya, Welch] Section 6.3, Chapter 13Self-stabilization• A useful fault-tolerance property for distributed algorithms.• Algorithm can start in any state---arbitrarily corrupted.• From there, if it runs normally (usually, without any further failures), it eventually gravitates back to correct behavior.• [Dijkstra 73: Self-Stabilizing Systems in Spite of Distributed Control]– Dijkstra’s most important contribution to distributed computing theory.– [Lamport talk, PODC 83] Reintroduced the paper, explained its importance, popularized it.– Became (still is) a major research direction.– Won PODC Influential Paper award, in 2002.– Award renamed the Dijkstra Prize.• [Dolev book, 00] summarizes main ideas of the field.Today…• Basic ideas, from [ Dolev, Chapter 2 ]• Rest of the book describes:– Many more self-stabilizing algorithms.– General techniques for designing them.– Converting non-SS algorithms to SS algorithms.– Transformations between models, preserving SS.– SS in presence of ongoing failures.– Efficient SS.–Etc.Self-Stabilization: DefinitionsSelf-stabilization• [Dolev] considers:– Message-passing models, with FIFO reliable channels.– Shared-memory models, with read/write registers.– Asynchronous and synchronous models.• To simplify, avoids internal process actions---combines these with sends, receives, or register access steps.• Sometimes considers message losses (“loss” steps).• Many models, must continually specify which is used.• Defines executions:– Like ours, but needn’t start in initial state.– Same as our “execution fragments”.• Fair executions: – Described informally.– Our task-based definition is fine.Legal execution fragments• Given a distributed algorithm A, define a set L of legal execution fragments of A.• L can include both safety and liveness conditions.• Example: Mutual exclusion problem– L might be the set of all fragments α satisfying:• Mutual exclusion:– No two processes are in the critical region, in any state in α.• Progress:– If in some state of α, someone is in T and no one is in C, then sometime thereafter, someone → C.– If in some state of α, someone is in E, then sometime thereafter, someone → R.Self-stabilization: Definition• A global state s of algorithm A is safe with respect to legal set L, provided that every fair execution fragment of A that starts with s is in L.• Algorithm A is self-stabilizing for legal set L if every fair execution fragment α of A contains a state s that is safe with respect to L.– Implies that the suffix of α starting with s is in L.– Also, any other fair execution fragment starting with s is in L.• Weaker definition: Algorithm A is self-stabilizing for legal set L if every fair execution fragment α has a suffix in L.αsIn LαIn LStronger vs. weaker definition of self-stabilization• Stronger definition: Algorithm A is self-stabilizing for legal set L if every fair execution fragment of A contains a state s that is safe with respect to L.• Weaker definition: Algorithm A is self-stabilizing for legal set L if every fair execution fragment has a suffix in L.• [Dolev] generally uses the stronger definition; so will we.• But occasionally, he appears to be using the weaker definition; we’ll warn when this arises.•Q:Equivalent definitions? Not in general. LTTR.Non-termination• Self-stabilizing algorithms for nontrivial problems don’t terminate.• E.g., consider message-passing algorithm A:– Suppose A is self-stabilizing for legal set L, and A has a terminating global state s.• All processes quiescent, all channels empty.– Consider a fair execution fragment α starting with s.– α contains no steps---just global state s.– Since A is self-stabilizing with respect to L, α must contain a safe state.– So s must be a safe state.– Then the suffix of α starting with s is in L; that is, just s itself is in L.– So L represents a trivial problem---doing nothing satisfies it.• Similar argument for shared-memory algorithms.Self-Stabilizing Algorithm 1: Self-Stabilizing Breadth-First Spanning Tree ConstructionBreadth-first spanning tree• Shared-memory model• Connected, undirected graph G = (V,E).• Processes P1,…,Pn, P1a designated root.• Permanent knowledge (built into all states of the processes):–P1always knows it’s the root.– Everyone always knows who their neighbors are.P1P4P3P2r12r21r13r42r24r31• Neighboring processes in G share registers in both directions: –rijwritten by Pi, read by Pj.• Output: A breadth-first spanning tree, recorded in the rijregisters:–rij.parent = 1 if j is i’s