Christian Scheideler - TU München

Random Processes for Robust Distributed Systems

Abstract: In my talk I will show how to keep the members of a dynamic distributed system well-mixed even under adaptive adversarial behavior. First, I consider a simple pebble-shuffling scenario. There are n white pebbles (the honest members) and epsilon*n black pebbles (the adversarial members) for some constant epsilon<1. Initially, all of the white pebbles are laid down in a ring, and the adversary has all of the black pebbles in its bag. In each round, the adversary can look at the entire ring and can choose to add a black pebble to the ring (if its bag is not empty) or to take any black pebble from the ring and put it back into its bag. However, the adversary cannot place a black pebble into any position it likes. This is handled by a join strategy to be specified by the system. The goal is to find an oblivious join strategy, i.e. a strategy that cannot distinguish between the white and black pebbles in the ring and does not remember the join-leave history, that integrates the black pebbles into this ring (and may do some further rearrangements) so that for a polynomial number of rounds the adversary will not manage to include its black pebbles into the ring so that there is a sequence of Theta(log n) consecutive pebbles in which at least half of the pebbles are black. If this is achieved by the join strategy, it wins. Otherwise, the adversary wins. I present a very simple randomized join strategy, called k-rotation, that wins with high probability against any adversary as long as epsilon<1-2/k.

Afterwards, I consider white and black pebbles that are assigned to real numbers in the [0,1) interval. Here, the goal is to maintain two conditions:
- in any Theta((log n)/n) interval there are Theta(log n) pebbles
- in any Theta((log n)/n) interval the white pebbles are in the majority.
To maintain this property even under adaptive adversarial behavior, we propose a simple randomized join strategy called k-cuckoo rule. This strategy wins with high probability against any adversary as long as epsilon < 1-1/k.

The results of this talk are joint work with Baruch Awerbuch.

Colloquium - 16:00

Maike Buchin - FU Berlin

Computing the Frechet Distance between Simple Polygons

Abstract: The Frechet Distance is a similarity measure used in Shape Matching. It can be computed in polynomial time for polygonal curves but is NP-hard to compute for surfaces. In this talk we show how to compute it in polynomial time for simple polygons. This is joint work with Kevin Buchin and Carola Wenk.