Towards a paradigm for robust distributed algorithms and data structures

There is a wealth of literature on distributed algorithms and data structures. Standard models used in the research community are synchronous or asynchronous shared memory or network models. The shared memory model is basically a generalization of the von Neumann model from one processing unit to multiple processing units or processes acting on a single, linear addressable memory. In the network model, there is no shared memory. Every processing unit has its own, private memory, and the processing units are connected by a network of (usually) bidirectional communication links that allow the processing units to exchange messages. The set of processing units is usually considered to be fixed though processing units may fail and recover according to some stochastic or adversarial model.

With the rise of very large distributed systems such as peer-to-peer systems, these models are not appropriate any more. For example, the set of processing units can be highly dynamic and there may not be any mutual trust relationships between the units. This creates fundamental problems, such as keeping the (honest) units in a single connected component, that the previous models cannot address in their basic form. We show how to extend the network model so that we have a model that is powerful enough to design algorithms and data structures that are provably robust even against massive adversarial attacks. This model even allows to design strategies capable of addressing modern threats such as denial-of-service attacks and phishing that appear to lie outside the algorithm design.

After presenting the new model and the motivation behind it, I will illustrate in my talk how to apply it to various relevant problems for distributed systems.

Adaptive Routing with Methods from Evolutionary Game Theory

Speaker: Prof. Dr. Berthold Vöcking

Network congestion is one of the major problems in large communication networks like the Internet. Current Internet technology based on the TCP protocol uses fixed end-to-end routes that not adapt to the traffic pattern. Congestion is avoided only by adjusting injection rates. A more flexible approach uses load-adaptive rerouting policies that reconsider routing strategies from time to time depending on the observed latencies. We present and discuss such policies that avoid congestion by balancing traffic using methods inspired by evolutionary game theory.

Parallel Computation of Three Dimensional Flows on Unstructured Grids

Speaker: Dr. Stephan Blazy

In this talk numerical results of different benchmark problems for the three dimensional Navier-Stokes equations are presented. The benchmark problems prescribe the flow around obstacles and the flow through a system of channels. Furthermore, chemical species are added in case of the channel flow. This comprises additionally a transport problem for the species. In all cases the behaviour of different solution techniques using adaptive finite element methods are studied. Moreover, computed meanvalues like lift and drag coefficient, pressure decay and species distribution are discussed.

The numerical schemes for solving the three dimensional Navier-Stokes equations and the species equations using the parallel adaptive finite element framework padfem2 are illustrated. Finally, some efficiency results and the comparison of the numerical computations with existing reference values are shown.