Descript 
1 online resource (xvii, 147 pages) : illustrations (some color) 

text rdacontent 

electronic isbdmedia 

online resource rdacarrier 
Series 
Synthesis lectures on distributed computing theory, 21551634 ; #15


Synthesis lectures on distributed computing theory ; #15


Synthesis digital library of engineering and computer science

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

Includes bibliographical references (pages 129141) and index 

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

2. Preliminaries  2.1. Network  2.2. Computational model  2.3. Selfstabilization  2.4. Complexity 

3. Coloring under a locally central unfair daemon  3.1. The problem  3.2. The algorithm  3.3. Proof of selfstabilization and silence  3.4. Complexity analysis 

4. Synchronous unison  4.1. The problem  4.2. The algorithm  4.3. Correctness and time complexity  4.4. Related work 

5. BFS spanning tree under a distributed unfair daemon  5.1. The problem  5.2. The algorithm  5.3. Proof of selfstabilization and silence  5.4. Complexity analysis 

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 

7. Hierarchical collateral composition  7.1. Hierarchical collateral composition  7.2. A toy example  7.3. Hierarchical vs. Nonhierarchical collateral composition 

8. Selfstabilization in message passing systems  8.1. Message passing for selfstabilizing systems  8.2. Related work  8.3. A lightweight technique for silent algorithms  8.4. Selfstabilization assuming boundedcapacity links  8.5. Stabilization time in message passing 

Abstract freely available; fulltext restricted to subscribers or individual document purchasers 

Compendex 

INSPEC 

Google scholar 

Google book search 

Mode of access: World Wide Web 

System requirements: Adobe Acrobat Reader 

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 an 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 (e.g., the Internet, PairtoPair networks, and Delay Tolerant Networks are examples of such distributed systems). Furthermore, selfstabilization 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 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 

Also available in print 

Title from PDF title page (viewed on May 3, 2019) 
Link 
Print version: 9781681735382
9781681735368

Subject 
Electronic data processing  Distributed processing


Computer algorithms


distributed computing


distributed algorithms


fault tolerance


transient faults


selfstabilization


convergence


closure


stabilization time


atomicstate model


daemons


Electronic books

Alt Author 
Devismes, Stéphane, author


Dubois, Swan, author


Petit, Franck, author

