Deterministic Fault-Tolerant Local Load Balancing and its Applications against Adaptive Adversaries
Abstract
Load balancing is among the basic primitives in distributed computing. In this paper, we consider this problem when executed locally on a network with nodes prone to failures. We show that there exist lightweight network topologies that are immune to message delivery failures incurred by (at most) a constant fraction of all nodes. More precisely, we design a novel deterministic fault-tolerant local load balancing (LLB) algorithm, which, similarly to their classical counterparts working in fault-free networks, has a relatively simple structure and guarantees exponentially fast convergence to the average value despite crash and omission failures.
Fields of Study & Subjects
Distributed systems and fault tolerance
Complexity and Algorithms in Graphs
Peer-to-Peer Network Technologies
Publication details
- Journal / source
- Proceedings of the 38th ACM Symposium on Parallelism in Algorithms and Architectures
- Publisher
- ACM
- Pages
- 167–179
- Publication date
- 6 July 2026
- Language
- EN