Survey of local algorithms
J Suomela - ACM Computing Surveys (CSUR), 2013 - dl.acm.org
A local algorithm is a distributed algorithm that runs in constant time, independently of the
size of the network. Being highly scalable and fault tolerant, such algorithms are ideal in the …
size of the network. Being highly scalable and fault tolerant, such algorithms are ideal in the …
Approximation ratios of graph neural networks for combinatorial problems
In this paper, from a theoretical perspective, we study how powerful graph neural networks
(GNNs) can be for learning approximation algorithms for combinatorial problems. To this …
(GNNs) can be for learning approximation algorithms for combinatorial problems. To this …
Quadratic and near-quadratic lower bounds for the CONGEST model
K Censor-Hillel, S Khoury, A Paz - arXiv preprint arXiv:1705.05646, 2017 - arxiv.org
We present the first super-linear lower bounds for natural graph problems in the CONGEST
model, answering a long-standing open question. Specifically, we show that any exact …
model, answering a long-standing open question. Specifically, we show that any exact …
Distributed assignment with limited communication for multi-robot multi-target tracking
We study the problem of tracking multiple moving targets using a team of mobile robots.
Each robot has a set of motion primitives to choose from in order to collectively maximize the …
Each robot has a set of motion primitives to choose from in order to collectively maximize the …
Weak models of distributed computing, with connections to modal logic
This work presents a classification of weak models of distributed computing. We focus on
deterministic distributed algorithms, and we study models of computing that are weaker …
deterministic distributed algorithms, and we study models of computing that are weaker …
Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks
M Åstrand, J Suomela - Proceedings of the twenty-second annual ACM …, 2010 - dl.acm.org
We present a distributed algorithm that finds a maximal edge packing in O (Δ+ log* W)
synchronous communication rounds in a weighted graph, independent of the number of …
synchronous communication rounds in a weighted graph, independent of the number of …
Smaller cuts, higher lower bounds
A Abboud, K Censor-Hillel, S Khoury… - ACM Transactions on …, 2021 - dl.acm.org
This article proves strong lower bounds for distributed computing in the congest model, by
presenting the bit-gadget: a new technique for constructing graphs with small cuts. The …
presenting the bit-gadget: a new technique for constructing graphs with small cuts. The …
Round compression for parallel graph algorithms in strongly sublinear space
K Onak - arXiv preprint arXiv:1807.08745, 2018 - arxiv.org
The Massive Parallel Computation (MPC) model is a theoretical framework for popular
parallel and distributed platforms such as MapReduce, Hadoop, or Spark. We consider the …
parallel and distributed platforms such as MapReduce, Hadoop, or Spark. We consider the …
A Distributed (2+ ε)-Approximation for Vertex Cover in O (log Δ/ε log log Δ) Rounds
R Bar-Yehuda, K Censor-Hillel… - Journal of the ACM …, 2017 - dl.acm.org
We present a simple deterministic distributed (2+ ε)-approximation algorithm for minimum-
weight vertex cover, which completes in O (log Δ/εlog log Δ) rounds, where Δ is the …
weight vertex cover, which completes in O (log Δ/εlog log Δ) rounds, where Δ is the …
Local algorithms: Self-stabilization on speed
Fault tolerance is one of the main concepts in distributed computing. It has been tackled from
different angles, eg by building replicated systems that can survive crash failures of …
different angles, eg by building replicated systems that can survive crash failures of …