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.
This paper extends the failures detector approach from crash-stop failures to muteness failures. Muteness failures are malicious failures in which a process stops sending algorithm messages, but might continue to send other messages, e.g. 'I-am-alive' mess ...
Due to their nature, distributed systems are vulnerable to failures of some of their parts. Conversely, distribution also provides a way to increase the fault tolerance of the overall system. However, achieving fault tolerance is not a simple problem and r ...
Performance Evaluation of a Consensus Algorithm with Petri Nets N. Sergent This paper presents an application of Hierarchical Coloured Timed Petri Nets to the modeling, the evaluation and the improvement of the performance of a distributed consensus algori ...
Informally, an indulgent algorithm is a distributed algorithm that tolerates unreliable failure detection: the algorithm is indulgent towards its failure detector. This paper formally characterizes such algorithms and states some of their interesting featu ...
A universal construction is an algorithm that transforms any object with a sequential specification into a wait-free and linearizable implementation of that object. This paper presents a novel universal construction algorithm for a message-passing system w ...
Agreement problems constitute a fundamental class of problems in the context of distributed systems. All agreement problems follow a common pattern: all processes must agree on some common decision, the nature of which depends on the specific problem. This ...
A distributed algorithm comprises a collection of sequential-code entities, which are spread over different computers connected to a network. The process of designing a distributed algorithm is influenced by the assumptions we make on the computational env ...
In this paper, we present an algorithm for finding all common bases in two matroids. Our algorithm lists all common bases by using pivot operations in such a way that each basis appears exactly once. The time complexity of the algorithm is O(n(n^2+t)§) whe ...
In a transactional system, an atomic commitment protocol ensures that for any transaction, all data managers agree on the same outcome: commit or abort. A non-blocking atomic commitment protocol enables an outcome to be decided at every correct data manage ...
This paper presents the abstraction of lazy consensus and argues for its use as an effective component for building distributed agreement protocols in practical asynchronous systems where processes and links can crash and recover. Lazy consensus looks like ...
