DOC PREVIEW
U of I CS 425 - Self-Stabilization

This preview shows page 1-2-16-17-18-33-34 out of 34 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 34 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 34 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 34 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 34 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 34 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 34 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 34 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 34 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Computer Science 425/ECE 428/CSE 424 Distributed Systems (Fall 2009)AcknowledgementAdministrative Plan for TodayMotivationSelf-stabilizationConfigurations of Distributed SystemsSelf-stabilizing systemsReasons for illegal configurationsSelf-stabilizing systemsExample1: Stabilizing mutual exclusion in unidirectional ringDijkstra’s stabilizing mutual exclusionExample executionExample stabilizing execution Why does it work?Why does it work?Why does it work?Why does it work?Putting it all together P2P Systems - Chord SearchStabilization Protocol in ChordSearch under peer failuresSearch under peer failuresSearch under peer failures (2)Search under peer failures (2)New peers joiningNew peers joining (2)Chord Stabilization ProtocolStabilizing graph coloringGraph coloring problem Simple coloring algorithm Correctness of simple coloring (SC)Properties of SCSummaryComputer Science 425/ECE 428/CSE 424 Distributed Systems(Fall 2009)Lecture 20Self-StabilizationReading: Chapter from Prof. Gosh’s book Klara NahrstedtAcknowledgement• The slides during this semester are based on ideas and material from the following sources: – Slides prepared by Professors M. Harandi, J. Hou, I. Gupta, N. Vaidya, Y-Ch. Hu, S. Mitra. – Slides from Professor S. Gosh’s course at University o Iowa.Administrative • MP2 posted October 5, 2009, on the course website, – Deadline November 6 (Friday)– Demonstration, 4-6pm, 11/6/2009 –Tutorial for MP2 planned for October 28 evening if students send questions to TA by October 25. Send requests what you would like to hear in the tutorial.Plan for Today• Motivation for Self-Stabilization• Self-Stabilization Concepts/Definitions• Dijkstra’s stabilization of mutual exclusion in unidirectional ring• Chord’s stabilization protocol • Stabilizing graph coloringMotivation• As the number of computing elements increase in distributed systems failures become more common • Fault tolerance (FT) should be automatic, without external intervention • two kinds of fault tolerance– masking: application layer does not see faults, e.g., redundancy and replication– non-masking: system deviates, deviation is detected and then corrected: e.g., feedback, roll back and recovery• self-stabilization is a general technique for non-maskingFT distributed systemsSelf-stabilization• Technique for spontaneous healing• Guarantees eventual safety following failures•Feasibility demonstrated by Dijkstra (CACM `74)E. DijkstraConfigurations of Distributed Systems• Two classes of configurations (or behaviors)– Legitimate configuration » In non-reactive system is represented by invariant over global state of the system • Example: legal state of network routing: no cycle in a route between pair of nodes» in reactive system is determined by a state predicate and by behavior. • Example: in token ring, legitimate config. When (i) there is exactly one token in the network; (ii) in infinite behavior of the system, each process receives the token infinitely often.– Illegitimate configuration » Example: if process grasps token, but does not release it, then the first criterion of the legitimate config. Is true, but the second criterion is not satisfied, hence configuration becomes illegitimate.Self-stabilizing systems• recover from any initial configuration to a legitimate configuration in a bounded number of steps, as long as the codes are not corruptedAssumption:• failures affect the state (and data) but not the program since program executes the self-stabilization;• Such systems can be deployed ad hoc, and are guaranteed to function properly in bounded time• Guarantees fault tolerance when the mean time between failures (MTBF) >> mean time to recovery (MTTR)– Stabilization provides solution when failures are infrequent and temporary malfunctions are acceptableReasons for illegal configurations• Transient failures perturb the global state. The ability to spontaneously recover from any initial state implies that no initialization is ever required.– Example: disappearance of the only circulating token in token ring; data corruption due to radio interference or power supply variations;• Topology changes: topology of network changes at run time when node crashes or new node is added to the system– Example: peer-to-peer networks and their churn rate (dynamic networks) – see stabilization protocol in Chord• Environmental changes: environment of a program may change without notice– Example: traffic lights in city may run different programs depending on volume and distribution of traffic. If system runs “early morning program” in the afternoon rush hours, we have illegal configuration.Self-stabilizing systems• Self-stabilizing systems exhibits non-masking fault-tolerance• They satisfy the following two criteria–convergenceregardless of initiate state, the system eventually returns to legal configuration–closure once in legal configuration, system continues in legal configuration unless failure or perturbation corrupts data memory faultL: Legitimate configurationNon L: Illegitimate configruationExample1: Stabilizing mutual exclusion in unidirectional ringconsider a unidirectional ring of processes. Legal configuration = exactly one token in the ring desired “normal” behavior: single token circulates in the ringOnly the node that holds the token can access the critical region!!!Dijkstra’s stabilizing mutual exclusionExample executionExample stabilizing executionWhy does it work?1. at any configuration, at least one process can make a move (has token)– suppose p1,…,pN-1cannot make a move– then x[N-1] = x[N-2] = … x[0]– then p0 can make a moveWhy does it work?1. at any configuration, at least one process can make a move (has token)2. set of legal configurations is closed under all movesWhy does it work?1. at any configuration, at least one process can make a move (has token)2. set of legal configurations is closed under all moves3. total number of possible moves from (successive configurations) never increases– any move by pieither enables a move for pi+1 or none at allWhy does it work?1. at any configuration, at least one process can make a move (has token)2. set of legal configurations is closed under all moves3. total number of possible moves from (successive configurations) never increases4. all illegal configuration C converges to a legal configuration in a finite number of moves– there must be a


View Full Document

U of I CS 425 - Self-Stabilization

Documents in this Course
Lecture 8

Lecture 8

23 pages

TIPS

TIPS

3 pages

The Grid

The Grid

41 pages

Lecture 4

Lecture 4

27 pages

Lecture 4

Lecture 4

20 pages

The Grid

The Grid

41 pages

LECTURE 5

LECTURE 5

25 pages

Multicast

Multicast

23 pages

LECTURE

LECTURE

34 pages

Load more
Download Self-Stabilization
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Self-Stabilization and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Self-Stabilization 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?