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

Publications associées (35)

Accelerating Spectral Clustering under Fairness Constraints

Fairness of decision-making algorithms is an increasingly important issue. In this paper, we focus on spectral clustering with group fairness constraints, where every demographic group is represented in each cluster proportionally as in the general populat ...

2025

Planetary-Scale Byzantine Fault Tolerance

Matteo Monti

The scale and pervasiveness of the Internet make it a pillar of planetary communication, industry and economy, as well as a fundamental medium for public discourse and democratic engagement. In stark contrast with the Internet's decentralized infrastructur ...

EPFL2024

A Comparative Analysis of Tools & Task Types for Measuring Computational Problem-Solving

Richard Lee Davis, Engin Walter Bumbacher, Jérôme Guillaume Brender

How to measure students' Computational Problem-Solving (CPS) competencies is an ongoing research topic. Prevalent approaches vary by measurement tools (e.g., interactive programming, multiple-choice tests, or programming-independent tests) and task types ( ...

Association for Computing Machinery2024

Quantifying the Unknown: Data-Driven Approaches and Applications in Energy Systems

Paul Scharnhorst

In light of the challenges posed by climate change and the goals of the Paris Agreement, electricity generation is shifting to a more renewable and decentralized pattern, while the operation of systems like buildings is increasingly electrified. This calls ...

EPFL2024

Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria

Mika Tapani Göös

We prove an N2-o(1) lower bound on the randomized communication complexity of finding an epsilon-approximate Nash equilibrium (for constant epsilon > 0) in a two-player N x N game. ...

Siam Publications2023

Hypergraph-Based Fast Distributed AC Power Flow Optimization

Colin Neil Jones, Yuning Jiang, Yingzhao Lian

This paper presents a novel distributed approach for solving AC power flow (PF) problems. The optimization problem is reformulated into a distributed form using a communication structure corresponding to a hypergraph, by which complex relationships between ...

IEEE2023

Byzantine-Resilient Learning Beyond Gradients: Distributing Evolutionary Search

Rachid Guerraoui, Matteo Monti, Andrei Kucharavy

Modern machine learning (ML) models are capable of impressive performances. However, their prowess is not due only to the improvements in their architecture and training algorithms but also to a drastic increase in computational power used to train them.|S ...

Assoc Computing Machinery2023

Building Strongly-Consistent Systems Resilient to Failures, Partitions, and Slowdowns

Cristina Basescu

Distributed systems designers typically strive to improve performance and preserve availability despite failures or attacks; but, when strong consistency is also needed, they encounter fundamental limitations. The bottleneck is in replica coordination, whi ...

EPFL2023

Simulating supercontinua from mixed and cascaded nonlinearities

Luis Guillermo Villanueva Torrijo, Victor Brasch, Tobias Herr, Furkan Ayhan, Thibault Voumard

Nonlinear optical frequency conversion is of fundamental importance in photonics and underpins countless of its applications: Sum- and difference-frequency generation in media with quadratic nonlinearity permits reaching otherwise inaccessible wavelength r ...

AIP Publishing2023

SCALLOP: Scaling the CSI-FiSh

Tako Boris Fouotsa

We present SCALLOP: SCALable isogeny action based on Oriented supersingular curves with Prime conductor, a new group action based on isogenies of supersingular curves. Similarly to CSIDH and OSIDH, we use the group action of an imaginary quadratic order’s ...

2023

Leaderless consensus

Rachid Guerraoui, Vincent Gramoli, Mihail Igor Zablotchi, Karolos Antoniadis, Gauthier Jérôme Timothée Voron

Classic synchronous consensus algorithms are leaderless in that processes exchange proposals, choose the maximum value and decide when they see the same choice across a couple of rounds. Indulgent consensus algorithms are typically leader-based. Although t ...

ACADEMIC PRESS INC ELSEVIER SCIENCE2023

The Societal and Scientific Importance of Inclusivity, Diversity, and Equity in Machine Learning for Chemistry

Daniel Probst

While the introduction of practical deep learning has driven progress across scientific fields, recent research highlighted that the requirement of deep learning for ever-increasing computational resources and data has potential negative impacts on the sci ...

2023

Hierarchy of quasisymmetries and degeneracies in the CoSi family of chiral crystal materials

Philip Johannes Walter Moll, Yi-Chiang Sun, Chunyu Guo

In materials, certain approximated symmetry operations can exist in a lower-order approximation of the effective model but are good enough to influence the physical responses of the system, and these approximated symmetries were recently dubbed "quasisymme ...

AMER PHYSICAL SOC2023

On the Validity of Consensus

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

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

Assoc Computing Machinery2023

Byzantine Consensus is Θ(n^2): The Dolev-Reischuk Bound is Tight even in Partial Synchrony!

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

The Dolev-Reischuk bound says that any deterministic Byzantine consensus protocol has (at least) quadratic communication complexity in the worst case. While it has been shown that the bound is tight in synchronous environments, it is still unknown whether ...

Dagstuhl Publishing2022

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

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

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

Communication Complexity of Collision

Mika Tapani Göös, Siddhartha Jain

The Collision problem is to decide whether a given list of numbers (x_1,…,x_n) ∈ [n]ⁿ is 1-to-1 or 2-to-1 when promised one of them is the case. We show an n^Ω(1) randomised communication lower bound for the natural two-party version of Collision where Ali ...

Leibniz-Zentrum für Informatik2022

Proofs, Circuits, and Communication

Mika Tapani Göös

We survey lower-bound results in complexity theory that have been obtained via newfound interconnections between propositional proof complexity, boolean circuit complexity, and query/communication complexity. We advocate for the theory of total search prob ...

2022

Unambiguous DNFs and Alon-Saks-Seymour

Mika Tapani Göös, Siddhartha Jain

We exhibit an unambiguous k-DNF formula that requires CNF width (Omega) over tilde (k(2)), which is optimal up to logarithmic factors. As a consequence, we get a near-optimal solution to the Alon-Saks-Seymour problem in graph theory (posed in 1991), which ...

IEEE COMPUTER SOC2022

Reconstructing Kinetic Models for Dynamical Studies of Metabolism using Generative Adversarial Networks

Vassily Hatzimanikatis, Ljubisa Miskovic, Subham Choudhury, Daniel Robert Weilandt, Pierre Guy Rémy Salvy, David Michael Moret

Kinetic models of metabolism relate metabolic fluxes, metabolite concentrations and enzyme levels through mechanistic relations, rendering them essential for understanding, predicting and optimizing the behaviour of living organisms. However, due to the la ...

NATURE PORTFOLIO2022