國立虎尾科技大學 |

Introduction to distributed self-stabilizing algorithms /

紀錄類型:	書目-語言資料,印刷品 : Monograph/item
正題名/作者:	Introduction to distributed self-stabilizing algorithms // Karine Altisen, St�ephane Devismes, Swan Dubois, Franck Petit.
作者:	Altisen, Karine,
其他作者:	Devismes, St�ephane,
面頁冊數:	1 PDF (xvii, 147 pages) :illustrations (some color). :
附註:	Part of: Synthesis digital library of engineering and computer science.
標題:	Electronic data processing - Distributed processing. -
電子資源:	https://doi.org/10.2200/S00908ED1V01Y201903DCT015
電子資源:	https://ieeexplore.ieee.org/servlet/opac?bknumber=8693060
ISBN:	9781681735375

Introduction to distributed self-stabilizing algorithms /
Altisen, Karine,

Introduction to distributed self-stabilizing algorithms /Karine Altisen, St�ephane Devismes, Swan Dubois, Franck Petit. - 1 PDF (xvii, 147 pages) :illustrations (some color). - Synthesis lectures on distributed computing theory,#152155-1634 ;. - Synthesis lectures on distributed computing theory ;.

Part of: Synthesis digital library of engineering and computer science.

Includes bibliographical references (pages 129-141) and index.

1. Introduction -- 1.1. Parable of the Collatz conjecture -- 1.2. Distributed self-stabilizing systems -- 1.3. Roadmap of this book

Abstract freely available; full-text restricted to subscribers or individual document purchasers.

Compendex

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 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 (e.g., the Internet, Pair-to-Pair networks, and Delay Tolerant Networks are examples of such distributed systems). Furthermore, self-stabilization is usually recognized as a lightweightproperty 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.

Mode of access: World Wide Web.

ISBN: 9781681735375

Standard No.: 10.2200/S00908ED1V01Y201903DCT015doiSubjects--Topical Terms:

528325
Electronic data processing
--Distributed processing.Subjects--Index Terms:

distributed computingIndex Terms--Genre/Form:

554714
Electronic books.

LC Class. No.: QA76.9.D5 / A485 2019eb

Dewey Class. No.: 004/.36

Introduction to distributed self-stabilizing algorithms /
LDR:06345nam 2200685 i 4500 001 959758
003 IEEE
005 20190503190106.0
006 m eo d
007 cr bn |||m|||a
008 201209s2019 caua fob 001 0 eng d
020 $a 9781681735375 $q electronic
020 $z 9781681735382 $q hardcover
020 $z 9781681735368 $q paperback
024 7 $a 10.2200/S00908ED1V01Y201903DCT015 $2 doi
035 $a (CaBNVSL)thg00978843
035 $a (OCoLC)1099315450
035 $a 8693060
040 $a CaBNVSL $b eng $e rda $c CaBNVSL $d CaBNVSL
050 4 $a QA76.9.D5 $b A485 2019eb
082 0 4 $a 004/.36 $2 23
100 1 $a Altisen, Karine, $e author. $3 1253087
245 1 0 $a Introduction to distributed self-stabilizing algorithms / $c Karine Altisen, St�ephane Devismes, Swan Dubois, Franck Petit.
264 1 $a [San Rafael, California] : $b Morgan & Claypool, $c [2019]
300 $a 1 PDF (xvii, 147 pages) : $b illustrations (some color).
336 $a text $2 rdacontent
337 $a electronic $2 isbdmedia
338 $a online resource $2 rdacarrier
490 1 $a Synthesis lectures on distributed computing theory, $x 2155-1634 ; $v #15
500 $a Part of: Synthesis digital library of engineering and computer science.
504 $a Includes bibliographical references (pages 129-141) and index.
505 0 $a 1. Introduction -- 1.1. Parable of the Collatz conjecture -- 1.2. Distributed self-stabilizing systems -- 1.3. Roadmap of this book
505 8 $a 2. Preliminaries -- 2.1. Network -- 2.2. Computational model -- 2.3. Self-stabilization -- 2.4. Complexity
505 8 $a 3. Coloring under a locally central unfair daemon -- 3.1. The problem -- 3.2. The algorithm -- 3.3. Proof of self-stabilization and silence -- 3.4. Complexity analysis
505 8 $a 4. Synchronous unison -- 4.1. The problem -- 4.2. The algorithm -- 4.3. Correctness and time complexity -- 4.4. Related work
505 8 $a 5. BFS spanning tree under a distributed unfair daemon -- 5.1. The problem -- 5.2. The algorithm -- 5.3. Proof of self-stabilization and silence -- 5.4. Complexity analysis
505 8 $a 6. Dijkstra's token ring -- 6.1. The problem -- 6.2. The algorithm -- 6.3. Study assuming K (n) and a distributed unfair daemon -- 6.4. Study assuming K (n 1) and a locally central unfair daemon
505 8 $a 7. Hierarchical collateral composition -- 7.1. Hierarchical collateral composition -- 7.2. A toy example -- 7.3. Hierarchical vs. Nonhierarchical collateral composition
505 8 $a 8. Self-stabilization in message passing systems -- 8.1. Message passing for self-stabilizing systems -- 8.2. Related work -- 8.3. A lightweight technique for silent algorithms -- 8.4. Self-stabilization assuming bounded-capacity links -- 8.5. Stabilization time in message passing.
506 $a Abstract freely available; full-text restricted to subscribers or individual document purchasers.
510 0 $a Compendex
510 0 $a INSPEC
510 0 $a Google scholar
510 0 $a Google book search
520 3 $a 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 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 (e.g., the Internet, Pair-to-Pair networks, and Delay Tolerant Networks are examples of such distributed systems). Furthermore, self-stabilization is usually recognized as a lightweightproperty 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.
530 $a Also available in print.
538 $a Mode of access: World Wide Web.
538 $a System requirements: Adobe Acrobat Reader.
588 $a Title from PDF title page (viewed on May 3, 2019).
650 0 $a Electronic data processing $x Distributed processing. $3 528325
650 0 $a Computer algorithms. $3 528448
653 $a distributed computing
653 $a distributed algorithms
653 $a fault tolerance
653 $a transient faults
653 $a self-stabilization
653 $a convergence
653 $a closure
653 $a stabilization time
653 $a atomic-state model
653 $a daemons
655 0 $a Electronic books. $2 local $3 554714
700 1 $a Devismes, St�ephane, $e author. $3 1253088
700 1 $a Dubois, Swan, $e author. $3 1253089
700 1 $a Petit, Franck, $e author. $3 1253090
776 0 8 $i Print version: $z 9781681735382 $z 9781681735368
830 0 $a Synthesis lectures on distributed computing theory ; $v $ 11. $x 2155-1634 $3 974998
830 0 $a Synthesis digital library of engineering and computer science. $3 598254
856 4 0 $3 Abstract with links to full text $u https://doi.org/10.2200/S00908ED1V01Y201903DCT015
856 4 2 $3 Abstract with links to resource $u https://ieeexplore.ieee.org/servlet/opac?bknumber=8693060