The Time-Complexity of Local Decision in Distributed Agreement

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.

Decision-making permeates every aspect of human and societal development, from individuals' daily choices to the complex decisions made by communities and institutions. Central to effective decision-making is the discipline of optimization, which seeks th ...

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

This paper offers a new algorithm to efficiently optimize scheduling decisions for dial-a-ride problems (DARPs), including problem variants considering electric and autonomous vehicles (e-ADARPs). The scheduling heuristic, based on linear programming theor ...

In this paper, we propose an analytical stochastic dynamic programming (SDP) algorithm to address the optimal management problem of price-maker community energy storage. As a price-maker, energy storage smooths price differences, thus decreasing energy arb ...

We consider optimal regimes for algorithm-assisted human decision-making. Such regimes are decision functions of measured pre-treatment variables and, by leveraging natural treatment values, enjoy a superoptimality property whereby they are guaranteed to o ...

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

Modern integrated circuits are tiny yet incredibly complex technological artifacts, composed of millions and billions of individual structures working in unison. Managing their complexity and facilitating their design drove part of the co-evolution of mode ...

We introduce an algorithm to reconstruct a mesh from discrete samples of a shape's Signed Distance Function (SDF). A simple geometric reinterpretation of the SDF lets us formulate the problem through a point cloud, from which a surface can be extracted wit ...

Humans are chronically exposed to airborne microplastics (MPs) by inhalation. Various types of polymer particles have been detected in lung samples, which could pose a threat to human health. Inhalation toxicological studies are crucial for assessing the e ...

Given a sequence of functions

f_1,\ldots,f_n

with

f_i:\mathcal{D}\mapsto \mathbb{R}

, finite-sum minimization seeks a point

{x}^\star \in \mathcal{D}

minimizing

\sum_{j=1}^nf_j(x)/n

. In this work, we propose a key twist into the finite-sum minimizat ...

We propose an adaptive quantum algorithm to prepare accurate variational time evolved wave functions. The method is based on the projected variational quantum dynamics (pVQD) algorithm, that performs a global optimization with linear scaling in the number ...

We study the proof theory and algorithms for orthologic, a logical system based on ortholattices, which have shown practical relevance in simplification and normalization of verification conditions. Ortholattices weaken Boolean algebras while having polyno ...

Dynamical system (DS) based motion planning offers collision-free motion, with closed-loop reactivity thanks to their analytical expression. It ensures that obstacles are not penetrated by reshaping a nominal DS through matrix modulation, which is construc ...

The rapid development of wearable biomedical systems now enables real-time monitoring of electroencephalography (EEG) signals. Acquisition of these signals relies on electrodes. These systems must meet the design challenge of selecting an optimal set of el ...

Motivation is a multifaceted phenomenon that we explore within the framework of decision-making. Through this cognitive process, actions are directed towards specific goals by performing a trade-off between the cost and benefit of an action. The dorsomedia ...

The recent geopolitical conflicts in Europe have underscored the vulnerability of the current energy system to the volatility of energy carrier prices. In the prospect of defining robust energy systems ensuring sustainable energy supply in the future, the ...

We introduce contextual stochastic bilevel optimization (CSBO) -- a stochastic bilevel optimization framework with the lower-level problem minimizing an expectation conditioned on some contextual information and the upper-level decision variable. This fram ...

A shift from fossil-based energy and products to more sustainable alternatives is essential to reduce greenhouse gas emissions and associated climate change impacts. Biomass represents a promising alternative for providing fuels and carbon-based products w ...

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

The Dolev-Reischuk bound says that any deterministic Byzantine consensus protocol has (at least) quadratic (in the number of processes) communication complexity in the worst case: given a system with n processes and at most f < n/3 failures, any solution t ...

The Time-Complexity of Local Decision in Distributed Agreement

Chat with Graph Search

Reliable data-driven decision-making through optimal transport

Planetary-Scale Byzantine Fault Tolerance

A ride time-oriented scheduling algorithm for dial-a-ride problems

Energy Management of Price-Maker Community Energy Storage by Stochastic Dynamic Programming

Optimal regimes for algorithm-assisted human decision-making

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

Graph generative deep learning models with an application to circuit topologies

Reach For the Arcs: Reconstructing Surfaces from SDFs via Tangent Points

Inhalation of Microplastics—A Toxicological Complexity

Efficient Continual Finite-Sum Minimization

Adaptive projected variational quantum dynamics

Orthologic with Axioms

Reactive collision-free motion generation in joint space via dynamical systems and sampling-based MPC

FETCH: A Fast and Efficient Technique for Channel Selection in EEG Wearable Systems

Neurobiological and metabolic basis of motivation and effort-based decision-making - A human 1H-MRS, fMRI and machine learning study

Identification of typical district configurations: A two-step global sensitivity analysis framework

Contextual Stochastic Bilevel Optimization

Decision support for the design of integrated biorefineries

On the Validity of Consensus

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