Chapter 2: Self Stabilization Techniques and Paradigms

1. Chapter 2 - Definitions, Techniques and Paradigms 2-1 Chapter 2 Self-Stabilization Self-Stabilization Shlomi Dolev MIT Press , 2000 Draft of May 2003, Shlomi Dolev, All Rights Reserved

2. Chapter 2 - Definitions, Techniques and Paradigms 2-2 Chapter 2: roadmap 2.1 Definitions of Computational Model 2.2 Self-Stabilization Requirements 2.3 Complexity Measures 2.4 Randomized Self-Stabilization 2.5 Example: Spanning-Tree Construction 2.6 Example: Mutual Exclusion 2.7 Fair Composition of Self-Stabilization Algorithms 2.8 Recomputation of Floating Output 2.9 Proof Techniques 2.10 Pseudo-Self-Stabilization

3. Chapter 2 - Definitions, Techniques and Paradigms 2-3 What is a Distributed System? Communication networks Multiprocessor computers Multitasking single processor A Distributed System is modeled by a set of n state machines called processors that communicate with each other

4. Chapter 2 - Definitions, Techniques and Paradigms 2-4 The Distributed System Model Denote : P i - the i th processor neighbor of P i - a processor that can communicate with it How to Represent the Model? Ways of communication message passing - fits communication networks and all the rest shared memory - fits geographically close systems P i P j Link P i <->P j = P i can communicate with P j Node i = Processor i

5. Chapter 2 - Definitions, Techniques and Paradigms 2-5 Asynchronous Distributed Systems Message passing A communication link which is unidirectional from P i to P j transfers message from P i to P j For a unidirectional link we will use the abstract q ij (a FIFO queue) P 1 P 2 P 3 q 13 = () q 32 = () q 21 = (m 2 ,m 10 ) P 1 P 2 P 3 q 13 = () q 32 = (m 1 ) q 21 = (m 10 ) send m 1 receive m 2 P 1 P 2 P 3 q 13 = () q 32 = (m 1 ) q 21 = (m 2 , m 10 )

6. Chapter 2 - Definitions, Techniques and Paradigms 2-6 Asynchronous Distributed Systems - Message passing q System configuration ( configuration ) : Description of a distributed system at a particular time. q A configuration will be denoted by c = (s 1 ,s 2 ,,s n ,q 1,2 ,q 1,3 ,,q i,j ,,q n,n-1 ) , where s i =State of P i q i,j (i j) the message queue m1 P 1 P 2 P 3 q 13 = () q 32 = () q 21 = (m 2 ,m 10 )

7. Chapter 2 - Definitions, Techniques and Paradigms 2-7 Asynchronous Distributed Systems Shared Memory Processors communicate by the use of shared communication registers The configuration will be denoted by c = (s 1 ,s 2 ,,s n ,r 1,2 ,r 1,3 ,r i,j ,r n,n-1 ) where si = State of P i r i = Content of communication register i P 1 P 2 r 12

8. Chapter 2 - Definitions, Techniques and Paradigms 2-8 The distributed System A Computation Step And in message passing model loss 21 (m 3 ) P 1 P 2 q 12 = (m 1 ) q 21 = (m 2 ,m 3 ,m 4 ) P 1 P 2 q 12 = (m 1 ) q 21 = (m 2 ,m 4 ) P 1 receives P 1 P 2 q 12 = (m 1 ) q 21 = (m 4 ) m 2 In shared memory model P 1 P 2 r 12 : m 1 P 1 writes P 1 P 2 r 12 : m 1 P 2 reads m 1 P 1 P 2 m 1 r 12 : x

9. Chapter 2 - Definitions, Techniques and Paradigms 2-9 Scheduling of events in a distributed system influences the transition made by the processors The interleaving model - at each given time only a single processor executes a computation step Every state transition of a process is due to communication-step execution A step will be denoted by a c 1 a c 2 denotes the fact that c 2 can be reached from c 1 by a single step a The Interleaving model

10. Chapter 2 - Definitions, Techniques and Paradigms 2-10 Step a is applicable to configuration c iff c : c a c . In the message passing system - queue q i,j contains m in c k , and in c k+1 m is removed from q i,j and placed in P t and this is the only difference between c k & c k+1 An execution E = (c 1 ,a 1 ,c 2 ,a 2 ,) , an alternating sequence such that c i-1 a c i (i>1) A fair execution - every step that is applicable infinitely often is executed infinitely often In the message passing model - a message which is sent infinitely often will be received infinitely often number of losses is finite The distributed System more definitions

11. Chapter 2 - Definitions, Techniques and Paradigms 2-11 A global clock pulse ( pulse ) triggers a simultaneous step of every processor in the system Fits multiprocessor systems in which the processors are located close to one another The execution of a synchronous system E = (c1,c2,) is totally defined by c1, the first configuration in E Synchronous Distributed Systems 1 4 3 2 q 12 = () q 14 = () q 21 = () q 31 = () q 32 = () 1 4 3 2 q 12 = () q 14 = () q 21 = () q 31 = () q 32 = () send receive * This models message passing, shared memory is analogous with write -> read 1 4 3 2 q 12 = (m 12 ) q 14 = (m 14 ) q 21 = (m 21 ) q 31 = (m 31 ) q 32 = (m 32 ) intermediate state

12. Chapter 2 - Definitions, Techniques and Paradigms 2-12 A desired legal behavior is a set of legal executions denoted LE A self-stabilizing system can be started in any arbitrary configuration and will eventually exhibit a desired legal behavior Legal Behavior c 2 safe c 1 safe c k safe c c i c c c m c l step step step step step step c t safe c safe c safe step step step legal execution

13. Chapter 2 - Definitions, Techniques and Paradigms 2-13 The first asynchronous round ( round ) in an execution E is the shortest prefix E of E such that each processor executes at least one step in E, E=EE. The number of rounds = time complexity A Self-Stabilizing algorithm is usually a do forever loop The number of steps required to execute a single iteration of such a loop is O( ), where is an upper bound on the number of neighbors of P i Asynchronous cycle ( cycle ) the first cycle in an execution E is the shortest prefix E of E such that each processor executes at least one complete iteration of its do forever loop in E, E=EE. Note : each cycle spans O( ) rounds The time complexity of synchronous algorithm is the number of pulses in the execution Time complexity

14. Chapter 2 - Definitions, Techniques and Paradigms 2-14 The space complexity of an algorithm is the total number of (local and shared) memory bits used to implement the algorithm Space complexity

15. Chapter 2 - Definitions, Techniques and Paradigms 2-15 Randomized Self-Stabilization Assumptions and definitions Processor activity is managed by a scheduler The schedulers assumption - at most one step is executed in every given time The scheduler is regarded as an adversary The scheduler is assumed to have unlimited resources and chooses the next activated processor on-line A scheduler S is fair if, for any configuration c with probability 1, an execution starting from c in which processors activated by S is fair

16. Chapter 2 - Definitions, Techniques and Paradigms 2-16 An algorithm is randomized self-stabilizing for task LE if, starting with any system configuration and considering any fair scheduler, the algorithm reaches a safe configuration within a finite number of rounds Randomized algorithms are often used to break symmetry in a system of totally identical processors Randomized Self-Stabilization - Assumptions and definitions ..

17. Chapter 2 - Definitions, Techniques and Paradigms 2-17 2.1 Definitions of Computational Model 2.2 Self-Stabilization Requirements 2.3 Complexity Measures 2.4 Randomized Self-Stabilization 2.5 Example: Spanning-Tree Construction 2.6 Example: Mutual Exclusion 2.7 Fair Composition of Self-Stabilization Algorithms 2.8 Recomputation of Floating Output 2.9 Proof Techniques 2.10 Pseudo-Self-Stabilization Chapter 2: roadmap

18. Chapter 2 - Definitions, Techniques and Paradigms 2-18 Spanning-Tree Construction 0 1 3 2 1 1 2 2 The root writes 0 to all its neighbors The rest each processor chooses the minimal distance of its neighbors, adds one and updates its neighbors

19. Chapter 2 - Definitions, Techniques and Paradigms 2-19 Spanning-Tree Algorithm for P i 01 Root: do forever 02 for m := 1 to do write r im := 0,0 03 od 04 Other: do forever 05 for m := 1 to do write lr mi := read ( r mi ) 06 FirstFound := false 07 dist := 1 + min lr mi . dis 1 m 08 for m := 1 to 09 do 10 if not FirstFound and lr mi . dis = dist -1 11 write r im := 1, dist 12 FirstFound := true 13 else 14 write r im := 0, dist 15 od 16 od = # of processors neighbors i = the writing processor m = for whom the data is written lr ji (local register ji) the last value of r ji read by P i

20. Chapter 2 - Definitions, Techniques and Paradigms 2-20 Spanning-Tree, System and code Demonstrates the use of our definitions and requirements The system l We will use the shared memory model for this example l The system consists n processors l A processor P i communicates with its neighbor P j by writing in the communication register r ij and reading from r ji

21. Chapter 2 - Definitions, Techniques and Paradigms 2-21 Spanning-Tree, System and code The output tree is encoded by means of the registers 1 4 5 8 6 2 3 7 r 21 : parent = 1 dis = 1 r 58 : parent = 8 dis = 3 r 73 : parent = 2 dis = 3

22. Chapter 2 - Definitions, Techniques and Paradigms 2-22 Spanning-Tree Application RUN RUN

23. Chapter 2 - Definitions, Techniques and Paradigms 2-23 Spanning-Tree, is Self-Stabilizing The legal task ST - every configuration encodes a BFS tree of the communication graph Definitions : A floating distance in configuration c is a value in r ij .dis that is smaller than the distance of P i from the root l The smallest floating distance in configuration c is the smallest value among the floating distance l is the maximum number of links adjacent to a processor

24. Chapter 2 - Definitions, Techniques and Paradigms 2-24 Spanning-Tree, is Self-Stabilizing For every k > 0 and for every configuration that follows + 4k rounds, it holds that: ( Lemma 2.1) l If there exists a floating distance, then the value of the smallest floating distance is at least k l The value in the registers of every processor that is within distance k from the root is equal to its distance from the root Note that once a value in the register of every processor is equal to its distance from the root, a processor Pi chooses its parent to be the parent in the first BFS tree, this implies that : The algorithm presented is Self-Stabilizing for ST

25. Chapter 2 - Definitions, Techniques and Paradigms 2-25 Mutual Exclusion The root changes its state if equal to its neighbor The rest each processor copies its neighbors state if it is different root

26. Chapter 2 - Definitions, Techniques and Paradigms 2-26 01 P 1 : do forever 02 if x 1 =x n then 03 x 1 :=(x 1 +1) mod (n+1) 04 P i ( i 1 ): do forever 05 if x i x i-1 then 06 x i :=x i-1 Dijkstras Algorithm

27. Chapter 2 - Definitions, Techniques and Paradigms 2-27 RUN RUN Mutual-Exclusion Application

28. Chapter 2 - Definitions, Techniques and Paradigms 2-28 Dijsktras alg. is Self-Stabilizing A configuration of the system is a vector of n integer values (the processors in the system) The task ME : l exactly one processor can change its state in any configuration, l every processor can change its state in infinitely many configurations in every sequence in ME A safe configuration in ME and Dijkstras algorithm is a configuration in which all the x variables have the same value

29. Chapter 2 - Definitions, Techniques and Paradigms 2-29 A configuration in which all x variables are equal, is a safe configuration for ME (Lemma 2.2) For every configuration there exists at least one integer j such that for every i x i j (Lemma 2.3) For every configuration c, in every fair execution that starts in c, P 1 changes the value of x 1 at least once in every n rounds (Lemma 2.4) For every possible configuration c, every fair execution that starts in c reaches a safe configuration with relation to ME within O(n 2 ) rounds (Theorem 2.1) Dijkstras alg. is Self-Stabilizing

30. Chapter 2 - Definitions, Techniques and Paradigms 2-30 Fair Composition -Some definitions The idea composing self-stabilizing algorithms AL 1 ,..., AL k so that the stabilized behavior of AL 1 , AL 2 ,..., AL i is used by AL i+1 AL i+1 cannot detect whether the algorithms have stabilized, but it is executed as if they have done so The technique is described for k=2 : Two simple algorithms server & client are combined to obtain a more complex algorithm The server algorithm ensures that some properties will hold to be used by the client algorithm

31. Chapter 2 - Definitions, Techniques and Paradigms 2-31 Assume the server algorithm AL 1 is for a task defined by a set of legal execution T 1 , and the client algorithm AL 2 for T 2 Let A i be the state set of P i in AL 1 and S i = A i B i the state set of P i in AL 2 ,where whenever P i executes AL 2 , it modifies only the B i components of A i B i For a configuration c S 1 S n , define the A-projection of c as the configuration (ap 1 , , ap n ) A 1 A n The A-projection of an execution - consist of the A-projection of every configuration of the execution Fair Composition -more definitions

32. Chapter 2 - Definitions, Techniques and Paradigms 2-32 AL 2 is self-stabilizing for task T 2 given task T 1 if any fair execution of AL 2 that has an A-projection in T 1 has a suffix in T 2 AL is a fair composition of AL 1 and AL 2 if, in AL , every processor execute steps of AL 1 and AL 2 alternately Assume AL 2 is self-stabilizing for task T 2 given task T 1 . If AL 1 is self-stabilizing for T 1 , then the fair composition of AL 1 and AL 2 is self-stabilizing for T 2 (Theorem 2.2) Fair Composition -more definitions

33. Chapter 2 - Definitions, Techniques and Paradigms 2-33 Will demonstrate the power of fair composition method What will we do ? Compose the spanning-tree construction algorithm with the mutual exclusion algorithm 0 1 3 2 1 1 2 2 Example : Mutual exclusion for general communication graphs Server Client

34. Chapter 2 - Definitions, Techniques and Paradigms 2-34 Modified version of the mutual exclusion algorithm Designed to stabilize in a system in which a rooted spanning tree exists and in which only read/write atomicity is assumed Euler tour defines a virtual ring P 1 P 4 P 2 P 3 r 1,4 r 1,2 r 1,3 r 3,1 r 2,1 r 4,1 lr 1,3 lr 1,2 lr 1,4 lr 3,1 lr 2,1 lr 4,1

35. Chapter 2 - Definitions, Techniques and Paradigms 2-35 Mutual exclusion for tree structure (for P i ) 01 Root: do forever 02 lr 1,i := read ( r 1,i ) 03 if lr ,i = r i,1 then 04 (* critical section*) 05 write r i,2 := ( lr 1,i + 1 mod (4 n -5)) 06 for m := 2 to do 07 lr m,i = read ( r m,i ) 08 write r i,m+1 := lr m,i 09 od 10 od 11 Other: do forever 12 lr 1,i := read ( r 1,i ) 13 if lr 1,i r i,2 14 (* critical section*) 15 write r i,2 := lr 1,i 16 for m := 2 to do 17 lr m,i := read ( r m,i ) 18 write r i,m+1 := lr m,i 19 od 20 od

36. Chapter 2 - Definitions, Techniques and Paradigms 2-36 Mutual-exclusion can be applied to a spanning tree of the system using the ring defined by the Euler tour Note a parent field in the spanning-tree defines the parent of each processor in the tree When the server reaches the stabilizing state, the mutual-exclusion algorithm is in an arbitrary state, from there converges to reach the safe configuration mutual exclusion for communication graphs

37. Chapter 2 - Definitions, Techniques and Paradigms 2-37 2.1 Definitions of Computational Model 2.2 Self-Stabilization Requirements 2.3 Complexity Measures 2.4 Randomized Self-Stabilization 2.5 Example: Spanning-Tree Construction 2.6 Example: Mutual Exclusion 2.7 Fair Composition of Self-Stabilization Algorithms 2.8 Recomputation of Floating Output 2.9 Proof Techniques 2.10 Pseudo-Self-Stabilization Chapter 2: roadmap

38. Chapter 2 - Definitions, Techniques and Paradigms 2-38 Recomputation of Floating Output -The Idea c 1 c 2 c i c k floating output variables What do we need to prove ? From every possible configuration, an execution of AL will eventually begin from a predefined initial state Any two executions of AL that begin from the initial state have identical output BAD BAD Output BAD Output OK

39. Chapter 2 - Definitions, Techniques and Paradigms 2-39 Demonstrates the core idea behind the recomputation of the floating output Assumptions l We will ignore synchronization issues l We will assume that the system is a message- passing synchronous system Define The synchronous consensus task - a set of (synchronous) executions SC in which the output variable of every processor is 1 iff there exists an input value with value 1 Recomputation of Floating Output Example: Synchronous Consensus

40. Chapter 2 - Definitions, Techniques and Paradigms 2-40 01 initialization 02 pulse := 0 03 O i = I i 04 while pulse i D do 05 upon a pulse 06 pulse i := pulse i + 1 07 send ( O i ) 08 forall P j N(i) do receive ( O j ) 09 if O i = 0 and P j N(i) | O j = 1 then 10 O i := 1 Non-stabilizing synchronous consensus algorithm i : I i = 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 This algorithm is not a self stabilizing algorithm 0 1 0 0 0 0 0 0

41. Chapter 2 - Definitions, Techniques and Paradigms 2-41 01 upon a pulse 02 if ( pulse i mod ( D +1)) = 0 then 03 begin 04 O i = o i (*floating output is assigned by the result*) 05 o i = I i (*initializing a new computation*) 06 end 07 send ( o i , pulse i ) 08 forall P j N(i) do receive ( o j , pulse j ) 09 if o i = 0 and P j N(i) | o j = 1 then 10 o i := 1 11 pulse i := max {{ pulse i } { pulse j | P j N(i) }} +1 Self-stabilizing synchronous consensus algorithm

42. Chapter 2 - Definitions, Techniques and Paradigms 2-42 Self-stabilizing synchronous consensus algorithm The output variable O i of every processor P i is used as a floating output, which is eventually fixed and correct The variable o i of every processor P i is used for recomputing the output of the algorithm 1 1 1 1 1 1 1 1 i : I i = 0 i : O i = 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0 0 1 1 1 1 1 1 1 0 i : O i = 0 0 0 0 0 0 0 0 0

43. Chapter 2 - Definitions, Techniques and Paradigms 2-43 2.1 Definitions of Computational Model 2.2 Self-Stabilization Requirements 2.3 Complexity Measures 2.4 Randomized Self-Stabilization 2.5 Example: Spanning-Tree Construction 2.6 Example: Mutual Exclusion 2.7 Fair Composition of Self-Stabilization Algorithms 2.8 Recomputation of Floating Output 2.9 Proof Techniques 2.10 Pseudo-Self-Stabilization Chapter 2: roadmap

44. Chapter 2 - Definitions, Techniques and Paradigms 2-44 Used for proving convergence Can be used to estimate the number of steps required to reach a safe configuration Variant Function step c c 1 c 2 c 3 step c safe step steps |VF(c)| |VF(c 1 )| |VF(c 2 )| |VF(c 3 )| |VF( c safe )| bound

45. Chapter 2 - Definitions, Techniques and Paradigms 2-45 Program for P i : 01 do forever 02 if pointer i = null and ( P j N(i) | pointer j = i ) then 03 pointer i = j 04 if pointer i = null and ( P j N(i) | pointer j i ) and 05 ( P j N(i) | pointer j = null ) then 06 pointer i = j 07 if pointer i = j and pointer j = k and k i then 08 pointer i = null 09 od Every processor P i tries to find a matching neighbor P j Variant Function - Example: self stabilizing Maximal Matching

46. Chapter 2 - Definitions, Techniques and Paradigms 2-46 Maximal Matching Application RUN RUN

47. Chapter 2 - Definitions, Techniques and Paradigms 2-47 The algorithm should reach a configuration in which pointer i = j implies that pointer j =i We will assume the existence of a central daemon The set of legal executions MM for the maximal matching task includes every execution in which the values of the pointers of all the processors are fixed and form a maximal matching Variant Function - Example: self stabilizing Maximal Matching

48. Chapter 2 - Definitions, Techniques and Paradigms 2-48 Variant Function - Example: self stabilizing Maximal Matching- definitions Program for P i : 01 do forever 02 if pointer i = null and ( P j N(i) | pointer j = i ) then 03 pointer i = j 04 if pointer i = null and ( P j N(i) | pointer j i ) and 05 ( P j N(i) | pointer j = null ) then 06 pointer i = j 07 if pointer i = j and pointer j = k and k i then 08 pointer i = null 09 od matched waiting free chaining single

49. Chapter 2 - Definitions, Techniques and Paradigms 2-49 The variant function VF(c) returns a vector (m+s,w,f,c) m - matched, s single, w waiting, f free, c - chaining Values of VF are compared lexicographically VF(c) = (n,0,0,0) c is a safe configuration with relation to MM and to our algorithm Once a system reaches a safe configuration, no processor changes the value of its pointer Variant Function - Example: self stabilizing Maximal Matching- proving correctness

50. Chapter 2 - Definitions, Techniques and Paradigms 2-50 In every non-safe configuration, there exists at least one processor that can change the value of its pointer Every change of a pointer-value increases the value of VF The number of such pointer-value changes is bounded by the number of all possible vector values. The first three elements of the vector (m+s,w,f,c) imply the value of c, thus there at most O(n 3 ) changes. Variant Function - Example: self stabilizing Maximal Matching- proving correctness

51. Chapter 2 - Definitions, Techniques and Paradigms 2-51 Convergence Stairs c j+1 c l A 1 A 2 ..... A k c l+1 c i c m c m+1 c safe c 1 c 2 c j A i predicate for every 1 i k, A i+1 is a refinement of A i

52. Chapter 2 - Definitions, Techniques and Paradigms 2-52 01 do forever 02 candidate,distance = ID ( i ) , 0 03 forall P j N ( i ) do 04 begin 05 leader i [ j ] ,dis i [ j ] := read leader j , dis j 06 if ( dis i [ j ] N ) and (( leader i [ j ] candidate ) or 07 (( leader i [ j ] = candidate ) and ( dis i [ j ] distance ))) then 08 candidate,distance := leader i [ j ] ,dis i [ j ] + 1 09 end 10 write leader i ,dis i := candidate,distance 11 od Convergence Stairs - Example: Leader election in a General Communication Network Program for Pi, each processor reads its neighbors leader and chooses the candidate with the lowest value :

53. Chapter 2 - Definitions, Techniques and Paradigms 2-53 We assume that every processor has a unique identifier in the range 1 to N The leader election task is to inform every processor of the identifier of a single processor in the system, this single processor is the leader Floating identifier - an identifier that appears in the initial configuration, when no processor in the system with this identifier appears in the system Convergence Stairs - Example: Leader election in a General Communication Networks

54. Chapter 2 - Definitions, Techniques and Paradigms 2-54 We will use 2 convergence stairs : l A 1 - no floating identifiers exists l A 2 (for a safe configuration) every processor chooses the minimal identifier of a processor in the system as the identifier of the leader To show that A 1 holds, we argue that, if a floating identifier exists, then during O( ) rounds, the minimal distance of a floating identifier increases Convergence Stairs - Example: Leader election, proving correctness

55. Chapter 2 - Definitions, Techniques and Paradigms 2-55 After the first stair only the correct ids exist, so the minimal can be chosen From that point, every fair execution that starts from any arbitrary configuration reaches the safe configuration Notice : if A 1 wasnt true, we couldnt prove the correctness Convergence Stairs - Example: Leader election, proving correctness ...

56. Chapter 2 - Definitions, Techniques and Paradigms 2-56 Purpose : proving the upper bounds of the time complexity of randomized distributed algorithms by probability calculations Using t he sl-game method . It tries to avoid considering every possible outcome of the randomized function used by the randomized algorithm Scheduler-Luck Game

57. Chapter 2 - Definitions, Techniques and Paradigms 2-57 The sl-game Given a randomized algorithm AL, we define a game between 2 players, scheduler and luck luck scheduler

58. Chapter 2 - Definitions, Techniques and Paradigms 2-58 Lucks strategy is used to show that the algorithm stabilizes Some definitions : cp = f i=1 p i f is # of lucks intervenes p i - probability of the ith intervention l luck should have a (cp,r)-strategy to win the game If luck has a (cp,r)-strategy,then AL reaches a safe configuration within, at most, r/cp expected number of rounds (Theorem 2.4) The sl-game(2)

59. Chapter 2 - Definitions, Techniques and Paradigms 2-59 Program for P i : 01 do forever 02 forall P j N ( i ) do 03 l i [ j ] = read ( leader j ) 04 if ( leader j = 0 and { j i | l i [ j ] = 0}) or 05 ( leader i = 1 and { j i | l i [ j ] = 1}) then 06 write leader i := random ({0,1}) 07 end The next algorithm works in complete graph systems, communication via shared memory SL-Game, Example: Self Stabilizing Leader election in Complete Graphs

60. Chapter 2 - Definitions, Techniques and Paradigms 2-60 Random Leader election in Complete Graphs RUN RUN

61. Chapter 2 - Definitions, Techniques and Paradigms 2-61 Task LE - the set of executions in which there exists a single fixed leader throughout the execution A configuration is safe if it satisfies the following: for exactly one processor, say P i , leader i = 1 and j i l i [ j ] = 0 for every other processor P j P i leader j = 0 and l j [ i ] = 1 In any fair execution E that starts with a safe configuration, P i is a single leader and thus E LE SL-Game, Example: Self Stabilizing Leader election in Complete Graphs

62. Chapter 2 - Definitions, Techniques and Paradigms 2-62 The algorithm stabilizes within 2 O(n) expected number of rounds (Lemma 2.6) l using theorem 2.4 we will show that the number of round is expected to be 2n2 n l we present an (1/2 n , 2n)-strategy for luck to win the sl-game Lucks strategy is as follows: whenever some processor P i tosses a coin, luck intervenes; if for all j i, leader j = 0, then luck fixes the coin toss to be 1; otherwise, it fixes the coin toss to be 0 SL-Game, Example: Self Stabilizing Leader election in Complete Graphs - proof

63. Chapter 2 - Definitions, Techniques and Paradigms 2-63 The algorithm is not self-stabilizing under fine- atomicity (Lemma 2.7) l By presenting a winning strategy for the scheduler that ensures that the system never stabilizes l Starting with all leader registers holding 1, the scheduler will persistently activate each processor until it chooses 0 and before it writes down. Then it lets them write. Analogously, scheduler forces to choose them 1. SL-Game, Example: Self Stabilizing Leader election in Complete Graphs - proof...

64. Chapter 2 - Definitions, Techniques and Paradigms 2-64 Purpose : proving memory lower bounds silent self-stabilizing algorithm - self-stabilizing algorithm in which the communication between the processors is fixed from some point of the execution The technique can be applied to silent self- stabilizing algorithms The idea : using a configuration c 0 (safe configuration) and construct a non-safe configuration c 1 in which every processor has the same neighborhood and therefore cannot distinguish c 0 from c 1 Neighborhood Resemblance

65. Chapter 2 - Definitions, Techniques and Paradigms 2-65 01 Root: do forever 02 for m := 1 to do write r im := 0,0 03 od 04 Other: do forever 05 for m := 1 to do write lr mi := read ( r mi ) 06 FirstFound := false 07 dist := 1 + min lr mi . dis 1 m 08 for m := 1 to 09 do 10 if not FirstFound and lr mi . dis = dist -1 11 write r im := dist, 1 12 FirstFound := true 13 else 14 write r im := 0, dist 15 od 16 od Reminder Spanning-Tree Algorithm for Pi 0 1 3 2 1 1 2 2

66. Chapter 2 - Definitions, Techniques and Paradigms 2-66 Neighborhood Resemblance - Example: Spanning-Tree Construction We will show that implementing the distance field requires (log d) bits in every communication register, where d is the diameter of the system Note - the Spanning-Tree Construction is indeed a silent self-stabilizing algorithm

67. Chapter 2 - Definitions, Techniques and Paradigms 2-67 a k e k b k a i b i Non-tree without special processor P 2 P 1 a i Q 1 b i e i Q 2 e j b i a i a k e k b k Tree Graph a k a k b k b k Non-tree with special processor Neighborhood Resemblance, Example: Spanning Tree Construction

68. Chapter 2 - Definitions, Techniques and Paradigms 2-68 2.1 Definitions of Computational Model 2.2 Self-Stabilization Requirements 2.3 Complexity Measures 2.4 Randomized Self-Stabilization 2.5 Example: Spanning-Tree Construction 2.6 Example: Mutual Exclusion 2.7 Fair Composition of Self-Stabilization Algorithms 2.8 Recomputation of Floating Output 2.9 Proof Techniques 2.10 Pseudo-Self-Stabilization Chapter 2: roadmap

69. Chapter 2 - Definitions, Techniques and Paradigms 2-69 What is Pseudo-Self-Stabilization ? The algorithm exhibits a legal behavior; but may deviate from this legal behavior a finite number of times step step step step step step c 2 safe c 1 safe c k safe c c i c c c m c l c t safe c safe c safe step step step c i c safe c safe c l safe

70. Chapter 2 - Definitions, Techniques and Paradigms 2-70 An Abstract Task An abstract task - variables and restrictions on their values The token passing abstract task AT for a system of 2 processors; Sender (S) and Receiver (R). S and R have boolean variable token S and token R Given E = (c 1 ,a 1 ,c 2 ,a 2 ,) one may consider only the values of token S and token R in every configuration c i to check whether the token-passing task is achieved

71. Chapter 2 - Definitions, Techniques and Paradigms 2-71 Pseudo-self-Stabilization Denote : l c i |tkns the value of the boolean variables (token S , token R ) in c i l E|tkns as (c 1 |tkns, c 2 |tkns, c 3 |tkns, ) We can define AT by E|tkns as follows: there is no c i |tkns for which token S =token R =true It is impossible to define a safe configuration in terms of c i |tkns, since we ignore the state variables of R/S

72. Chapter 2 - Definitions, Techniques and Paradigms 2-72 Pseudo-Self-Stabilization The system is not in a safe configuration, and there is no time bound for reaching a safe configuration Only after a message is lost does the system reach the safe configuration token R = true token S = true token R = true token S = false token R = false token S = false token R = false token S = false token R = false token S = true token R = true token S = false token R = false token S = false token R = false token S = false token R = false token S = true Illegal legal legal

73. Chapter 2 - Definitions, Techniques and Paradigms 2-73 Pseudo-Self-Stabilization, The Alternating Bit Algorithm A data link algorithm used for message transfer over a communication link Messages can be lost, since the common communication link is unreliable The algorithm uses retransmission of messages to cope with message loss frame distinguishes the higher level messages, from the messages that are actually sent (between S and R)

74. Chapter 2 - Definitions, Techniques and Paradigms 2-74 Pseudo-Self-Stabilization, The Data Link Algorithm The task of delivering a message is sophisticated, and may cause message corruption or even loss The layers involved Physical Layer Data link Layer Tail Packet Frame Network Layer Head Physical Layer Data link Layer Tail Packet Frame Network Layer Head

75. Chapter 2 - Definitions, Techniques and Paradigms 2-75 Pseudo-Self-Stabilization, The Data Link Algorithm S R . . m 3 m 2 m 1 S R . . m 3 m 2 m 1 fetch S R . . m 3 m 2 m 1 f 2 m 1 send S R . . m 3 m 2 m 1 m 1 deliver S R . . m 3 m 2 m 1 f 1 receive S R . . m 3 m 2 m 1 f 1 send The flow of a message:

76. Chapter 2 - Definitions, Techniques and Paradigms 2-76 Pseudo-Self-Stabilization, Back to The Alternating Bit Algorithm The abstract task of the algorithm: S has an infinite queue of input messages (im 1 ,im 2 ,) that should be transferred to the receiver in the same order without duplications, reordering or omissions. R has an output queue of messages (om 1 ,om 2 ,). The sequence of messages in the output queue should always be the prefix of the sequence of messages in the input queue

77. Chapter 2 - Definitions, Techniques and Paradigms 2-77 The alternating bit algorithm - Sender 01 initialization 02 begin 03 i := 1 04 bit s := 0 05 send ( bit s , im i ) (* im i is fetched*) 06 end (*end initialization*) 07 upon a timeout 08 send ( bit s , im i ) 09 upon frame arrival 10 begin 11 receive ( FrameBit ) 12 if FrameBit = bit s then (*acknowledge arrives*) 13 begin 14 bit s := ( bit s + 1) mod 2 15 i := i + 1 16 end 17 send ( bit s , im i ) (* im i is fetched*) 18 end

78. Chapter 2 - Definitions, Techniques and Paradigms 2-78 The alternating bit algorithm - Receiver 01 initialization 02 begin 03 j := 1 04 bit r := 1 05 end (*end initialization*) 06 upon frame arrival 07 begin 08 receive ( FrameBit , msg ) 09 if FrameBit bit r then (*a new message arrived*) 10 begin 11 bit r := FrameBit 12 j := j + 1 13 om j := msg (* om j is delivered*) 14 end 15 send ( bit r ) 16 end

79. Chapter 2 - Definitions, Techniques and Paradigms 2-79 Pseudo-Self-Stabilization, The Alternating Bit Algorithm Denote L = bit s ,q s,r ,bit r ,q r,s , the value of the of this label sequence is in [0*1*] or [1*0*] where q s,r and q r,s are the queue messages in transit on the link from S to R and from R to S respectively We say that a single border between the labels of value 0 and the labels of value 1 slides from the sender to the receiver and back to the sender Once a safe configuration is reached, there is at most one border in L, where a border is two consecutive but different labels

80. Chapter 2 - Definitions, Techniques and Paradigms 2-80 The Alternating Bit Algorithm, borders sample l Suppose we have two borders l If frame m 2 gets lost, receiver will have no knowledge about it X S R < m 3 ,0 >..< m 2 ,1 > .. < m 1 ,0 > bit S = 0 bit R = 1 < m 3 ,0 > < m 1 ,0 >

81. Chapter 2 - Definitions, Techniques and Paradigms 2-81 Pseudo-Self-Stabilization, The Alternating Bit Algorithm Denote L(c i ) - the sequence L of the configuration c i A loaded configuration c i is a configuration in which the first and last values in L(c i ) are equal

82. Chapter 2 - Definitions, Techniques and Paradigms 2-82 Pseudo-Self-Stabilization, The Alternating Bit Algorithm The algorithm is pseudo self-stabilizing for the data-link task , guaranteeing that the number of messages that are lost during the infinite execution is bounded, and the performance between any such two losses is according to the abstract task of the data-link