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 9110

Parallel and Distributed Algorithms

( 04. Mar – 08. Mar, 1991 )

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

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


The first Workshop on "Parallel and distributed algorithms" at the IBFI was organized by Ernst W. Mayr (Frankfurt) and Friedhelm Meyer auf der Heide (Paderborn). There were twenty-six participants from five countries. Regrettably, most of the invitees from the US, Canada, and Israel had to cancel due to travel restrictions because of the Gulf war.

Twenty-four lectures were presented at the workshop, covering a wide range of topics in parallel complexity theory, parallel and distributed algorithms, parallel architectures and models of parallel and distributed computing.

Lectures in parallel complexity theory dealt with communication complexity, depth reduction for unbounded fan-in circuits and shallow circuits for symmetric functions.

A large number of algorithmic problems was covered, including clustering algorithms, parallel algorithms for sorting integers, dynamic programming and context-free recognition. Other talks were concerned with the transformation of parallel algorithms on idealistic machine models to more realistic ones, and with basic implementation issues on such more realistic networks, e.g. distributed load balancing, wait-free parallel algorithms, routing on grids, and the issue of parallel data structures like heaps and priority queues, or distributed dictionaries.

Other, more specific topics arising from architectural problems were the bisection problem for graphs of degree 4, the determination of close upper and lower bounds for the crossing number of hypercubes and cube-connected-cycles, and a time-randomness tradeoff.

Finally, there were several talks on parallel architectures and computation models. On the one hand, the theoretical PRAM model was shown to have a lot of practical appeal after all, given some recent advances in technology, and on the other, even more powerful models of parallel computation, like synchronized alternation, were presented- There were also some musings on the fundamental issues in parallel complexity theory and computation, as well as a survey on the state of the art in neurocomputing.

The setup of IBFI and the workshop provided ample time for discussions among the participants, be it on topics related to the theme of the workshop, or on politics and its fast pace at the moment.


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

Verwandte Seminare
  • Dagstuhl-Seminar 9210: Parallel and Distributed Algorithms (1992-03-02 - 1992-03-06) (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)