Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Within this website:
External resources:
Within this website:
External resources:
  • the dblp Computer Science Bibliography

Dagstuhl Seminar 9210

Parallel and Distributed Algorithms

( Mar 02 – Mar 06, 1992 )

Please use the following short url to reference this page:

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


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.


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

Related Seminars
  • Dagstuhl Seminar 9110: Parallel and Distributed Algorithms (1991-03-04 - 1991-03-08) (Details)
  • Dagstuhl Seminar 9337: Parallel and Distributed Algorithms (1993-09-13 - 1993-09-17) (Details)
  • Dagstuhl Seminar 9537: Parallel and Distributed Algorithms (1995-09-11 - 1995-09-15) (Details)
  • Dagstuhl Seminar 9737: Parallel and Distributed Algorithms (1997-09-08 - 1997-09-12) (Details)
  • Dagstuhl Seminar 99291: Parallel and Distributed Algorithms (1999-07-18 - 1999-07-23) (Details)