9 papers
Supervised Distributed Computing: Efficiency and Robustness under a Majority of Adversarial Workers
John Augustine, Henning Hillebrandt, Manish Kumar +2
We consider a recently proposed \emph{supervised distributed computing} paradigm \cite{augustine2025supervised} that extends and refines the standard master-worker paradigm for par…
Logarithmic-Time Geodesically Convex Decomposition in Programmable Matter
Henning Hillebrandt, Andreas Padalkin, Christian Scheideler +2
The decomposition of complex structures into simpler substructures is a powerful technique with a wide range of applications. We study the computation of decompositions in the cont…
Simulations between Strongly Sublinear MPC and Node-Capacitated Clique
Philipp Schneider, Julian Werthmann
We study how the Massively Parallel Computation (MPC) model in the strongly sublinear regime relates to the classic, graph-centric distributed models, focusing on the Node-Capacita…
Supervised Distributed Computing
John Augustine, Christian Scheideler, Julian Werthmann
We introduce a new framework for distributed computing that extends and refines the standard master-worker approach of scheduling multi-threaded computations. In this framework, th…
Distributed And Parallel Low-Diameter Decompositions for Arbitrary and Restricted Graphs
Jinfeng Dou, Thorsten Götte, Henning Hillebrandt +2
We consider the distributed and parallel construction of low-diameter decompositions with strong diameter for (weighted) graphs and (weighted) graphs that can be separated through…
Distributed Construction of Near-Optimal Compact Routing Schemes for Planar Graphs
Jinfeng Dou, Thorsten Götte, Henning Hillebrandt +2
We consider the problem of computing compact routing tables for a (weighted) planar graph in the PRAM, CONGEST, and the novel HYBRID communication model. We present…
Routing Schemes for Hybrid Communication Networks
Sam Coy, Artur Czumaj, Christian Scheideler +2
We consider the problem of computing routing schemes in the model of distributed computing where nodes have access to two fundamentally different communication mo…
Beep-And-Sleep: Message and Energy Efficient Set Cover
Thorsten Götte, Christina Kolb, Christian Scheideler +1
We observe message-efficient distributed algorithms for the Set Cover problem. Given a ground set of elements and subsets of , we aim to find the minimal number of t…
Time-Optimal Construction of Overlay Networks
Thorsten Götte, Kristian Hinnenthal, Christian Scheideler +1
We show how to construct an overlay network of constant degree and diameter in time starting from an arbitrary weakly connected graph. We assume a synchrono…