Publications related to On the Reduction of Atomic Broadcast to Consensus with Byzantine Faults

On the Validity of Consensus

Rachid Guerraoui, Jovan Komatovic, Pierre Philippe Civit, Manuel José Ribeiro Vidigueira, Seth Gilbert

The Byzantine consensus problem involves.. processes, out of which t < n could be faulty and behave arbitrarily. Three properties characterize consensus: (1) termination, requiring correct (nonfaulty) processes to eventually reach a decision, (2) agreement ...

New York2023

As easy as ABC: Optimal (A)ccountable (B)yzantine (C)onsensus is easy!

Rachid Guerraoui, Jovan Komatovic, Pierre Philippe Civit, Vincent Gramoli, Seth Gilbert

It is known that the agreement property of the Byzantine consensus problem among n processes can be violated in a non-synchronous system if the number of faulty processes exceeds t0 = ┌n/3┐ − 1 [10], [19]. In this paper, we investigate the accountable Byza ...

IEEE2022

Fast and Space Efficient Spectral Sparsification in Dynamic Streams

Mikhail Kapralov, Jakab Tardos, Navid Nouri, Aidasadat Mousavifar

In this paper, we resolve the complexity problem of spectral graph sparcification in dynamic streams up to polylogarithmic factors. Using a linear sketch we design a streaming algorithm that uses (O) over tilde (n) space, and with high probability, recover ...

ASSOC COMPUTING MACHINERY2020

Manifold Learning and Optimal Control for Obstacle Avoidance in Autonomous Driving

Colin Neil Jones, Sanket Sanjay Diwale

A novel manifold learning approach is presented to incorporate computationally efficient obstacle avoidance constraints in optimal control algorithms. The method presented provides a significant computational benefit by reducing the number of constraints r ...

2019

Generic Round-Function-Recovery Attacks for Feistel Networks over Small Domains

Serge Vaudenay, Fatma Betül Durak

Feistel Networks (FN) are now being used massively to encrypt credit card numbers through format-preserving encryption. In our work, we focus on FN with two branches, entirely unknown round functions, modular additions (or other group operations), and when ...

2018

Generic Round-Function-Recovery Attacks for Feistel Networks over Small Domains

Serge Vaudenay, Fatma Betül Durak

Feistel Networks (FN) are now being used massively to encrypt credit card numbers through format-preserving encryption. In our work, we focus on FN with two branches, entirely unknown round functions, modular additions (or other group operations), and when ...

ePrint2018

SHAPE: Linear-Time Camera Pose Estimation With Quadratic Error-Decay

Martin Vetterli, Adam James Scholefield, Alireza Ghasemi

We propose a novel camera pose estimation or perspective-n-point (PnP) algorithm, based on the idea of consistency regions and half-space intersections. Our algorithm has linear time-complexity and a squared reconstruction error that decreases at least qua ...

Ieee2016

A Thrifty Universal Construction

Rachid Guerraoui, Cheng Wang

A universal construction is an algorithm which transforms any sequential implementation of an object into a concurrent implementation of that same object in a linearizable and wait-free manner. Such constructions require underlying low-level universal shar ...

2015

Asynchronous Byzantine Agreement with Optimal Resilience and Linear Complexity

Cheng Wang

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 ...

2015

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

On the Reduction of Atomic Broadcast to Consensus with Byzantine Faults

Graph Chatbot

Chat with Graph Search

On the Validity of Consensus

As easy as ABC: Optimal (A)ccountable (B)yzantine (C)onsensus is easy!

Fast and Space Efficient Spectral Sparsification in Dynamic Streams

Manifold Learning and Optimal Control for Obstacle Avoidance in Autonomous Driving

Generic Round-Function-Recovery Attacks for Feistel Networks over Small Domains

Generic Round-Function-Recovery Attacks for Feistel Networks over Small Domains

SHAPE: Linear-Time Camera Pose Estimation With Quadratic Error-Decay

A Thrifty Universal Construction

Asynchronous Byzantine Agreement with Optimal Resilience and Linear Complexity

Beyond One Third Byzantine Failures

On the Validity of Consensus

As easy as ABC: Optimal (A)ccountable (B)yzantine (C)onsensus is easy!

Manifold Learning and Optimal Control for Obstacle Avoidance in Autonomous Driving

Generic Round-Function-Recovery Attacks for Feistel Networks over Small Domains

Generic Round-Function-Recovery Attacks for Feistel Networks over Small Domains

SHAPE: Linear-Time Camera Pose Estimation With Quadratic Error-Decay

A Thrifty Universal Construction

Asynchronous Byzantine Agreement with Optimal Resilience and Linear Complexity

Beyond One Third Byzantine Failures

Fast and Space Efficient Spectral Sparsification in Dynamic Streams