When several computers have to cooperate to achieve a certain task (i.e. distributed computing) we need 'recipes' (i.e. protocols) to tell them what to do. Unfortunately, human minds are not well suited to keeping track of what might happen given even a very simple protocol. In this book Dr Schoone shows how we can derive properties of those protocols that always hold (i.e. invariants), irrespective of what actually happens in an execution of the protocol. From these invariants the basic attributes of the protocols can be obtained. Each protocol is explained intuitively, proved correct using invariants, and analysed to establish the relation between parameter settings and its essential features. The protocols belong to a wide range of layers in the ISO reference model hierarchy, and include the following: a class of communication protocols that tolerate and correct message loss, duplication, and resequencing; protocols for determining and maintaining routing information, both in a static and a dynamic environment; connection-management protocols; and atomic commitment protocols for use in distributed database management.

Various problems in computer science are 'hard', that is NP-complete, and so not realistically computable; thus in order to solve them they have to be approximated. 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 (for example, flows, coverings, matchings, travelling salesman problems, graphs), but in order to make the book reasonably self-contained, 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 ended by an appendix that gives a convenient summary of the problems described in the book. This is an up-to-date reference for research workers in the area of algorithms, but it can also be used for graduate courses in the subject.

'Design by programming' has proved very successful in the development of complex software systems. This book describes the construction of programs for VLSI digital circuit design, using the language Tangram, and shows how they can be compiled automatically in fully asynchronous circuits. Handshake circuits were invented by the author to separate questions involving the efficient implementation of the VLSI circuits from issues arising in their design. Dr van Berkel presents a mathematical theory of handshake circuits and a silicon compiler supported by a correctness proof. The treatment of VLSI realizations of handshake circuits includes various forms of optimization, handshake refinement, message encoding, circuit initialization, and testing. The approach is illustrated with a host of examples drawn from a wide range of application areas. The book will be of use to electrical engineers and computer scientists involved in VLSI design.

The major reason for the lack of use of parallel computing is the mismatch between the complexity and variety of parallel hardware, and the software development tools to program it. The cost of developing software needs to be amortised over decades, but the platforms on which it executes change every few years, requiring complete rewrites. The evident cost-effectiveness of parallel computation has not been realized because of this mismatch. This book presents an integrated approach to parallel software development by addressing both software and performance issues together. It presents a methodology for software construction that produces architecture-independent and intellectually abstract software. 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 data types, and of objects. Categorical data types abstract both from the representation of a data type, and also from the detailed control flow necessary to perform operations on it. They thus impose a strong separation between the semantics, on which programs can depend, and the implementation, which is therefore free to hide the parallel machine properties that are used.

In 1989, Michael Rabin proposed a fundamentally new approach to the problems of fault-tolerant routing and memory management in parallel computation, based on the idea of information dispersal. Yuh-Dauh Lyuu developed this idea in a number of new and exciting ways in his PhD thesis. Further work has led to extensions of these methods to other applications such as shared memory emulations. This volume presents an extended and updated printing of Lyuu's thesis. It gives a detailed treatment of the information dispersal approach to the problems of fault-tolerance and distributed representations of information which have resisted rigorous analysis by previous methods.