Suche auf der Schloss Dagstuhl Webseite
Sie suchen nach Informationen auf den Webseiten der einzelnen Seminare? - Dann:
Nicht fündig geworden? - Einige unserer Dienste laufen auf separaten Webseiten mit jeweils eigener Suche. Bitte beachten Sie folgende Liste:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Innerhalb dieser Seite:
Externe Seiten:
  • DOOR (zum Registrieren eines Dagstuhl Aufenthaltes)
  • DOSA (zum Beantragen künftiger Dagstuhl Seminare oder Dagstuhl Perspektiven Workshops)
Innerhalb dieser Seite:
Externe Seiten:
Innerhalb dieser Seite:
Externe Seiten:
  • die Informatik-Bibliographiedatenbank dblp

Dagstuhl-Seminar 9210

Parallel and Distributed Algorithms

( 02. Mar – 06. Mar, 1992 )

Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite:

  • 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

Verwandte Seminare
  • 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)