Distributed Algorithms for Message-Passing Systems / by Michel Raynal.

Format:

Book

Author/Creator:

Raynal, M. (Michel), author.

Contributor:

SpringerLink (Online service)

Series:

Computer Science (Springer-11645)

Language:

English

Subjects (All):

Computers.

Computer networks.

Computer programming.

Computer hardware.

Theory of Computation.

Computer Communication Networks.

Programming Techniques.

Computer Hardware.

Local Subjects:

Theory of Computation.

Computer Communication Networks.

Programming Techniques.

Computer Hardware.

Physical Description:

1 online resource (XXXI, 500 pages)

Edition:

First edition 2013.

Contained In:

Springer eBooks

Place of Publication:

Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 2013.

System Details:

text file PDF

Summary:

Distributed computing is at the heart of many applications. It arises as soon as one has to solve a problem in terms of entities -- such as processes, peers, processors, nodes, or agents -- that individually have only a partial knowledge of the many input parameters associated with the problem. In particular each entity cooperating towards the common goal cannot have an instantaneous knowledge of the current state of the other entities. Whereas parallel computing is mainly concerned with 'efficiency', and real-time computing is mainly concerned with 'on-time computing', distributed computing is mainly concerned with 'mastering uncertainty' created by issues such as the multiplicity of control flows, asynchronous communication, unstable behaviors, mobility, and dynamicity. While some distributed algorithms consist of a few lines only, their behavior can be difficult to understand and their properties hard to state and prove. The aim of this book is to present in a comprehensive way the basic notions, concepts, and algorithms of distributed computing when the distributed entities cooperate by sending and receiving messages on top of an asynchronous network. The book is composed of seventeen chapters structured into six parts: distributed graph algorithms, in particular what makes them different from sequential or parallel algorithms; logical time and global states, the core of the book; mutual exclusion and resource allocation; high-level communication abstractions; distributed detection of properties; and distributed shared memory. The author establishes clear objectives per chapter and the content is supported throughout with illustrative examples, summaries, exercises, and annotated bibliographies. This book constitutes an introduction to distributed computing and is suitable for advanced undergraduate students or graduate students in computer science and computer engineering, graduate students in mathematics interested in distributed computing, and practitioners and engineers involved in the design and implementation of distributed applications. The reader should have a basic knowledge of algorithms and operating systems.

Contents:

Part I Distributed Graph Algorithms

Chap. 1 Base Definitions and Network Traversal Algorithms

Chap. 2 Distributed Graph Algorithms

Chap. 3 An Algorithmic Framework to Compute Global Functions on a Process Graph

Chap. 4 Leader Election Algorithms

Chap. 5 Mobile Objects Navigating a Network

Part II Logical Time and Global States in Distributed Systems

Chap. 6 Nature of Distributed Computations and the Concept of a Global State

Chap. 7 Logical Time in Asynchronous Distributed Systems

Chap. 8 Asynchronous Distributed Checkpointing

Chap. 9 Simulating Synchrony on Top of Asynchronous Systems

Part III Mutual Exclusion and Resource Allocation

Chap. 10 Permission-Based Mutual Exclusion Algorithms

Chap. 11 Distributed Resource Allocation

Part IV High-Level Communication Abstractions

Chap. 12 Order Constraints on Message Delivery

Chap. 13 Rendezvous and Synchronous Communication

Part V Detection of Properties on Distributed Executions

Chap. 14 Distributed Termination Detection

Chap. 15 Distributed Deadlock Detection

Part VI Distributed Shared Memory

Chap. 16 Atomic Consistency (Linearizability)

Chap. 17 Sequential Consistency

Afterword

Bibliography

Index.

Other Format:

Printed edition:

ISBN:

978-3-642-38123-2

9783642381232

Access Restriction:

Restricted for use by site license.