Tight Network Topology Dependent Bounds on Rounds of Communication

Preprint English OPEN
Chattopadhyay, Arkadev; Langberg, Michael; Li, Shi; Rudra, Atri;
  • Subject: Computer Science - Distributed, Parallel, and Cluster Computing | Computer Science - Computational Complexity

We prove tight network topology dependent bounds on the round complexity of computing well studied $k$-party functions such as set disjointness and element distinctness. Unlike the usual case in the CONGEST model in distributed computing, we fix the function and then va... View more
  • References (1)

    [DSHK+12] A. Das Sarma, S. Holzer, L. Kor, A. Korman, D. Nanongkai, G. Pandurangan, D. Peleg, and R. Wattenhofer. Distributed verification and hardness of distributed approximation. SIAM Journal on Computing, 41(5):1235-1265, 2012.

  • Metrics
Share - Bookmark