This is a past event.

Think Stabilizing
A Workshop for STEM Researchers

Organizers: Alex Klinkhamer and Ali Ebnenasir

3rd workshop in a series of 3.

The goal of this workshop is to enhance awareness of the notion of Self-Stabilization amongst researchers in Science, Technology, Engineering and Math (STEM). A self-stabilizing system has two properties, namely closure and convergence. Convergence requires that starting from any state/configuration system executions will reach a set of legitimate states from where the system meets its specifications. Starting from a legitimate state, system executions remain in legitimate states, i.e., closure. A self-stabilizing algorithm for a problem (e.g., sorting) must satisfy closure and convergence.  

The necessary background required for attendance includes basic Discrete Math and some experience of programming, preferably parallel programming. The objective of this workshop is to familiarize the attendees with the challenges and opportunities of distributed problem solving and decision making in a self-stabilizing fashion, hence the title Think Self-Stabilizing. This novel way of thinking will enable researchers to develop algorithms that are more robust. That is, if such self-stabilizing algorithms are implemented as software, then the resulting program will be highly dependable and will provide more assurance about its correctness.

This workshop will be presented in the context of three one-hour sessions. The outline of the workshop will cover the challenges of today’s distributed systems due to their heterogeneity, huge scale and dynamism (e.g., mobility). These features of modern distributed systems result in disturbing events (e.g., loss of coordination and bad initialization) that perturb the state/configuration of these systems. As such, the focus of this workshop will be on the problem of designing self-stabilizing systems/algorithms. Self-stabilizing systems autonomously recover to legitimate behaviors without human intervention, which is a required property in large-scale networks (e.g., the Internet).  Self-stabilization has significant applications in Computer Science (e.g., robust network protocols, parallel and distributed programs), Math (e.g., game theory), Economics (e.g., Nash equilibrium) and Multi-Agent systems (e.g., Unmanned Vehicles). Most existing methods are problem-specific and are based on a method of manual design and after-the-fact verification. The verification step could be manual or mechanical, both being extremely difficult and costly due to (i) constraints of distribution such as limited knowledge of each component about the global state of the system; (ii) the requirement of global recovery using local actions of system components without any central point of administration, and (iii) the necessity of convergence from any state.

In this workshop, we present a novel two-step method for automatic generation of self-stabilizing algorithms with the help of the software tools (http://asd.cs.mtu.edu/projects/protocon/) we have developed at the Software Design Group at Michigan Tech (http://asd.cs.mtu.edu). We will present a new way of thinking for problem solving, where the attendees will get a hands-on experience in the design of self-stabilizing algorithms in the context of fun activities such as a card game.  After this workshop, the attendees will gain a clear understanding of the following subjects:

•    Challenges in modern distributed systems;
•    The concept of self-stabilization;
•    Complexities of designing and verifying self-stabilizing algorithms;
•    Novel methods and tools for automated design of self-stabilizing algorithms, and
•    Classic self-stabilizing protocols such as agreement and leader election.