NDLI: Optimal implementation of the weakest failure detector for solving consensus (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)

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

Content Provider	ACM Digital Library
Author	Arévalo, Sergio Fernández, Antonio Larrea, Mikel
Abstract	Unreliable failure detectors were introduced by Chandra and Toueg [2] as a mechanism that provides (possibly incorrect) information about process failures. They showed how unreliable failure detectors can be used to solve the Consensus problem in asynchronous systems. They also showed in [1] that one of the classes of failure detectors they defined, namely Eventually Strong (⋄S), is the weakest class allowing to solve Consensus1.This brief announcement presents a new algorithm implementing ⋄S. Due to space limitation, the reader is referred to [4] for an in-depth presentation of the algorithm (system model, correctness proof, and performance analysis). Here, we present the general idea of the algorithm and compare it with other algorithms implementing unreliable failure detectors.The algorithm works as follows. We have n processes, p1, …, pn. Initially, process p1 starts sending messages periodically to the rest of processes. The rest of processes initially trust p1, and wait for its messages. If a process does not receive a message within some timeout period from its trusted process, then it suspects its trusted process and takes the next process as its new trusted process. If a process trusts itself, then it starts sending messages periodically to its successors. Otherwise, it just waits for periodical messages from its trusted process. If, at some point, a process receives a message from a process pi such that pi precedes its trusted process, then it will trust pi again, increasing the value of its timeout period with respect to pi.With this algorithm, eventually all the correct processes will permanently trust the same correct process. This provides the eventual weak accuracy property required by ⋄S. By simply suspecting the rest of processes, we obtain the strong completeness property required by ⋄S.Our algorithm compares favorably with the algorithms proposed in [2] and [3] in terms of the number and size of the messages periodically sent and the total amount of information periodically exchanged. Since algorithms implementing failure detectors need not necessarily be periodic, we propose a new and (we believe) more adequate performance measure, which we call eventual monitoring degree. Informally, this measure counts the number of pairs of correct processes that will infinitely often communicate. We show that the proposed algorithm is optimal with respect to this measure. Table 1 summarizes the comparison, where C denotes the number of correct processes and LFA denotes the proposed algorithm.
File Format	PDF
ISBN	1581131836
DOI	10.1145/343477.362113
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

Optimal Implementation of the Weakest Failure Detector for Solving Consensus (0)

Brief Announcement: Optimal Implementation of the Weakest Failure Detector for Solving Consensus (0)

Brief announcement: Optimal implementation of the weakest failure detector for solving consensus (2000)

The weakest failure detector for solving consensus

The weakest failure detector for solving consensus (1996).

Implementing the weakest failure detector for solving consensus

Optimal implementation of the weakest failure detector for solving consensus

The weakest failure detector to solve nonuniform consensus

Brief announcement: an efficient failure detector for omission environments

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

Similar Documents

Optimal Implementation of the Weakest Failure Detector for Solving Consensus (0)

Brief Announcement: Optimal Implementation of the Weakest Failure Detector for Solving Consensus (0)

Brief announcement: Optimal implementation of the weakest failure detector for solving consensus (2000)

The weakest failure detector for solving consensus

The weakest failure detector for solving consensus (1996).

Implementing the weakest failure detector for solving consensus

Optimal implementation of the weakest failure detector for solving consensus

The weakest failure detector to solve nonuniform consensus

Brief announcement: an efficient failure detector for omission environments

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