Sunsets, Souls, and Senses: Exploring Natural Phenomena
Dive into the intriguing world of natural occurrences depicted in cartoons and reflective notes. Explore the boundaries of science and the study of the natural world, distinguishing between the measurable and the supernatural. See how observation through senses and scientific instruments plays a vital role in understanding the universe around us.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Self-Stabilizing Systems Seminar of Distributed systems University of L Aquila Date:19/01/2016 Giuseppe Tomei Giuseppe Di Lena
Topics Introductionto Self-stabilizingSystems Dijkstra s approch: K-state machines (K>N) Four-state machines Three-state machines MutualExclusion with K-State machines
Introduction The synchronization task of processes in a distributed-system can be viewed as keeping the system in a legitimate state. If there is a shared memory, every process can access it by mutex.In this scenario the current state of system is stored in the shared memory . If there isn t a shared memory, then every process must have some distributed variables and each process can only exchange information with its neighbors.
Introduction In our presentation we discuss the second case, in particular we consider ring topology which is a connected graph in which the majority of the edge are missing. What s the problem? Each process only knows the state of its neighbors; The behavior of a process is influenced only by a part of the total system state .
Assumptions In each node there is a finite state machine Each machine has one or more privileges Privilege is defined such as boolean function, where its input is the state of the machine and the states of its neighbors. The result of the function is True if the privilege is present, false otherwise There is a central daemon that can select one of the present privileges We don t know how the daemon works
How the system works The machine that has the selected privilege will make its move After its move, the machine will be in a new state, which it depends on its old state and the states of its neighbors After completion of the move the daemon will select a new privilege
Legitimate state What is a legitimate state ? The system is in a legitimate state when it satisfies the following properties: 1. In each legitimate state one or more privileges will be present; 2. In each legitimate state each possible move will bring the system again in a legitimate state ; 3. Each privilege must be present in at least one legitimate state 4. For any pair of legitimate states there exists a sequence of moves transferring the system from the one into the other
Self-stabilizing System Wecall the system self-stabilizing if and onlyif, regardless of the initial state and regardless of the privilege selected eachtime for the nextmove, at least oneprivilege will always be present and the system is guaranteed to find itself in a legitimate state after a finite numberof moves
Dijkstra assumptions We consider ? + 1 machines numbered from 0to ? in a ring topology We shall use for machine number ?: L: to refer to the state of its lefthand neighbor, machine nr. (? 1)???(? + 1); S:to refer to the state of itself, machine nr. ? R: to refer to the state of its righthand neighbor, machine nr. (? + 1)???(? + 1);
Dijkstra assumptions Machine number 0will also be called the bottom machine Machine number ? will also be called the top machine The legitimate state has exactly one privilege present Sintax: ifprivilege then corresponding move fi;
Solution with K-state machines (? > ?) Eachmachine state is represented by an integer value ?, where 0 ? < ? For eachmachine oneprivilege is defined: Code for the bottom machine : Code for the other machines:
Example for ? > ? Who has the privilege??? Bottom N = 4 p0 S = 2 S = 3 L R p1 p2 p4 K = 5 The demon chooses one p1 = L I choose p1 Now the only machine that has the privilege is p4 p4 S = 0 S = 2 p1 S = 1 S = 2 p4 = L Now the bottom machine has the privilege p3 S = 2 p2 S = 2 p0 = (S + 1)mod K And so on
Solution with 4-state machines Each machine state is represented by two booleans :?? and ???. For the bottom machine ??? = ???? by definition, for the top machine ??? = ????? by definition For each machine the privilege is defined: Code for the bottom machine: Code for the top machine: Code for the other machines:
Example 4-state machines bottom Who has the privilege??? p1 p2 p3 p4 p0 L R x = true up = true x = false The demon chooses p3 The demon can still choose p3 The demon chooses p1 Only p1 has the privilege now After the last execution of p1, p1.up = false and this unlock the bottom machine top p4 p1 x = false up = true up = false x = true x = true up = false See how it evolves p3 p2 x = false up = false up = true x = true x = true up = false Bottom: Top: Other:
Example 4-state machines bottom Who has the privilege??? p1 p2 p3 p4 p0 L R x = false The demon chooses p3 The demon can still choose p3 The demon chooses p1 Only p1 has the privilage now After the last execution of p1, p1.up = false and this unlock the bottom machine up = true top p4 p1 x = true up = false x = false up = true See how it evolves p3 p2 x = true up = false x = true up = false
Solution with 3-state machines Each state is represented by an integer value ?, where 0 ? < 3. For each machine the privilege is defined: Code for the bottom machine: Code for the top machine: Code for the other machines:
Example 3-state machines Who has the privilege??? p1 p2 p2.S = R Only p2 has the privilege now bottom p0 S = 1 L R The system is stabilized top I m back!!! I choose p2 p4 S = 2 p1 S = 1 See how it evolves p2 S = 2 S = 0 S = 1 p3 S = 0 S = 1 Bottom: Top: Other:
Example 3-state machines Who has the privilege??? p1 p2 p2.S = R Only p2 has the privilege now bottom p0 L R The system is stabilized top p4 p1 See how it evolves p2 p3
Mutual Exclusion with K-State machines
Introduction Now we present Dijkstra self-stabilizing algorithm for the mutual exclusion on a ring. The notation used in this example is : ? = number of processes ? = state of process ? = total number of states per machine ? = state of left neighbor ? = state of right neighbor ? = state of bottom machine
Assumptions A machine can enter in the critical section only if it has a privilege. The system is in a legal state if exactly one machine has a privilege The goal of the self-stabilizing algorithm is to determinate who has the privilege and how the privileges move in the network. There are ? machines numbered 0 ? 1 The state of any machine is determinated by its label from the set 0 ? 1 Remember the pseudocode: Code for the bottom machine : if (? = ?) then ? = (? + 1) ??? ? Code for the other machines: if (? ?) then ? = ?
Proof of correctness The system is in a legal state if exactly one machine has the privilege. It is easy to verify that (?0,?1 ?? 1) is legal if and only if either all ?? are equal or there exists ? < ? 1 such that all ?? with ? ? are equal to some value and all other ?? are equal to some other value In the first case the bottom machine has the privilege, in the second case the machine ?? + 1 has the privilege ????? ?: if if the the system system is is in a in a legal legal state, state, then then it it will will stay stay legal legal. .
Proof of correctness ????? ?: a sequence of moves in which the bottom machine does not move is at most ?(??) ?????: in the best case the number of moves is ?(1), obviously; Let s analyze the worst case: For the sake of semplicity we consider ? = ? bottom L R 0 In the first step we have N-1 moves ? 1 ? 2 ? 3 1 = ? 1 (? 2) 0 1 0 In the second step we have N-2 moves And so on for N 2 step where we have this situation at the ? 1 step the bottom get the privilege 2 1 0 ? 2 ? 3 ? 4 0 =?2 ? ? 1 2 N 2 ?(??) 2 So the bottom machine waits a finite number of moves ? 3 ? 4 ? 5 0 3 2 1 0
Proof of correctness ????? ?: Given any configuration of the ring, either: 1: no other machine has the same label as the bottom, or 2: there exist a label that is different from all machines. Furthermore, within a finite number of moves, (1) will be true ?????:We show that if (1) does not hold, then (2) is true. If there exist a machine that has the same label as that of bottom, then there are now ? 1 labels left to be distributed among ? 2 machines. Since ? ?, we get that there is some label which is not used. To show the second part, first note that if some label is missing from the network, then it can only be genereted by the bottom machine. (continue)
Proof of correctness Makeover, the bottom machine simply cycles among all labels. Since, from lemma(2), the bottom machine moves after some finite number of moves by normal machines, we get that the bottom machine will eventually get the missing label. ????? ?: If the system is in illegal state, then within O(??) moves it reaches a legal state Proof: It is easy to see that once the bottom machine gets the unique label, the system stabilizes in ?(?2) moves. (continue)
Proof of correctness The bottom machine can move at most ? times before it acquires the missing label. Machine 1 therefore can move at most ? + 1 times before the bottom acquires the label. Similarly, machine ? can move at most ? + ? times before the bottom gets the label. By adding up all the moves, we get ? + (? + 1) + + (? + ? 1) = ?(?2) moves
References [1] Self-Stabilizing System in Spite of Distributed Control, E.W. Dijkstra [2] cap 23, 82.130.102.95/lectures/ss06/distcomp/lecture/self_stabilization.pdf
