This book contains collected lectures given at the 1990 ALCOM Spring School of Parallel Computation. The motivation for the school was to provide an introduction for graduate students to topics at the leading edge of research in this very active area of computer science. Topics covered include PRAM algorithmics, general purpose computation, systolic and distributed algorithms, distributed memory models, as well as issues from practical parallel computation. The papers by some of the leading figures in this field have been carefully edited to make a coherent and unique introduction to the...

Using parallel machines is difficult because of their inherent complexity and because their architecture changes frequently. This book presents an integrated approach to developing software for parallel machines that addresses software issues and performance issues together. The author describes a methodology for software construction that is architecture-independent and intellectually abstract. The software can execute efficiently on a range of existing and potential hardware configurations. The approach is based on the construction of categorical data types, a generalization of abstract...

Algorithms are a set of rules that specify a sequence of actions to be taken to solve a problem. Distributed algorithms, which are designed to solve many problems at once, are conceptually far more complex than algorithms in a single processing unit environment. When the number of simultaneous events becomes large, human minds cannot keep track of all of them. Naturally, it is necessary to know whether a distributed algorithm will have the desired effect. In this book, Dr. Schoone discusses assertational verification by system-wide invariants for use in verifying the behavior of distributed...

This book is a survey of the basic techniques for approximating combinatorial problems using parallel algorithms. Its core is a collection of techniques that can be used to provide parallel approximations for a wide range of problems, such as flows, coverings, matchings, traveling salesman problems, and graphs. For added clarity, the authors provide an introductory chapter containing the basic definitions and results. A final chapter deals with problems that cannot be approximated, and the book is rounded off by an appendix that gives a convenient summary of the problems described in the...

Processor networks consisting of a thousand and more processing nodes that interact by sending messages over a communications network are feasible today. They can only meet the market's demand for high-speed, low-cost computing when adequate facilities for the implementation of distributed programs--programs consisting of a collection of processes that communicate and synchronize via the exchange of messages--are offered. This book investigates some of these facilities by viewing both the processor network and the distributed program as a graph. Dr. Hilbers begins by introducing distributed...