Sampling and Output Estimation in Distributed Algorithms and LCAs
Leonid Barenboim, Tzalik Maimon · 2020
We consider the distributed message-passing model and the Local Computational Algorithms (LCA) model. In both models a network is represented by an n-vertex graph G = (V, E). We focus on labeling problems, such as vertex-coloring, edge-coloring, maximal independent set (MIS) and maximal matching. In the distributed model the vertices of v perform computations in parallel, in order to compute their parts in the solution for G. In the LCA model, on the other hand, probes are performed on certain vertices in order to compute their labels in a solution to a given problem. We study the possibility of estimating a solution produced by an algorithm, much before the algorithm terminates. This estimation not only allows for size estimation of a solution, but also for an early detection of failure in randomized algorithms, so that a correcting procedure can be executed. To this end, we propose a sampling technique, in which the labels in the sampling are distributed proportionally to the distribution in the algorithm’s output. However, the sampling running time is significantly smaller than that of the algorithm in hand.