This paper presents a decentralized, accurate, and efficient method to find a cluster of Internet hosts, given the desired cluster size and minimum interconnection bandwidth. We describe a centralized polynomial time algorithm for a tree metric space, along with a proof of correctness. We then provide a decentralized version of the algorithm. Simulation experiments with two real-world datasets confirm that our clustering approach achieves high accuracy and scalability. We also discuss the costs of decentralization and how the treeness of the dataset affects clustering accuracy.

@inProceedings{icdcs11,
	title = "Searching for Bandwidth-Constrained Clusters",
	author = "Sukhyun Song and Peter J. Keleher and Alan Sussman",
	booktitle = { The 31st International Conference on Distributed Computing Systems (ICDCS 2011)},
	month = {April},
	year = {2011},
}