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