Publication

Asynchronous Byzantine Agreement with Optimal Resilience and Linear Complexity

2015
Reports

Abstract

Given a system with $n > 3t + 1$ processes, where $t$ is the tolerated number of faulty ones, we present a fast asynchronous Byzantine agreement protocol that can reach agreement in $O(t)$ expected running time. This improves the $O(n^2)$ expected running time of Abraham, Dolev, and Halpern [PODC 2008]. Furthermore, if $n = (3 + \varepsilon) t$ for any $\varepsilon > 0$ , our protocol can reach agreement in $O (1 / \varepsilon)$ expected running time. This improves the result of Feldman and Micali [STOC 1988] (with constant expected running time when $n > 4 t$ ).

Official source

Graph Chat

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.

2015
Reports

Abstract

Official source

Related concepts (12)

Time complexity

In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor.

Computational complexity

In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) and memory storage requirements. The complexity of a problem is the complexity of the best algorithms that allow solving the problem. The study of the complexity of explicitly given algorithms is called analysis of algorithms, while the study of the complexity of problems is called computational complexity theory.

Space complexity

The space complexity of an algorithm or a computer program is the amount of memory space required to solve an instance of the computational problem as a function of characteristics of the input. It is the memory required by an algorithm until it executes completely. This includes the memory space used by its inputs, called input space, and any other (auxiliary) memory it uses during execution, which is called auxiliary space. Similar to time complexity, space complexity is often expressed asymptotically in big O notation, such as etc.

Related publications (2)

Asynchronous Byzantine Agreement with Optimal Resilience and Linear Complexity

Chat with Graph Search

Efficient Key Exchange for Wireless Multi-hop Networks

Generic homomorphic undeniable signatures