When Distributed Computation is Communication Expensive

Abstract

We consider a number of fundamental statistical and graph problems in the message-passing model, where we have $k$ machines (sites), each holding a piece of data, and the machines want to jointly solve a problem defined on the union of the $k$ data sets. The communication is point-to-point, and the goal is to minimize the total communication among the $k$ machines. This model captures all point-to-point distributed computational models with respect to minimizing communication costs. Our analysis shows that exact computation of many statistical and graph problems in this distributed setting requires a prohibitively large amount of communication, and often one cannot improve upon the communication of the simple protocol in which all machines send their data to a centralized server. Thus, in order to obtain protocols that are communication-efficient, one has to allow approximation, or investigate the distribution or layout of the data sets.

A few minor modifications are made. The new version also has a more appropriate title

References in corpus (2)

• Communication Steps for Parallel Query Processing
• Sorting, Searching, and Simulation in the MapReduce Framework

Cited by in corpus (7)

• Worst-Case Optimal Algorithms for Parallel Query Processing
• The Sketching Complexity of Graph Cuts
• Tribes Is Hard in the Message Passing Model
• On the Communication Complexity of Distributed Clustering
• On The Multiparty Communication Complexity of Testing Triangle-Freeness
• Batch Sparse Recovery, or How to Leverage the Average Sparsity
• The Range of Topological Effects on Communication