Combinatorics Seminar

When: Sunday, June 6, 10am Where: Schreiber 309 Speaker: Po-Shen Loh, CMU Title: Peer-to-peer clustering protocols

Abstract:

Suppose N individuals (clusters of size 1) need to rapidly coalesce into a single cluster, where the elementary operation is to merge two existing clusters. If these operations are allowed to occur in parallel, the fastest running time is of course logarithmic in N, because in each time step, the existing clusters could pair up perfectly, reducing their number by half. However, if one wishes to do this in a non-centralized manner, the above discussion conceals a critical implementation challenge: how should one determine the pairing assignments at each time step without a centralized index of the individuals?

In this talk, we analyze a randomized peer-to-peer clustering algorithm proposed by the Distributed Systems group at Microsoft Research, which empirically appeared to achieve the asymptotically optimal running time. We provide the first rigorous bounds on the performance of this and a related algorithm, extending an approach of Oded Schramm. Joint work with Eyal Lubetzky.