March 2 – 6 , 1992, Dagstuhl Seminar 9210

Parallel and Distributed Algorithms


R. Cole, E.W. Mayr, F. Meyer a.d. Heide

For support, please contact

Dagstuhl Service Team


Dagstuhl-Seminar-Report 33


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.

Dagstuhl Seminar Series


In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.


Download overview leaflet (PDF).

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.


Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.