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

The Banff International Research Station will host the "Probabilistic versus Deterministic Techniques for Shared Memory Computation" workshop from February 5th to February 10th, 2012.

Today's commodity desktop computers contain two to eight processors; high-performance computers have hundreds. In a few years "multi-core" desktops will also have hundreds of processing units on a single board. Our knowledge of how to most effectively exploit this parallelism lags far behind our knowledge of how to build the hardware. Programs for these machines are very difficult to design because they need to be able to cope with asynchronous and faulty behavior of hardware, and the increasing elaborate shared memory interconnection designs.



Many fundamental problems in these settings cannot be solved efficiently (or at all) by conventional deterministic algorithms. Probabilistic algorithms, which allow computers to make random choices, have proved extremely useful to overcome these limitations. Sometimes probabilistic algorithms provide the only solution to a problem; sometimes they are more efficient; sometimes they are simply easier to implement. The workshop focuses on studying the power and limitations of probabilistic algorithms. The goals are to identify situations in which probabilistic methods are useful and when they are not. We aim to develop new, more efficient solutions by exploiting randomization and also to mathematically prove that certain problems cannot be solved efficiently, even if random decisions can be made.

The Banff International Research Station for Mathematical Innovation and Discovery (BIRS) is a collaborative Canada-US-Mexico venture that provides an environment for creative interaction as well as the exchange of ideas, knowledge, and methods within the Mathematical Sciences, with related disciplines and with industry. The research station is located at The Banff Centre in Alberta and is supported by Canada's Natural Science and Engineering Research Council (NSERC), the U.S. National Science Foundation (NSF), Alberta's Advanced Education and Technology, and Mexico's Consejo Nacional de Ciencia y Tecnología (CONACYT).