Protocols by Invariants

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 algorithms. The approach is entirely pragmatic; the author considers many different examples, over a wide range of algorithms and protocols. This volume will be an essential purchase for all those with an interest in distributed algorithms.

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.

1. Introduction; 2. Link-level protocols; 3. Minimum-hop route maintenance; 4. Connection-management protocols; 5. Commit protocols; Bibliography; Index.

This book presents a collection of protocols used in distributed computing and distributed system implementation. The application areas include data communication, routing, and database management, making the book valuable for professional engineers and computer scientists working with parallel and distributed computer systems.