Parallel and Distributed Algorithms

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.