Publication

The disagreement power of an adversary

Related publications (32)

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.

Orleans: Cloud Computing for Everyone

James Richard Larus

Cloud computing is a new computing paradigm, combining diverse client devices -- PCs, smartphones, sensors, single-function, and embedded -- with computation and data storage in the cloud. As with every advance in computing, programming is a fundamental ch ...

ACM2011

The Complexity Of Early Deciding Set Agreement

Rachid Guerraoui, Bastian Pochon

In the k-set agreement problem, each processor starts with a private input value and eventually decides on an output value. At most k distinct output values may be chosen, and every processor's output value must be one of the proposed values. We consider a ...

Society for Industrial and Applied Mathematics2011

The complexity of robust atomic storage

Rachid Guerraoui, Marko Vukolic

We study the time-complexity of robust atomic read/write storage from fault-prone storage components in asynchronous message-passing systems. Robustness here means wait-free tolerating the largest possible number t of Byzantine storage component failures ( ...

ACM Press2011

Model Checking of Distributed Algorithm Implementations

Maysam Yabandeh

It is notoriously difficult to develop reliable, high-performance distributed systems that run over asynchronous networks. Even if a distributed system is based on a well-understood distributed algorithm, its implementation can contain errors arising from ...

EPFL2011

Émulation de mémoire partagée en environnements distribués dynamiques

Vincent Gramoli

Most distributed systems are large-scale and dynamic. Communication has thus become a critical issue and the shared memory, which is a reliable paradigm of communication, allow distributed nodes to exchange information through read and write operations. In ...

2011

Isolated Actors for Race-Free Concurrent Programming

Philipp Haller

Message-based concurrency using actors has the potential to scale from multicore processors to distributed systems. However, several challenges remain until actor-based programming can be applied on a large scale. First, actor implementations must be effic ...

EPFL2010

The Disagreement Power of an Adversary

Rachid Guerraoui

At the heart of distributed computing lies the fundamental result that the level of agreement that can be obtained in an asynchronous shared memory model where t processes can crash is exactly t + 1. In other words, an adversary that can crash any subset o ...

2009

Failure detectors as type boosters

Rachid Guerraoui

The power of an object type T can be measured as the maximum number n of processes that can solve consensus using only objects of T and registers. This number, denoted cons(T), is called the consensus power of T. This paper addresses the question of the we ...

Springer-Verlag2008

Sharing is Harder than Agreeing

Rachid Guerraoui

One of the most celebrated results of the theory of distributed computing is the impossibility, in an asynchronous system of

n

processes that communicate through shared memory registers, to solve the set agreement problem where the processes need to deci ...

2008

Abstractions for asynchronous distributed computing with malicious players

Marko Vukolic

In modern distributed systems, failures are the norm rather than the exception. In many cases, these failures are not benign. Settings such as the Internet might incur malicious (also called Byzantine or arbitrary) behavior and asynchrony. As a result, and ...

EPFL2008

Sharing is Harder than Agreeing

Rachid Guerraoui

One of the most celebrated results of the theory of distributed computing is the impossibility, in an asynchronous system of

n

processes that communicate through shared memory registers, to solve the set agreement problem where the processes need to deci ...

2008