Concept

Distributed algorithm

Related publications (180)

A Fault-Tolerant Token-Based Atomic Broadcast Algorithm

Many atomic broadcast algorithms have been published in the last 20 years. Token-based algorithms represent a large class of these algorithms. Interestingly, all the token-based atomic broadcast algorithms rely on a group membership service and none of the ...

2011

Fast Computation of Small Cuts via Cycle Space Sampling

David Pritchard

We describe a new sampling-based method to determine cuts in an undirected graph. For a graph (V, E), its cycle space is the family of all subsets of E that have even degree at each vertex. We prove that with high probability, sampling the cycle space iden ...

2011

Detection and Recovery From Pollution Attacks in Coding Based Distributed Storage Schemes

László Czap, Levente Buttyan

We address the problem of pollution attacks in coding based distributed storage systems. In a pollution attack, the adversary maliciously alters some of the stored encoded packets, which results in the incorrect decoding of a large part of the original dat ...

Institute of Electrical and Electronics Engineers2011

Distributed processing of continuous sliding-window k-NN queries for data stream filtering

Karl Aberer, Ivana Podnar, Kresimir Pripuzic

A sliding-window k-NN query (k-NN/w query) continuously monitors incoming data stream objects within a sliding window to identify k closest objects to a query. It enables effective filtering of data objects streaming in at high rates from potentially distr ...

Springer Verlag2011

Round-Based Consensus Algorithms, Predicate Implementations and Quantitative Analysis

Fatemeh Borran

Fault-tolerant computing is the art and science of building computer systems that continue to operate normally in the presence of faults. The fault tolerance field covers a wide spectrum of research area ranging from computer hardware to computer software. ...

EPFL2011

Verification of consensus algorithms using satisfiability solving

André Schiper

Consensus is at the heart of fault-tolerant distributed computing systems. Much research has been devoted to developing algorithms for this particular problem. This paper presents a semi-automatic verification approach for asynchronous consensus algorithms ...

Springer Verlag2011

Quantitative Analysis of Consensus Algorithms

André Schiper, Martin Hutle, Fatemeh Borran, Nuno Filipe de Sousa Santos

Consensus is one of the key problems in fault-tolerant distributed computing. Although the solvability of consensus is now a well-understood problem, comparing different algorithms in terms of efficiency is still an open problem. In this paper, we address ...

2011

Systematic correct construction of self-stabilizing systems: A case study

Joseph Sifakis

Design and implementation of distributed algorithms often involve many subtleties due to their complex structure, non-determinism, and low atomicity as well as occurrence of unanticipated physical events such as faults. Thus, constructing correct distribut ...

2010

PaxosInside

Rachid Guerraoui, Maysam Yabandeh

Amodernmanycore architecture can be viewed as a distributed system with explicit message passing to communicate between cores. Ensuring the consistency of shared state replicated over several cores is the key to the well functioning of such a system. Yet, ...

2010

Order-Optimal Consensus Through Randomized Path Averaging

Martin Vetterli, Patrick Thiran, Florence Bénézit

Gossip algorithms have recently received significant attention, mainly because they constitute simple and robust mes- sage-passing schemes for distributed information processing over networks. However, for many topologies that are realistic for wire- less ...

Institute of Electrical and Electronics Engineers2010

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.