Julien Dallot

Julien Dallot, Yuval Emek, Yuval Gil et al.

This paper introduces a new model for ML-augmented online decision making, called online algorithms with unreliable guidance (OAG). This model completely separates between the predictive and algorithmic components, thus offering a single well-defined analysis framework that relies solely on the considered problem. Formulated through the lens of request-answer games, an OAG algorithm receives, with each incoming request, a piece of guidance which is taken from the problem's answer space; ideally, this guidance is the optimal answer for the current request, however with probability $β$, the guidance is adversarially corrupted. The goal is to develop OAG algorithms that admit good competitiveness when $β= 0$ (a.k.a. consistency) as well as when $β= 1$ (a.k.a. robustness); the appealing notion of smoothness, that in most prior work required a dedicated loss function, now arises naturally as $β$ shifts from $0$ to $1$. We then describe a systematic method, called the drop or trust blindly (DTB) compiler, which transforms any online algorithm into a learning-augmented online algorithm in the OAG model. Given a prediction-oblivious online algorithm, its learning-augmented counterpart produced by applying the DTB compiler either follows the incoming guidance blindly or ignores it altogether and proceeds as the initial algorithm would have; the choice between these two alternatives is based on the outcome of a (biased) coin toss. As our main technical contribution, we prove (rigorously) that although remarkably simple, the class of algorithms produced via the DTB compiler includes algorithms with attractive consistency-robustness guarantees for three classic online problems: for caching and uniform metrical task systems our algorithms are optimal, whereas for bipartite matching (with adversarial arrival order), our algorithm outperforms the state-of-the-art.

Julien Dallot, Caio Caldeira, Arash Pourdamghani et al.

This paper studies the integration of machine-learned advice in overlay networks in order to adapt their topology to the incoming demand. Such demand-aware systems have recently received much attention, for example in the context of data structures (Fu et al. in ICLR 2025, Zeynali et al. in ICML 2024). We in this paper extend this vision to overlay networks where requests are not to individual keys in a data structure but occur between communication pairs, and where algorithms have to be distributed. In this setting, we present an algorithm that adapts the topology (and the routing paths) of the overlay network to minimize the hop distance travelled by bit, that is, distance times demand. In a distributed manner, each node receives an (untrusted) prediction of the future demand to help him choose its set of neighbors and its forwarding table. This paper focuses on optimizing the well-known skip list networks (SLNs) for their simplicity. We start by introducing continuous skip list networks (C-SLNs) which are a generalization of SLNs specifically designed to tolerate predictive errors. We then present our learning-augmented algorithm, called LASLiN, and prove that its performance is (i) similar to the best possible SLN in case of good predictions ($O(1)$-consistency) and (ii) at most a logarithmic factor away from a standard overlay network in case of arbitrarily wrong predictions ($O(\log^2 n)$-robustness, where $n$ is the number of nodes in the network). Finally, we demonstrate the resilience of LASLiN against predictive errors (ie, its smoothness) using various error types on both synthetic and real demands.

Julien Dallot, Darya Melnyk, Tijana Milentijevic et al.

This paper studies the Byzantine Agreement problem where the nodes have access to a predictor that flags nodes for suspicion of faulty (Byzantine) behavior. We focus on algorithmic resilience -- the maximum number of faulty nodes an algorithm can tolerate -- and present algorithms and impossibility results whose resilience depend on the accuracy of the predictor. As our first main result, we bring a complete characterization of the consistency--robustness trade-offs in both the non-authenticated and authenticated settings: for $n$ nodes and a parameter $α\in [0, 1]$, we present algorithms that tolerate up to $α\cdot n$ faulty nodes when the predictor is correct (consistency), and up to $\frac{1-α}{2} \cdot n - 1$ faulty nodes when the predictor is arbitrarily wrong (robustness); in the authenticated setting the robustness bound improves to $(1-α) \cdot n - 1$. These trade-offs are exactly tight as we show that one additional faulty node renders the problem impossible. Our second main result characterizes smoothness: the rate at which resilience degrades as the predictor becomes less accurate. We show that resilience linearly decreases in the number of wrong predictions as long as that number stays within a constant fraction of $n$. Concretely, in the non-authenticated setting each additional wrong prediction loses one unit of resilience, whereas in the authenticated setting the decline is halved since two wrong predictions are needed to lose one unit of resilience.

Tom-Lukas Breitkopf, Julien Dallot, Antoine El-Hayek et al.

Population protocols are a model of distributed computing where $n$ agents, each a simple finite-state machine, interact in pairs to solve a common task against a (adversarial) interaction scheduler. This model was intensively studied in recent years; in particular, the problem of relative majority received much attention: Each agent starts with an input opinion (or color) out of $k$ possibilities, and the goal is for each agent to eventually output the color with the largest support in the population. Before our work, the state complexity (the minimum number of states required per agent) was only known to be between $Ω(k^2)$ and $O(k^{7})$. Our main contribution is a population protocol that solves the relative majority problem with $k^3$ states. We achieve this result with a new protocol called CIRCLES. While prior approaches in the literature relied on duels of agents to find the majority color -- an approach that proved effective for the case with two colors -- CIRCLES partitions the agents into circular linked lists of decreasing sizes, with the property that no two agents with the same initial color lie in the same circle. We show that CIRCLES always correctly computes the desired structure against the most adversarial of schedulers (weakly fair). We then show that a trivial extension of CIRCLES solves the relative majority problem. We extend our protocol to handle various tie-breaking mechanisms or to support the case where the agents do not share a prior ordering of the colors. Finally, we show that a modification of CIRCLES solves the ranking problem with $2 \cdot k^4$ states, where each agent must output the rank of its initial color in the population.

Julien Dallot, Darya Melnyk, Maciej Pacut et al.

Graph embedding is a fundamental problem of mapping nodes of a guest graph into a host graph while minimizing the distance distortion, with broad applications, including virtual network embeddings into physical topologies, VLSI design, or community detection in social networks. However, in many real-world applications the guest graph changes over time and the embedding can adapt to these changes (e.g. virtual machine migration in network embeddings). Static embeddings are inherently inefficient in comparison to adaptive embeddings, but it remains an unresolved algorithmic challenge to design efficient embedding algorithms that adapt to the demand on-the-fly, i.e., that are online. In this paper, we derive optimal deterministic and randomized online algorithms for the online graph embedding problem in star host graphs. This is an essential building block on the way to design algorithms for more complex host graphs, representing a single node and its neighborhood. We start by presenting a $1.5$-competitive deterministic algorithm and showing that no deterministic algorithm can perform better. Our main contribution is a randomized algorithm that achieves a significantly better competitive ratio of $11/9 \approx 1.222$. Both the deterministic and the randomized algorithms are optimal, which we prove by deriving tight lower bounds for the competitiveness of any algorithm.

Marcin Bienkowski, Julien Dallot, Dominik Danelski et al.

Payment channel networks (PCNs) are a promising solution to make cryptocurrency transactions faster and more scalable. At their core, PCNs bypass the blockchain by routing the transactions through intermediary channels. However, a channel can forward a transaction only if it possesses the necessary funds: the problem of keeping the channels balanced is a current bottleneck on the PCN's transaction throughput. This paper considers the problem of maximizing the number of accepted transactions by a channel in a PCN. Previous works either considered the associated optimization problem with all transactions known in advance or developed heuristics tested on particular transaction datasets. This work however considers the problem in its purely online form where the transactions are arbitrary and revealed one after the other. We show that the problem can be modeled as a new online knapsack variant where the items (transaction proposals) can be either positive or negative depending on the direction of the transaction. The main contribution of this paper is a deterministic online algorithm that is $O(\log B)$-competitive, where $B$ is the knapsack capacity (initially allocated funds). We complement this result with an asymptotically matching lower bound of $Ω(\log B)$ which holds for any randomized algorithm, demonstrating our algorithm's optimality.