Parallel and Distributed Algorithms

Summary

The second Dagstuhl Seminar on Parallel and Distributed Algorithms was organized by Richard Cole (Courant Institute), Ernst W. Mayr (Johann-Wolfgang Goethe-Universität Frankfurt), and Friedhelm Meyer auf der Heide (Universität Paderborn). This year, it brought together 30 participants from 7 countries, 10 of them came from overseas.

The 26 talks presented covered a wide range of topics including parallel data management and rearrangement on networks and PRAMS, both deterministic and randomized, computational geometry, parallel complexity theory, and synchronous and asynchronous computation.

The log-star revolution brought about efficient randomized PRAM algorithms e. g. for maintaining dictionaries and padded sorting. Also an overview of the ideas and techniques of such algorithms was given. Two talks provided important tools for the analysis of randomized and probabilistic algorithms.

Algorithms for integer sorting, sorting on two- and high-dimensional meshes, verification of optimal sorting networks and bounds of the performance of bus-networks demonstrate the never ending youth of parallel sorting.

Interesting algorithms for the construction of trapezoidal diagrams and reporting of intersection points of curves were presented as well as an algorithm that shows the surprising fact that merging of bit-strings on EREW PRAMs is possible in loglog-time.

Dissemination of data in buttery and deBruijn networks, efficient on-line routing of complicated permutations, and embedding of trees in the presence of faults were discussed in the area of hypercubic networks. The talks about networks were rounded off by developing a theory of wormhole routing.

Talks in parallel complexity theory dealt with pointers versus arithmetic in PRAMs, structural considerations of parallel algorithms, lower bound techniques, scheduling problems, time-varying data, and the parallel recognition of context free languages.

Moreover, a look into asynchronous list traversal problems and into the future of optical computers was given.

Worth mentioning, Larry Rudolph demonstrated in his talk the differences between sequential, distributed, and parallel computing by juggling with apples (and eating one of them).

Caused by the pleasant atmosphere, the participants used the surroundings for lively discussions and recreational hiking.

Finally, we would like to express our thanks to all who contributed to the success of this seminar.