Robust Distributed Clustering With Redundant Data Assignment
- 29 January 2025
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 71 (4) , 2888-2908
Abstract
In this work, we present distributed clustering algorithms that can handle large-scale data across multiple machines in the presence of faulty machines. These faulty machines can either be straggling machines that fail to respond within a stipulated time or Byzantines that send arbitrary responses. We propose redundant data assignment schemes that enable us to obtain clustering solutions based on the entire dataset, even when some machines are stragglers or adversarial in nature. Our proposed robust clustering algorithms generate a constant factor approximate solution in the presence of stragglers or Byzantines. We also provide various constructions of the data assignment scheme that provide resilience against a large fraction of faulty machines. Simulation results show that the distributed algorithms based on the proposed assignment scheme provide good-quality solutions for a variety of clustering problems.Keywords
Funding Information
- National Science Foundation (2112665, 2217058)
This publication has 33 references indexed in Scilit:
- The Power of Uniform Sampling for Coresets2022
- Gradient Coding with Dynamic Clustering for Straggler Mitigation2021
- Data Encoding Methods for Byzantine-Resilient Distributed Optimization2019
- Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension2018
- Lifts, Discrepancy and Nearly Optimal Spectral Gap*Combinatorica, 2006
- Expander graphs and their applicationsBulletin of the American Mathematical Society, 2006
- Iterative shrinking method for clustering problemsPattern Recognition, 2006
- A Simple Linear Time (1+ ∊) -Approximation Algorithm for k-Means Clustering in Any Dimensions2004
- BIRCH: A New Data Clustering Algorithm and Its ApplicationsData Mining and Knowledge Discovery, 1997
- Clustering to minimize the maximum intercluster distanceTheoretical Computer Science, 1985