NDLI: Fast and compact self stabilizing verification, computation, and fault detection of an MST

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

Coordinated consensus in dynamic networks

Distributed graph coloring in a few rounds

The complexity of robust atomic storage

On the power of hardware transactional memory to simplify memory management

Distributed deterministic edge coloring using bounded neighborhood independence

Compact policy routing

Adaptively secure broadcast, revisited

Distributed k-core decomposition

Transforming worst-case optimal solutions for simultaneous tasks into all-case optimal solutions

A tight unconditional lower bound on distributed randomwalk computation

The universe of symmetry breaking tasks

Xheal: localized self-healing using expanders

Scalability versus semantics of concurrent FIFO queues

Tight bounds on information dissemination in sparse mobile networks

Error-free multi-valued consensus with byzantine failures

MIS on trees

Resilience of mutual exclusion algorithms to transient memory faults

A complexity separation between the cache-coherent and distributed shared memory models

The space complexity of long-lived and one-shot timestamp implementations

Locally checkable proofs

Scalable rational secret sharing

Fork-consistent constructions from registers

Optimal-time adaptive strong renaming, with applications to counting

Minimum congestion mapping in a cloud

Rationality authority for provable rational behavior

Fast and compact self stabilizing verification, computation, and fault detection of an MST

Distributed computing with rules of thumb

Order optimal information spreading using algebraic gossip

Byzantine agreement with homonyms

Toward more localized local algorithms: removing assumptions concerning global knowledge

Structuring unreliable radio networks

From bounded to unbounded concurrency objects and back

Fault-tolerant spanners: better and simpler

Analyzing consistency properties for fun and profit

Unbounded contention resolution in multiple-access channels

The round complexity of distributed sorting: extended abstract

Conflict on a communication channel

Secure data structures based on multi-party computation

Stability of a peer-to-peer communication system

Incentive-compatible distributed greedy protocols

Time-efficient randomized multiple-message broadcast in radio networks

The impact of memory models on software reliability in multiprocessors

Tracking distributed aggregates over time-based sliding windows

Robust network supercomputing without centralized control

Sustaining collaboration in multicast despite rational collusion

Faster information dissemination in dynamic networks via network coding

Accurate byzantine agreement with feedback

On the hardness and approximation of minimum topic-connected overlay

Reliable end-user communication under a changing packet network protocol

B-neck: a distributed and quiescent max-min fair algorithm

A generalization of multiple choice balls-into-bins

Securing social networks

Information dissemination on multiple channels

A theory of goal-oriented communication

Parallel and distributed programming extensions for mainstream languages based on pi-calculus

Robust data sharing with key-value stores

A nonblocking set optimized for querying the minimum value

Network synchronization and localization based on stolen signals

Time bounds for shared objects in partially synchronous systems

Validity bound of regular registers with churn and byzantine processes

The inherent difficulty of timely primary-backup replication

Easy impossibility proofs for k-set agreement in message passing systems

Randomized compact routing in decomposable metrics

Solving the at-most-once problem with nearly optimal effectiveness

Partial reversal acyclicity

Fast and compact self stabilizing verification, computation, and fault detection of an MST

Content Provider	ACM Digital Library
Author	Korman, Amos Masuzawa, Toshimitsu Kutten, Shay
Abstract	This paper demonstrates the usefulness of distributed local verification of proofs, as a tool for the design of algorithms. In particular, it introduces a somewhat generalized notion of distributed local proofs, and utilizes it for improving the memory size complexity, while obtaining time efficiency too. As a result, we show that optimizing the memory size carries at most a small cost in terms of time, in the context of Minimum Spanning Tree (MST). That is, we present algorithms that are both time and space efficient for constructing an MST, for verifying it, and for detecting the location of the faults. This involves several steps that may be considered contributions in themselves. First, we generalize the notion of local proofs, trading off the locality (or, really, the time complexity) for memory efficiency. This adds a dimension to the study of distributed local proofs, that has been gaining attention recently. Second, as opposed to previous studies that presented only the labels verification part of a proof labeling schemes, we present here also a space and time efficient distributed self stabilizing marker algorithm to generates those labels. This presents proof labeling schemes as an algorithmic tool. Finally, we show how to enhance a known transformer that makes input/output algorithms self stabilizing. It now takes as input an efficient construction algorithm and an efficient self stabilizing proof labeling scheme, and produces an efficient self stabilizing algorithm. When used for MST, the transformer produces a memory optimal (i.e., O(log n) bits per node) self stabilizing algorithm, whose time complexity, namely, O(n), is significantly better even than that of previous algorithms that where not space optimal. (The time complexity of previous MST algorithms that used $©(log^{2}$ n) memory bits per node was $O(n^{2}),$ and the time for optimal space algorithms was O(n\|E\|).) Our MST algorithm also has the important property that, if faults occur after the construction ended, then they are detected by some nodes within $O(log^{2}$ n) time in synchronous networks, or within O(? $log^{2}$ n) time in asynchronous ones. This property is inherited from the specific proof labeling scheme we construct. It answers an open problem posed by Awerbuch and Varghese (FOCS 1991). We also show that ©(log n) time is necessary if the memory size is restricted to O(log n) bits, even in synchronous networks. Another property is that if f faults occurred, then, within the required detection time above, they are detected by some node in the O(f log n) locality of each of the faults. We also show how to improve the above detection time and locality, at the expense of some increase in the memory.
Starting Page	311
Ending Page	320
Page Count	10
File Format	PDF
ISBN	9781450307192
DOI	10.1145/1993806.1993866
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2011-06-06
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Self stabilization Fault detection Locality Local proof checking Distributed algorithms Distributed verification Mst
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

Fast and compact self-stabilizing verification, computation, and fault detection of an MST

Fast and Compact Self-Stabilizing Verification, Computation, and Fault Detection of an MST, an extended version of the PODC

Fast and compact self-stabilizing verification, computation, and fault detection of an MST

Self-stabilizing Algorithms

Brief announcement: self-stabilizing resource discovery algorithm

Verification of orbitally self-stabilizing distributed algorithms using Lyapunov functions and Poincare maps

Distributed verification of minimum spanning trees

Fast and Compact Distributed Verification and Self-Stabilization of a DFS Tree (2014)

Self-stabilizing counting in mobile sensor networks

Fast and compact self stabilizing verification, computation, and fault detection of an MST

Similar Documents

Fast and compact self-stabilizing verification, computation, and fault detection of an MST

Fast and Compact Self-Stabilizing Verification, Computation, and Fault Detection of an MST, an extended version of the PODC

Fast and compact self-stabilizing verification, computation, and fault detection of an MST

Self-stabilizing Algorithms

Brief announcement: self-stabilizing resource discovery algorithm

Verification of orbitally self-stabilizing distributed algorithms using Lyapunov functions and Poincare maps

Distributed verification of minimum spanning trees

Fast and Compact Distributed Verification and Self-Stabilization of a DFS Tree (2014)

Self-stabilizing counting in mobile sensor networks

Fast and compact self stabilizing verification, computation, and fault detection of an MST