Introduction to Distributed Self-Stabilizing Algorithms, Karine Altisen, Stephane Devismes, Swan Dubois, Franck Petit

Автор: Karine Altisen, Stephane Devismes, Swan Dubois, Franck Petit
Название: Introduction to Distributed Self-Stabilizing Algorithms
ISBN: 1681735369 ISBN-13(EAN): 9781681735368
Издательство: Mare Nostrum (Eurospan)
Рейтинг:
Цена: 72070.00 T
Наличие на складе: Нет в наличии.
Описание: This book aims at being a comprehensive and pedagogical introduction to the concept of self-stabilization , introduced by Edsger Wybe Dijkstra in 1973. Self-stabilization characterizes the ability of a distributed algorithm to converge within finite time to a configuration from which its behavior is correct (i.e., satisfies a given specification), regardless the arbitrary initial configuration of the system. This arbitrary initial configuration may be the result of the occurrence of a finite number of transient faults. Hence, self-stabilization is actually considered as a versatile non-masking fault tolerance approach, since it recovers from the effect of any finite number of such faults in a unified manner. Another major interest of such an automatic recovery method comes from the difficulty of resetting malfunctioning devices in a large-scale (and so, geographically spread) distributed system (the Internet, Pair-to-Pair networks, and Delay Tolerant Networks are examples of such distributed systems). Furthermore, self-stabilization is usually recognized as a lightweight property to achieve fault tolerance as compared to other classical fault tolerance approaches. Indeed, the overhead, both in terms of time and space, of state-of-the-art self-stabilizing algorithms is commonly small. This makes self-stabilization very attractive for distributed systems equipped of processes with low computational and memory capabilities, such as wireless sensor networks. After more than 40 years of existence, self-stabilization is now sufficiently established as an important field of research in theoretical distributed computing to justify its teaching in advanced research-oriented graduate courses. This book is an initiation course, which consists of the formal definition of self-stabilization and its related concepts, followed by a deep review and study of classical (simple) algorithms, commonly used proof schemes and design patterns, as well as premium results issued from the self-stabilizing community. As often happens in the self-stabilizing area, in this book we focus on the proof of correctness and the analytical complexity of the studied distributed self-stabilizing algorithms. Finally, we underline that most of the algorithms studied in this book are actually dedicated to the high-level atomic-state model , which is the most commonly used computational model in the self-stabilizing area. However, in the last chapter, we present general techniques to achieve self-stabilization in the low-level message passing model, as well as example algorithms.

Автор: Jean-Claude Bermond; Michel Raynal
Название: Distributed Algorithms
ISBN: 3540516875 ISBN-13(EAN): 9783540516873
Издательство: Springer
Рейтинг:
Цена: 69870.00 T
Наличие на складе: Есть у поставщика Поставка под заказ.

Автор: Fokkink Wan
Название: Distributed Algorithms: An Intuitive Approach
ISBN: 0262037661 ISBN-13(EAN): 9780262037662
Издательство: MIT Press
Рейтинг:
Цена: 56430.00 T
Наличие на складе: Невозможна поставка.
Описание:

The new edition of a guide to distributed algorithms that emphasizes examples and exercises rather than the intricacies of mathematical models.

This book offers students and researchers a guide to distributed algorithms that emphasizes examples and exercises rather than the intricacies of mathematical models. It avoids mathematical argumentation, often a stumbling block for students, teaching algorithmic thought rather than proofs and logic. This approach allows the student to learn a large number of algorithms within a relatively short span of time. Algorithms are explained through brief, informal descriptions, illuminating examples, and practical exercises. The examples and exercises allow readers to understand algorithms intuitively and from different perspectives. Proof sketches, arguing the correctness of an algorithm or explaining the idea behind fundamental results, are also included. The algorithms presented in the book are for the most part "classics," selected because they shed light on the algorithmic design of distributed systems or on key issues in distributed computing and concurrent programming.

This second edition has been substantially revised. A new chapter on distributed transaction offers up-to-date treatment of database transactions and the important evolving area of transactional memory. A new chapter on security discusses two exciting new topics: blockchains and quantum cryptography. Sections have been added that cover such subjects as rollback recovery, fault-tolerant termination detection, and consensus for shared memory. An appendix offers pseudocode descriptions of many algorithms. Solutions and slides are available for instructors.

Distributed Algorithms can be used in courses for upper-level undergraduates or graduate students in computer science, or as a reference for researchers in the field.