In this work, we focus on designing an efficient Local Computation Algorithm (LCA) for the set cover problem, which is a core optimization task. The state-of-the-art LCA for computing O(logΔ)-approximate set cover, developed by Grunau, Mitrović, Rubinfeld, and Vakilian [SODA ’20], achieves query complexity of ΔO(logΔ) · fO(logΔ · (loglogΔ + loglogf)), where Δ is the maximum set size, and f is the maximum frequency of any element in sets. We present a new LCA that solves this problem using fO(logΔ) queries. Specifically, for instances where f = poly logΔ, our algorithm improves the query complexity from ΔO(logΔ) to ΔO(loglogΔ).

We study the allocation problem in the Massively Parallel Computation (MPC) model. This problem is a special case of b-matching in which the input is a bipartite graph with capacities greater than 1 in only one part of the bipartition. We give a (1 + ϵ) approximate algorithm for the problem, which runs in Õ (√long λ) MPC rounds, using sublinear space per machine and Õ (λn) total space, where λ is the arboricity of the input graph. Our result is obtained by providing a new analysis of a LOCAL algorithm by Agrawal, Zadimoghaddam, and Mirrokni [ICML 2018], which improves its round complexity from O (log n) to O (log λ). Prior to our work, no o (log n) round algorithm for constant-approximate allocation was known in either LOCAL or sublinear space MPC models for graphs with low arboricity.

We study a framework for modeling distributed network systems assisted by a reliable and powerful cloud service. Our framework aims at capturing hybrid systems based on a point to point message passing network of machines, with the additional capability of being able to access the services of a trusted high-performance external entity (the cloud). We focus on one concrete aspect that was not studied before, namely, ways of utilizing the cloud assistance in order to attain increased resilience against Byzantine behavior of machines in the network. Our network is modeled as a congested clique comprising $k$ machines that are completely connected to form a clique and can communicate with each other by passing small messages. In every execution, up to $βk$ machines (for suitable values of $β\in [0, 1)$) are allowed to be Byzantine, i.e., behave maliciously including colluding with each other, with the remaining $γk$ or more machines being \emph{honest} (for $γ=1-β$). Additionally, the machines in our congested clique can access data through a trusted cloud via queries. This externality of the data captures many real-world distributed computing scenarios and provides a natural context for exploring Byzantine resilience for essentially all conceivable problems. Moreover, we are no longer bound by the usual limits of $β< 1/3$ or even $β< 1/2$ that are typically seen in Byzantine Agreement. We focus on a few fundamental problems. We start with the ${\textsf{Download}}$ problem, wherein the cloud stores $n$ bits and these $n$ bits must be downloaded to all of the $k$ machines. In addition to ${\textsf{Download}}$, we also consider the problem of computing the ${\textsf{Disjunction}}$ and ${\textsf{Parity}}$ of the bits in the cloud. We study these problems under several settings comprising various $β$ values and adversarial capabilities.

The paper considers the SUPPORTED model of distributed computing introduced by Schmid and Suomela [HotSDN'13], generalizing the LOCAL and CONGEST models. In this framework, multiple instances of the same problem, differing from each other by the subnetwork to which they apply, recur over time, and need to be solved efficiently online. To do that, one may rely on an initial preprocessing phase for computing some useful information. This preprocessing phase makes it possible, in some cases, to overcome locality-based time lower bounds. A first contribution of the current paper is expanding the spectrum of problem types to which the SUPPORTED model applies. In addition to subnetwork-defined recurrent problems, we introduce also recurrent problems of two additional types: (i) instances defined by partial client sets, and (ii) instances defined by partially fixed outputs. Our second contribution is illustrating the versatility of the SUPPORTED framework by examining recurrent variants of three classical graph problems. The first problem is Minimum Client Dominating Set (CDS), a recurrent version of the classical dominating set problem with each recurrent instance requiring us to dominate a partial client set. We provide a constant time approximation scheme for CDS on trees and planar graphs. The second problem is Color Completion (CC), a recurrent version of the coloring problem in which each recurrent instance comes with a partially fixed coloring (of some of the vertices) that must be completed. We study the minimum number of new colors and the minimum total number of colors necessary for completing this task. The third problem we study is a recurrent version of Locally Checkable Labellings (LCL) on paths of length $n$. We show that such problems have complexities that are either $Θ(1)$ or $Θ(n)$, extending the results of Foerster et al. [INFOCOM'19].

We study the SUPPORTED model of distributed computing introduced by Schmid and Suomela [15], generalizing the LOCAL and CONGEST models. In this framework, multiple instances of the same problem, differing from each other by some problem specific input, recur over time, and need to be solved efficiently online. To do that, one may rely on an initial preprocessing phase for computing some useful information. This preprocessing phase makes it possible, in some cases, to obtain improved distributed algorithms, overcoming locality-based time lower bounds.