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.



PREFACE

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

1
BSP Programming

    W.F. McColl

21
Beyond Computable Functions or Escape form the Turing Tarpit

    Peter Wegner

37
Compositional Specifications of Parallel Programs: Nondeterministic Data Flow

    K. Mani Chandy, Beverly A. Sanders

51
Building Categorical Data Type Programs

    D.B. Skillicorn

65
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

75
Operational Implication of Conditional Unity Properties

    Yih-Kuen Tsay, Rajive L. Bagrodia

91
On the Implementation of Set-based Parallel Algorithms

    Susan Flynn Hummel

101
On Granularity of Events in Distributed Computations

    Michel Hurfin, Noel Plouzeau, Michel Raynel

115
Atomic Transactions for Multiprocessor Programming: A Formal Approach

    Nancy Lynch

125
A Practical Parallel Programming Model

    Lawrence Snyder

143
A Program Building Tool for Parallel Applications

    Shakil Ahmed, Nicholas Carriero, David Gelernter

161
Higher-Order Multiset Programming

    Daniel Le Metayer

179
Specifying Parallel Programs in a Functional Language: The EPL Experience

    Boleslaw K. Szymanski

201
Developing Molecular Dynamics Simulation Codes Using Mixed Language Programming

    Thomas DeBoni, John Feo, Hugh Caffey, Frederick Hausheer

225
Actor Languages for Specification of Parallel Computations

    Gul Agha, Wooyoung Kim, Rajendra Panwar

239
The Mode System of Moded Flat GHC

    Kazunori Ueda

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

    Kenjiro Taura, Satoshi Matsuoka, Akinori Yonezawa

275
TLA in Pictures

    Leslie Lamport

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

    Patrick Lincoln, Narciso Marti-Oliet, Jose Meseguer

309
Constraint Satisfaction as a Basis for Designing Nonmasking Fault-Tolerance

    Anish Arora, Mohamed Gouda, George Varghese

341
A Discipline of Multiprogramming

    Jayadev Misra

357
Specification and Development of Parallel Algorithms with the Proteus System

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

383

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