DIMACS Series in
Discrete Mathematics and Theoretical Computer Science

VOLUME Eighteen
TITLE: Specification of Parallel Algorithms
EDITORS: Guy E. Blelloch, K. Mani Chandy, Suresh Jagannathan
Published by the American Mathematical Society

Ordering Information

This volume may be obtained from the AMS or through bookstores in your area.

To order through AMS contact the AMS Customer Services Department, P.O. Box 6248, Providence, Rhode Island 02940-6248 USA. For Visa, Mastercard, Discover, and American Express orders call 1-800-321-4AMS.

You may also visit the AMS Bookstore and order directly from there. DIMACS does not distribute or sell these books.


As part of the DIMACS (the Center for Discrete Mathematics and Theoretical Computer Science) special year on massively parallel computation, a three day workshop on Specification of Parallel Algorithms was held in May 1994 at Princeton, New Jersey. This workshop was undertaken in collaboration with CRPC (the Center for Research on Parallel Computation).

The goal of the workshop was to bring together some of the best researchers in parallel languages, algorithms, and systems to present and discuss recent developments in their areas of expertise, and to interact on current issues of common interest. The broad focus of the workshop was on specification techniques for concurrent systems. Listed below are some of the topics discussed.

The papers found in this volume include all papers presented at the workshop.

My thanks go to all the authors and attendees for contributing to a stimulating and productive meeting. I would also like to thank the other two members of the organizing committee, Mani Chandy and Guy Blelloch for their help. Christine Thivierge at the AMS was responsible for coordinating the publication of the proceedings. The Computer Science department at Princeton University kindly provided use of their facility. Pat Toci was the DIMACS liason for the workshop; Bruce Maggs and Tom Leighton are co-chairs for all the DIMACS special year workshops.

I am especially grateful to Dale Ronan for her expert handling of all meta-technical issues surrounding the workshop; among her numerous responsibilities were coordinating hotel accomodations, handling travel arrangements and workshop registration, organizing an evening reception, and ensuring copious availability of fine refreshments during the meeting. Sandy Barbu at Princeton was also a significant contributor in this respect.

Suresh Jagannathan, NEC Research Institute, Princeton, New Jersey

Table of Contents

Foreward ix
Preface xi
A Case Study in Irregular Parallel Programming

    A.Chen, M.Straka, J. Dolby, V.Karamcheti, J.Plevyak, X. Zhang

BSP Programming

    W.F. McColl

Beyond Computable Functions or Escape form the Turing Tarpit

    Peter Wegner

Compositional Specifications of Parallel Programs: Nondeterministic Data Flow

    K. Mani Chandy, Beverly A. Sanders

Building Categorical Data Type Programs

    D.B. Skillicorn

The Concurrency Factory- Practical Tools for Specification, Stimulation, Verification, and Implementation for Concurrent Systems

    R. Cleaveland, J.N. Gada, P.M. Lewis, S.A. Smolka, O. Sokolsky, S. Zhang

Operational Implication of Conditional Unity Properties

    Yih-Kuen Tsay, Rajive L. Bagrodia

On the Implementation of Set-based Parallel Algorithms

    Susan Flynn Hummel

On Granularity of Events in Distributed Computations

    Michel Hurfin, Noel Plouzeau, Michel Raynel

Atomic Transactions for Multiprocessor Programming: A Formal Approach

    Nancy Lynch

A Practical Parallel Programming Model

    Lawrence Snyder

A Program Building Tool for Parallel Applications

    Shakil Ahmed, Nicholas Carriero, David Gelernter

Higher-Order Multiset Programming

    Daniel Le Metayer

Specifying Parallel Programs in a Functional Language: The EPL Experience

    Boleslaw K. Szymanski

Developing Molecular Dynamics Simulation Codes Using Mixed Language Programming

    Thomas DeBoni, John Feo, Hugh Caffey, Frederick Hausheer

Actor Languages for Specification of Parallel Computations

    Gul Agha, Wooyoung Kim, Rajendra Panwar

The Mode System of Moded Flat GHC

    Kazunori Ueda

ABCL/f: A Future-Based Polymorphic Typed Concurrent Object- Oriented Language- Its Design and Implementation

    Kenjiro Taura, Satoshi Matsuoka, Akinori Yonezawa

TLA in Pictures

    Leslie Lamport

Specification, Transformation, and Programming of Concurrent Systems in Rewriting Logic

    Patrick Lincoln, Narciso Marti-Oliet, Jose Meseguer

Constraint Satisfaction as a Basis for Designing Nonmasking Fault-Tolerance

    Anish Arora, Mohamed Gouda, George Varghese

A Discipline of Multiprogramming

    Jayadev Misra

Specification and Development of Parallel Algorithms with the Proteus System

    Allen Goldberg, Peter Mills, Lars Nyland, Jan Prins, John Reif, James Riely


Index Index of Volumes
DIMACS Homepage
Contacting the Center
Document last modified on October 28, 1998.