The Time-Complexity of Local Decision in Distributed Agreement
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.
The fair exchange problem is key to trading electronic items in systems of mutually untrusted parties.We consider modern variants of such systems where each party is equipped with a tamper proof security module. The security modules trust each other but ca ...
This paper investigates the time-complexity of the non-blocking atomic commit (NBAC) problem in a synchronous distributed model where t out of n processes may fail by crashing. We exhibit for t > 3 an inherent trade-off between the fast abort property of N ...
This paper addresses the problem of designing an efficient implementation of a basic atomic read-write data structure over an asynchronous message-passing system. In particular, we consider time-efficient implementations of this abstraction in the case of ...
This paper establishes tight lower bounds on the time complexity of algorithms solving the generic broadcast problem. Generic broadcast assumes a symmetric, non-reflexive conflict relation on the set of messages, and requires ordered delivery only for conf ...
When devising a distributed agreement algorithm, it is common to minimize the time complexity of global decisions, which is typically measured as the number of communication rounds needed for all correct processes to decide. In practice, what we might want ...
We introduce quittable consensus, a natural variation of the consensus problem, where processes have the option to agree on “quit” if failures occur, and we relate this problem to the well-known problem of non-blocking atomic commit. We then determine the ...
Recent papers [GK03,HT03] define the weakest failure detector for solving the Non-Blocking Atomic Commit problem (NBAC) in a message passing system where processes can fail by crashing and a majority of processes never crash. In this paper, we generalize t ...
Protocols that solve agreement problems are essential building blocks for fault tolerant distributed systems. While many protocols have been published, little has been done to analyze their performance, especially the performance of their fault tolerance m ...
Protocols that solve agreement problems are essential building blocks for fault tolerant distributed systems. While many protocols have been published, little has been done to analyze their performance, especially the performance of their fault tolerance m ...
This paper addresses the question of the weakest failure detector for solving the Non-Blocking Atomic Commit problem (NBAC) in a message passing system where processes can fail by crashing. We define a failure detector, denoted by X, which we show to be su ...