Title: Self-stabilizing distributed data structures (slides in PDF)
Christian Scheideler (University of Paderborn, Germany)
http://www.cs.uni-paderborn.de/fachgebiete/fg-ti/personen/scheideler.html
Abstract: In this talk I will discuss new models and approaches for scalable distributed data structures that are not just efficient but also robust so that they can be used for large distributed systems connected via the Internet. While many scalable distributed data structures have already been proposed, in particular in the context of peer-to-peer systems, the models and approaches used for them in the theory literature are often rather simple: the nodes are assumed to operate in a synchronous manner (to ensure timely executions of operations) and the pseudo-code presented for the operations can often just handle the isolated execution of these operations.
One may think about using the techniques known from classical concurrent data structures to handle concurrency, but the problem is different here since illegal states are unavoidable in large distributed systems. Hence, besides preventing illegal states, it is also important to recover from illegal states. A useful concept in this context is self-stabilization. Since classical self-stabilization techniques do not work well for large distributed data structures (as they should not rely on a shared memory layer), I will explore new ways of using this concept in my talk.
