Publications related to Byzantine consensus is Θ(n^2): the Dolev-Reischuk bound is tight even in partial synchrony!

Enhancing Bitcoin Security and Performance with Strong Consistency via Collective Signing

Bryan Alexander Ford, Linus Gasser, Philipp Svetolik Jovanovic, Nicolas Gailly, Ismail Khoffi

While showing great promise, Bitcoin requires users to wait tens of minutes for transactions to commit, and even then, offering only probabilistic guarantees. This paper introduces ByzCoin, a novel Byzantine consensus protocol that leverages scalable colle ...

Usenix Assoc2016

Bitcoin Meets Collective Signing

Bryan Alexander Ford, Linus Gasser, Eleftherios Kokoris Kogias, Philipp Svetolik Jovanovic, Nicolas Gailly, Ismail Khoffi

While showing great promise, Bitcoin requires users to wait tens of minutes for transactions to commit, and even then, offering only probabilistic guarantees. This paper introduces ByzCoin, a novel Byzantine consensus protocol that leverages scalable colle ...

2016

Beyond One Third Byzantine Failures

Rachid Guerraoui, Anne-Marie Kermarrec, Cheng Wang

The Byzantine agreement problem requires a set of

n

processes to agree on a value sent by a transmitter, despite a subset of

b

processes behaving in an arbitrary, i.e. Byzantine, manner and sending corrupted messages to all processes in the system. It ...

2015

Fast Byzantine Agreement

Rachid Guerraoui, Florian Huc

This paper presents the first probabilistic Byzantine Agreement algorithm whose communication and time complexities are poly-logarithmic. So far, the most effective probabilistic Byzantine Agreement algorithm had communication complexity and time complexit ...

2013

Abstractions for Solving Consensus and Related Problems with Byzantine Faults

Zarko Milosevic

We become increasingly dependent on online services; therefore, their availability and correct behavior become increasingly important. Software replication is a popular technique for ensuring that computer systems continue to provide a correct service even ...

EPFL2013

A Polynomial-Time Solution Scheme for Quadratic Stochastic Programs

Daniel Kuhn

We consider quadratic stochastic programs with random recourse—a class of problems which is perceived to be computationally demanding. Instead of using mainstream scenario tree-based techniques, we reduce computational complexity by restricting the space o ...

2013

Scalable and Secure Polling in Dynamic Distributed Networks

Rachid Guerraoui, Anne-Marie Kermarrec, Hamza Harkous, Florian Huc

We consider the problem of securely conducting a poll in synchronous dynamic networks equipped with a Public Key Infrastructure (PKI). Whereas previous distributed solutions had a communication cost of O(n^2) in an n nodes system, we present SPP (Secure an ...

2012

Practicality and time complexity of a sparsified RNA folding algorithm

Philipp Bucher, Slavica Dimitrieva Janeva

Commonly used RNA folding programs compute the minimum free energy structure of a sequence under the pseudoknot exclusion constraint. They are based on Zuker's algorithm which runs in time O(n^3). Recently, it has been claimed that RNA folding can be achie ...

2012

Randomized versus Deterministic Implementations of Concurrent Data Structures

Dan Alistarh

One of the key trends in computing over the past two decades has been increased distribution, both at the processor level, where multi-core architectures are now the norm, and at the system level, where many key services are currently distributed overmulti ...

EPFL2012

Scalable and Secure Aggregation in Distributed Networks

Rachid Guerraoui, Anne-Marie Kermarrec, Hamza Harkous, Florian Huc

We consider the problem of computing an aggregation function in a \emph{secure} and \emph{scalable} way. Whereas previous distributed solutions with similar security guarantees have a communication cost of

O(n^3)

, we present a distributed protocol that r ...

CoRR2011

Byzantine consensus is Θ(n^2): the Dolev-Reischuk bound is tight even in partial synchrony!

Graph Chatbot

Chat with Graph Search

Enhancing Bitcoin Security and Performance with Strong Consistency via Collective Signing

Bitcoin Meets Collective Signing

Beyond One Third Byzantine Failures

Fast Byzantine Agreement

Abstractions for Solving Consensus and Related Problems with Byzantine Faults

A Polynomial-Time Solution Scheme for Quadratic Stochastic Programs

Scalable and Secure Polling in Dynamic Distributed Networks

Practicality and time complexity of a sparsified RNA folding algorithm

Randomized versus Deterministic Implementations of Concurrent Data Structures

Scalable and Secure Aggregation in Distributed Networks

Fast Byzantine Agreement

Abstractions for Solving Consensus and Related Problems with Byzantine Faults

A Polynomial-Time Solution Scheme for Quadratic Stochastic Programs

Randomized versus Deterministic Implementations of Concurrent Data Structures

Beyond One Third Byzantine Failures

Bitcoin Meets Collective Signing

Scalable and Secure Polling in Dynamic Distributed Networks

Practicality and time complexity of a sparsified RNA folding algorithm

Scalable and Secure Aggregation in Distributed Networks

Enhancing Bitcoin Security and Performance with Strong Consistency via Collective Signing