Introduction to distributed selfstabilizing algorithms
 Responsibility
 Karine Altisen, Stéphane Devismes, Swan Dubois, Franck Petit.
 Publication
 Cham, Switzerland : Springer, 2019.
 Physical description
 1 online resource (167 pages)
 Series
 Synthesis lectures on distributed computing theory ; #15.
Online
More options
Description
Creators/Contributors
 Author/Creator
 Altisen, Karine, author.
 Contributor
 Devismes, Stéphane, author.
 Dubois, Swan, author.
 Petit, Franck, author.
 Raynal, M. (Michel), author.
Contents/Summary
 Bibliography
 Includes bibliographical references and index.
 Contents

 Preface Acknowledgments Introduction Preliminaries Coloring under a Locally Central Unfair Daemon Synchronous Unison BFS Spanning Tree Under a Distributed Unfair Daemon Dijkstra's Token Ring Hierarchical Collateral Composition SelfStabilization in Message Passing Systems Bibliography Authors' Biographies Index.
 (source: Nielsen Book Data)
 Publisher's summary

This book aims at being a comprehensive and pedagogical introduction to the concept of selfstabilization, introduced by Edsger Wybe Dijkstra in 1973.Selfstabilization 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, selfstabilization is actually considered as a versatile nonmasking 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 largescale (and so, geographically spread) distributed system (the Internet, PairtoPair networks, and Delay Tolerant Networks are examples of such distributed systems). Furthermore, selfstabilization 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 stateoftheart selfstabilizing algorithms is commonly small. This makes selfstabilization 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, selfstabilization is now sufficiently established as an important field of research in theoretical distributed computing to justify its teaching in advanced researchoriented graduate courses. This book is an initiation course, which consists of the formal definition of selfstabilization 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 selfstabilizing community. As often happens in the selfstabilizing area, in this book we focus on the proof of correctness and the analytical complexity of the studied distributed selfstabilizing algorithms. Finally, we underline that most of the algorithms studied in this book are actually dedicated to the highlevel atomicstate model, which is the most commonly used computational model in the selfstabilizing area. However, in the last chapter, we present general techniques to achieve selfstabilization in the lowlevel message passing model, as well as example algorithms.
(source: Nielsen Book Data)
Subjects
Bibliographic information
 Publication date
 2019
 Series
 Synthesis lectures on distributed computing theory, 21551634 ; #15
 Note
 Part of: Synthesis digital library of engineering and computer science.
 ISBN
 9781681735375 (electronic bk.)
 1681735377 (electronic bk.)
 9781681735382 (hardcover)
 1681735385 (hardcover)
 9781681735368 (paperback)
 1681735369 (paperback)
 9783031020131 (electronic bk.)
 3031020138 (electronic bk.)
 DOI
 10.2200/S00908ED1V01Y201903DCT015.
 10.1007/9783031020131