04. – 08. März 1991, Dagstuhl-Seminar 9110

Parallel and Distributed Algorithms


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

Auskunft zu diesem Dagstuhl-Seminar erteilt

Dagstuhl Service Team


Dagstuhl-Seminar-Report 8


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.

Dagstuhl-Seminar Series


In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.


Download Übersichtsflyer (PDF).

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.


Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.