4 March 2026 in SSRN Electronic Journal
In this paper, we present distributed fault-tolerant algorithms that approximate the centroid (i.e., the average) of a set of n data points in R d . Our work falls into the broader area of multidimensional Byzantine approximate agreement. We show that state-of-the-art algorithms, such as agreeing inside the convex hull of all non-faulty vectors, or minimum-diameter averaging (MDA), in the worst case either prevent us from agreeing on a vector close to the centroid (in terms of approximation quality), or allow Byzantine parties to influence the output considerably (in terms of validity). To design better approximation algorithms, we propose a novel concept of defining an approximation ratio of the centroid by including the vectors of the Byzantine adversaries in the definition. We analyze the algorithms in the synchronous and asynchronous models of communication with public communication channels. We show that the standard agreement algorithms based on agreeing inside the convex hull of all non-faulty vectors do not allow us to compute a better approximation than 2d of the centroid. On the other hand, MDA can be used to achieve constant approximation at the cost of only satisfying strong validity. As a trade-off, we develop an approach that reaches a 2 √ d-approximation of the centroid, while satisfying box validity. Our approach provides optimal resilience, allowing up to t < n/3 faulty nodes.
14 September 2021 in arXiv
In this work we introduce the graph-theoretic notion of mendability: for each locally checkable graph problem we can define its mending radius, which captures the idea of how far one needs to modify a partial solution in order to "patch a hole." We explore how mendability is connected to the existence of efficient algorithms, especially in distributed, parallel, and fault-tolerant settings. It is easy to see that $O(1)$-mendable problems are also solvable in $O(\log^* n)$ rounds in the LOCAL model of distributed computing. One of the surprises is that in paths and cycles, a converse also holds in the following sense: if a problem $\Pi$ can be solved in $O(\log^* n)$, there is always a restriction $\Pi' \subseteq \Pi$ that is still efficiently solvable but that is also $O(1)$-mendable. We also explore the structure of the landscape of mendability. For example, we show that in trees, the mending radius of any locally checkable problem is $O(1)$, $\Theta(\log n)$, or $\Theta(n)$, while in general graphs the structure is much more diverse.