Towards a rigorous base for the design of distributed systems
Thim Strothmann
University of Paderborn, Germany
Thursday, October 30, 2014
12:30 p.m.
Brickyard (BYENG) 210, Tempe campus [map]
Abstract
In this talk Thim Strothmann will present recent results concerning the design of dynamic distributed systems. More precisely, we aim to create a rigorous base for peer-to-peer systems, which allows for a formal analysis of real-world phenomena. To achieve this goal, we first introduce four general primitives for peers, which not only leave the overlay network graph connected at all times, but are also provably universal to create any goal topology for the network.
Furthermore, we formally investigate one of the most fundamental problems of robust peer-to-peer systems: safe departure of nodes, i.e. nodes requesting to leave the peer-to-peer system are excluded from its overlay network without affecting the network connectivity. If the overlay is initially in a well-defined state, then various proposals have already been made on how to safely exclude nodes, but surprisingly, the problem had not been formally studied yet for the case when the overlay network may be in an arbitrary initial state. We propose self-stabilizing solutions for excluding leaving nodes. We study this problem in two variants: the Finite Departure Problem (FDP) and the Finite Sleep Problem (FSP).
In the FDP the leaving nodes have to irrevocably decide in finite time when it is safe to leave the network whereas in the FSP we just aim at excluding the leaving nodes from the network in finite time, but they may not be aware of the fact when they are ultimately excluded from the network. Not surprisingly, we can show that there is no self-stabilizing local-control protocol for the FDP. To enable a solution, we introduce oracles that give nodes non-local information about the network. For a oracle called ONESID, we can show that it is necessary and sufficient so solve the FDP.
On the other hand, we show that if we just want to solve the FSP problem, then no oracle is required to exclude the leaving nodes. This phenomenon is similar to what is known for other fundamental problems like the consensus problem: if we require the nodes to decide in finite time when a consensus has been reached, then there is no self-stabilizing local-control solution for it, but if we just aim at eventually reaching a consensus without the nodes being aware of it, there is a self-stabilizing solution.
This is joint work with Christian Scheideler and Andreas Koutsopoulos (U. of Paderborn), and Mikhail Nesterenko and Dianne Foreback (Kent State).
Bio
Thim Strothmann is a CS Ph.D. student under the supervision of professor Christian Scheideler at the University of Paderborn, Germany. He received his M.S. and B.S. degree from University of Paderborn. He is currently visiting ASU for two weeks, hosted by Andrea Richa, associate professor in the School of Computing, Informatics, and Decision Systems Engineering. His research interests are programmable matter, self-stabilizing distributed systems and algorithmic game theory.
CIDSE Invited Talk
Hosted by Professor Andrea Richa
