000 05211nam a22005655i 4500
001 978-3-031-02013-1
003 DE-He213
005 20240730163754.0
007 cr nn 008mamaa
008 220601s2019 sz | s |||| 0|eng d
020 _a9783031020131
_9978-3-031-02013-1
024 7 _a10.1007/978-3-031-02013-1
_2doi
050 4 _aQA75.5-76.95
072 7 _aUY
_2bicssc
072 7 _aCOM000000
_2bisacsh
072 7 _aUY
_2thema
082 0 4 _a004
_223
100 1 _aAltisen, Karine.
_eauthor.
_4aut
_4http://id.loc.gov/vocabulary/relators/aut
_980492
245 1 0 _aIntroduction to Distributed Self-Stabilizing Algorithms
_h[electronic resource] /
_cby Karine Altisen, Stéphane Devismes, Swan Dubois, Franck Petit.
250 _a1st ed. 2019.
264 1 _aCham :
_bSpringer International Publishing :
_bImprint: Springer,
_c2019.
300 _aXVII, 147 p.
_bonline resource.
336 _atext
_btxt
_2rdacontent
337 _acomputer
_bc
_2rdamedia
338 _aonline resource
_bcr
_2rdacarrier
347 _atext file
_bPDF
_2rda
490 1 _aSynthesis Lectures on Distributed Computing Theory,
_x2155-1634
505 0 _aPreface -- 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 -- Self-Stabilization in Message Passing Systems -- Bibliography -- Authors' Biographies -- Index.
520 _aThis 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 an 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.
650 0 _aComputer science.
_99832
650 0 _aCoding theory.
_94154
650 0 _aInformation theory.
_914256
650 0 _aData structures (Computer science).
_98188
650 1 4 _aComputer Science.
_99832
650 2 4 _aCoding and Information Theory.
_980493
650 2 4 _aData Structures and Information Theory.
_931923
700 1 _aDevismes, Stéphane.
_eauthor.
_4aut
_4http://id.loc.gov/vocabulary/relators/aut
_980494
700 1 _aDubois, Swan.
_eauthor.
_4aut
_4http://id.loc.gov/vocabulary/relators/aut
_980495
700 1 _aPetit, Franck.
_eauthor.
_4aut
_4http://id.loc.gov/vocabulary/relators/aut
_980496
710 2 _aSpringerLink (Online service)
_980497
773 0 _tSpringer Nature eBook
776 0 8 _iPrinted edition:
_z9783031001314
776 0 8 _iPrinted edition:
_z9783031008856
776 0 8 _iPrinted edition:
_z9783031031410
830 0 _aSynthesis Lectures on Distributed Computing Theory,
_x2155-1634
_980498
856 4 0 _uhttps://doi.org/10.1007/978-3-031-02013-1
912 _aZDB-2-SXSC
942 _cEBK
999 _c84970
_d84970