Date: Fri 19 Jun
Time: 11.00
Place: room 214

Speaker: Prof. Ajoy Datta (Univ. of Nevada at Las Vegas), Dr. Synnove Kekkonen (Univ. Paris-Sud, Orsay)
Title: Self-Stabilization and Fault-Tolerance
Reference: Massimo Ancona

Abstract. (Ajoy Datta) We propose a self-stabilizing PIF scheme on a rooted tree network. We call this scheme the Propagation of information with Feedback and Cleaning (PFC). The PFC scheme has extremely small state requirement---only 3 states per processor (except the root and the leaf processors, which have only 2 states). We show that the state requirement is optimal for the PIF algorithms on the tree networks. The proposed PFC algorithm stabilizes in h-1 steps.

(Synnove Kekkonen) Failures that affect the correct functioning of a distributed system can be classified, based on their effect, into "process failures" (causing code corruption) and "systemic failures" (causing data corruption). Given this classification, we define a formal model for representing the computations of a distributed protocol in the presence of process and/or systemic failures. We then design several distributed protocols and use this model for verifying their failure resilience properties. In the first part of the thesis, we focus on "self-stabilizing" protocols that restore automatically the correct system behavior after a systemic failure. Our two self-stabilizing protocols (the first probabilistic, the second deterministic) illustrate this new programming paradigm. The second part of the thesis is on "simultaneously k-fault-tolerant and self-stabilizing" (k-ftss) protocols that, despite the presence of up to k failed processes and in the absence of further systemic failures, guarantee that the non-faulty processes (i) return to correct behavior from any (arbitrarily corrupted) state and (ii) then continue their correct behavior. We first prove an important impossibility result on k-ftss protocols; this result identifies a condition for deciding whether a problem is k-ftss-solvable or not. Second, we design and verify deterministic and probabilistic k-ftss protocols for some of those problems that are k-ftss-solvable. Last, we explore hypotheses that allow a k-ftss solution for a problem that is k-ftss-unsolvable.