9 papers
Resilient Byzantine Agreement with Predictions
Julien Dallot, Darya Melnyk, Tijana Milentijevic +2
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…
Ranking Opinions with Few States in Population Protocols
Tom-Lukas Breitkopf, Julien Dallot, Antoine El-Hayek +1
Population protocols are a model of distributed computing where agents, each a simple finite-state machine, interact in pairs to solve a common task against a (adversarial) int…
Competitive Transaction Admission in PCNs: Online Knapsack with Positive and Negative Items
Marcin Bienkowski, Julien Dallot, Dominik Danelski +2
Payment channel networks (PCNs) are a promising approach to making cryptocurrency transactions faster and more scalable. At their core, PCNs bypass the blockchain by routing transa…
Online Graph Embedding in Star Graphs
Julien Dallot, Darya Melnyk, Maciej Pacut +1
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 ne…
Online Algorithms with Unreliable Guidance
Julien Dallot, Yuval Emek, Yuval Gil +2
This paper introduces online algorithms with unreliable guidance (OAG), a model for ML-augmented online decision-making that cleanly separates the predictive and algorithmic compon…
The Harmonic Policy for Online Buffer Sharing is (2 + ln n)-Competitive: A Simple Proof
Vamsi Addanki, Julien Dallot, Leon Kellerhals +2
The problem of online buffer sharing is expressed as follows. A switch with output ports receives a stream of incoming packets. When an incoming packet is accepted by the switc…
A Learning-Augmented Overlay Network
Julien Dallot, Caio Caldeira, Arash Pourdamghani +2
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 re…
Learning Minimum Linear Arrangement of Cliques and Lines
Julien Dallot, Maciej Pacut, Marcin Bienkowski +2
In the well-known Minimum Linear Arrangement problem (MinLA), the goal is to arrange the nodes of an undirected graph into a permutation so that the total stretch of the edges is m…
Dependency-Aware Online Caching
Julien Dallot, Amirmehdi Jafari Fesharaki, Maciej Pacut +1
We consider a variant of the online caching problem where the items exhibit dependencies among each other: an item can reside in the cache only if all its dependent items are also…