Probabilistic versus Deterministic Techniques for Shared Memory Computation (12w5122)

Objectives

One of the main challenges faced by today's computing is to enable algorithms to fully exploit the parallelism provided by hardware. Shared memory algorithms need to cope with the inherent asynchrony and faulty process behavior in parallel systems. In the light of recent technological developments, most conspicuously multi-core processors, distributed shared memory algorithms have gained huge importance for every-day and high-performance computing. This workshop will bring together international experts, promising junior researchers, and some exceptional graduate students and postdocs, to exchange ideas on how probabilistic methods can be applied to advance the research on the complexity of fundamental algorithmic problems in shared memory systems. The discussions between experts on the theory of distributed computation and experts on probabilistic methods from other computing domains will result in identifying new and enhanced techniques for exploiting randomization in multiprocessor shared memory systems. We will also invite some researchers with systems background, whose expertise will help identify problems and approaches that are relevant for practical applications.

Below we list some of the goals of the workshop.

(1) Identify and promote techniques to prove upper and lower bounds for randomized computation. Devise design paradigms for randomized distributed algorithms. Understand the applicability and limits of Yao's Min-Max principle. In sequential computing, several standard techniques, such as tail bounds or Yao's Min-Max principle are used frequently for algorithm analysis. Are there techniques that are particularly applicable to distributed computing?

(2) Gain insights into the power and limitations of randomized algorithms compared to deterministic algorithms. For which types of problems or models can we hope to be able to gain speedups using randomization?

(3) Explore how changes in assumptions effect the complexity of probabilistic solutions to problems. Example of model assumption that can have an impact on the complexity of problems are,

* details of the shared memory model (cache coherence or distributed shared memory model; fixed or variable number of processes).
* the adversary model, which describes how the scheduling is influenced by random coin flips,
* liveness requirements (e.g., wait free, non-blocking, or obstruction free)
* details of the complexity measures (step complexity, remote memory accesses, space)

(4) Tackle the analysis of the randomized complexity of core shared-memory problems. For standard problems such as mutual exclusion or consensus, randomized algorithms exist, but often the exact complexity is still unknown. For other problems no randomized algorithms have been developed, yet. Of particular interest is the efficient implementation of strong primitives from weaker ones by using randomization.