TOP
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
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 9110

Parallel and Distributed Algorithms

( Mar 04 – Mar 08, 1991 )

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/9110

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



Summary

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.

Copyright

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

Related Seminars
  • 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)