NDLI: Self-stabilization—beyond the token ring circulation (brief announcement)

Please wait, while we are loading the content...

Distributed algorithms in TLA (abstract)

A middleware overview: goals, research issues, and coded examples (abstract)

Data communications vs. distributed computing (abstract)

How computer architecture trends may affect future distributed systems: from infiniBand clusters to inter-processor speculation (abstract)

Towards robust distributed systems (abstract)

Interval routing schemes allow broadcasting with linear message-complexity (extended abstract)

Optimal smoothing schedules for real-time streams (extended abstract)

Average-case analysis of greedy packet scheduling (extended astract)

Sparse communication networks and efficient routing in the plane (extended abstract)

Compact roundtrip routing in directed networks (extended abstract)

Laziness pays! using lazy synchronization mechanisms to improve non-blocking constructions

Long-lived and adaptive atomic snapshot and immediate snapshot (extended abstract)

Bounds on the shared memory requirements for long-lived & adaptive objects (extended abstract)

Adaptive and efficient mutual exclusion (extended abstract)

Assigning labels in unknown anonymous networks (extended abstract)

The wakeup problem in synchronous broadcast systems (extended abstract)

Random oracles in constantipole: practical asynchronous Byzantine agreement using cryptography (extended abstract)

Clock synchronization with faults and recoveries (extended abstract)

k-set agreement with limited accuracy failure detectors

Garbage collection of timestamped data in Stampede

On the interconnection of causal memory systems

Distributed reconfiguration of metamorphic robot chains

1/k phase stamping for continuous shared data (extended abstract)

$Π^{2}$ -- a generic proxy platform for wireless access and mobility in CORBA

High performance adaptive middleware for CORBA-based systems

Efficient atomic broadcast using deterministic merge

Achieving scalability and expressiveness in an Internet-scale event notification service

X-ability: a theory of replication

Debugging distributed programs using controlled re-execution

Self-stabilizing token circulation on asynchronous uniform unidirectional rings

Stable and fault-tolerant object allocation

Resettable vector clocks

Efficient generation of all regular non-dominated coteries

Indulgent algorithms (preliminary version)

Fast deterministic consensus in a noisy environment

Stability of long-lived consensus (extended abstract)

Toward a theory of maximally concurrent programs (shortened version)

A verification technique for self-stabilizing algorithms based on Ljapunov's ”Second Method“ (brief announcement)

Time and message-efficient S-based consensus (brief announcement)

Self-stabilization—beyond the token ring circulation (brief announcement)

Optimal implementation of the weakest failure detector for solving consensus (brief announcement)

Memory consistency and process coordination for SPARC v8 multiprocessors (brief announcement)

Deterministic distributed resource discovery (brief announcement)

Compact routing with stretch factor of less than three (brief announcement)

Specification, implementation and application of randomized regular registers (brief announcement)

Distributed cooperation in the absence of communication (brief announcement)

Average probe complexity of non-dominated coteries (brief announcement)

Fast protocol transition in a distributed environment (brief announcement)

Self-stabilization—beyond the token ring circulation (brief announcement)

Content Provider	ACM Digital Library
Author	Ciuffoletti, Augusto
Abstract	There is a diffused feeling that the self-stabilization concept, as defined by Dijkstra in 1974, is extremely deep in pointing out the features of a fault tolerant distributed system, but is also too restrictive in the definition of what is self-stabilizing.My primary purpose is to explain why Dijkstra's definition needs to be extended: the reader understands that the task is extremely delicate, since there is a unanimous appreciation of the original definition of self-stabilization, and its modification should exhibit extremely strong motivations. Secondarily, we show how it can be modified to widen its applicability.First I restate the original definition using Chandy and Misra's Unity. This step is mechanical, so to keep the result as independent as possible from any subjective understanding of the self-stabilization concept:DEFINITION 1 (SELF-STABILIZING SYSTEM). Given a (flat) Unity program P with guards &Pgr; and a predicate l, P is self-stabilizing to l if and only if: the initially section of P is empty, unconditionall is stable, stability∀p ∈ &Pgr;, {l ∧ p} ≠ 0, minimal statements∀x, y ∈ {l}, x ↦ y, minimal statestrue ↦ l.finite convergence The label attached to each predicate may help intuition. The next theorem, whose proof is in the full paper that can be requested by e.mail, limits the set of problems that can be treated with self-stabilization:THEOREM 1. A predicate l satisfies stability and minimal states if and only ifonly one state satisfies l and the execution of any statement leaves that state unaltered orthere are n > 1 states that satisfy l and an indexing l} = {s0,…,sn - 1} exists such that si ensures s(i+1) mod n.A corollary says that, if there is more than one legitimate state, then units are arranged in a ring, and are enabled to move according to that arrangement. That limits the applicability of the self-stabilization concept to the range of token circulation problems, and concludes the first step.Next I want to modify the Definition 1 in order to extend the number of problems that can be treated using the self-stabilization concept. Coherently with a conservative approach, the impact of the modification should be minimal.I opt to redefine the Minimal States predicate so that it operates set-wise: to this purpose I split l, the set of legitimate states, in a family of subsets L, and for any pair in L I want that “there exists a sequence of moves transferring the system from the one into the other”. The sets in L can be defined either by enumeration, or by a characteristic property. The new formulation of the Minimal States is: DEFINITION 2 (MINIMAL STATES (SET-WISE)). A family L = {l1, …, lk}, with ∪L = l exists such that ∀(la, lb) ∈ L2, la ↦ lbThe last step consists in proving that the new definition widens the applicability of the self-stabilization concept. In Figure 1 I give a simple clock synchronization problem that can be treated with self-stabilization only when this concept is extended with the set-wise minimal states.The problem cannot be treated using Definition 1: the proof is by contradiction, using the only if part of the Theorem, if I want to exploit the presence of redundant paths. The partition I need to apply the set-wise extension is: L = {ticki, tacki \| i ∈ [0, 2n - 1]} where ticki = {s \| A = 2i - 1 ∧ A = C + 1 ∧ (∀k : Bk = A ∨ Bk = C)} tacki = {s \| A = 2i - 1 ∧ A = C - 1 ∧ (∀k : Bk = A ∨ Bk = C)} and the problem is solved by the following self-stabilizing algorithm (the proof is available):A: if (B==B2) and (B2==B3) if even(B1) A=B1+1; else A=B1; C: if (B1==B2) and (B2==B3) if even(B1) C=B1; else C=B1+1;Bk: if A!=(C-1) Bk=A; else Bk=C;.
File Format	PDF
ISBN	1581131836
DOI	10.1145/343477.362068
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2000-07-16
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Brief announcement: optimal self-stabilizing multi-token ring: a randomized solution

Self-Stabilization Beyond the token ring circulation

Self-stabilization beyond the token ring circulation (2001).

Self-Stabilizing Master-Slave Token Circulation Algorithm in an Undirected Ring of Arbitrary Size and Its Orientation

Brief announcement: monotonic stabilization

Brief Announcement: Memory Lower Bounds for Self-Stabilization

Self-Stabilizing ℓ-Exclusion Revisited

Brief announcement: a framework for building self-stabilizing overlay networks

Self-Stabilizing Token Circulation on Anonymous Message Passing Rings (Extended Abstract) (1998)

Self-stabilization—beyond the token ring circulation (brief announcement)

Similar Documents

Brief announcement: optimal self-stabilizing multi-token ring: a randomized solution

Self-Stabilization Beyond the token ring circulation

Self-stabilization beyond the token ring circulation (2001).

Self-Stabilizing Master-Slave Token Circulation Algorithm in an Undirected Ring of Arbitrary Size and Its Orientation

Brief announcement: monotonic stabilization

Brief Announcement: Memory Lower Bounds for Self-Stabilization

Self-Stabilizing ℓ-Exclusion Revisited

Brief announcement: a framework for building self-stabilizing overlay networks

Self-Stabilizing Token Circulation on Anonymous Message Passing Rings (Extended Abstract) (1998)

Self-stabilization—beyond the token ring circulation (brief announcement)