Fundamental Tradeoff between Computation and Communication in Distributed Computing

Table of Contents

1. Introduction

Distributed computing frameworks like MapReduce and Spark have revolutionized large-scale data processing, but they face a fundamental bottleneck: the communication load during data shuffling phase. This paper addresses the critical question of how to optimally trade extra computing power to reduce communication load in distributed computing systems.

The research demonstrates that computation and communication loads are inversely proportional to each other, establishing a fundamental tradeoff relationship. The proposed Coded Distributed Computing (CDC) framework shows that increasing computation load by a factor of r creates coding opportunities that reduce communication load by the same factor.

2. Fundamental Tradeoff Framework

2.1 System Model

The distributed computing framework consists of K computing nodes that process input data through Map and Reduce functions. Each node processes a subset of input files and generates intermediate values, which are then exchanged during the shuffling phase to compute final outputs.

2.2 Computation and Communication Loads

The computation load r is defined as the total number of Map function executions normalized by the number of input files. The communication load L is defined as the total amount of data (in bits) exchanged during shuffling normalized by the total size of intermediate values.

3. Coded Distributed Computing (CDC)

3.1 CDC Algorithm Design

The CDC scheme carefully designs the data placement and function assignment to create coded multicasting opportunities. By evaluating each Map function at r carefully chosen nodes, the scheme enables nodes to compute coded messages that are simultaneously useful for multiple recipients.

3.2 Mathematical Formulation

The key insight is that with computation load r, the communication load can be reduced to:

$$L(r) = \frac{1}{r} \left(1 - \frac{r}{K}\right)$$

This represents an inverse relationship where increasing r by a factor reduces L by the same factor, achieving the optimal tradeoff.

4. Theoretical Analysis

4.1 Information-Theoretic Lower Bound

The paper establishes an information-theoretic lower bound on the communication load:

$$L^*(r) \geq \frac{1}{r} \left(1 - \frac{r}{K}\right)$$

This bound is derived using cut-set arguments and information inequality techniques.

4.2 Optimality Proof

The CDC scheme achieves this lower bound exactly, proving its optimality. The proof involves showing that any scheme with computation load r must have communication load at least L*(r), and CDC achieves exactly this value.

5. Experimental Results

5.1 CodedTeraSort Implementation

The coding techniques were applied to the Hadoop TeraSort benchmark to develop CodedTeraSort. This implementation maintains the same API as standard TeraSort while incorporating CDC principles.

5.2 Performance Evaluation

Empirical results demonstrate that CodedTeraSort speeds up overall job execution by 1.97× to 3.39× for typical settings of interest. The performance improvement scales with the computation load parameter r.

6. Code Implementation

class CodedTeraSort {
    // Map Phase with computation load r
    void map(InputSplit split) {
        for (int i = 0; i < r; i++) {
            // Process subset of data with coding
            intermediateValues = processWithCoding(split, i);
        }
    }
    
    // Shuffle Phase with coded communication
    void shuffle() {
        // Generate coded messages instead of raw data
        codedMessages = generateCodedMessages(intermediateValues);
        broadcast(codedMessages);
    }
    
    // Reduce Phase with decoding
    void reduce(CodedMessage[] messages) {
        // Decode to get required intermediate values
        decodedValues = decode(messages);
        // Perform reduction
        output = performReduction(decodedValues);
    }
}

7. Future Applications

The CDC framework has significant implications for various distributed computing domains:

• Machine Learning: Distributed training of large neural networks with reduced communication overhead
• Edge Computing: Efficient computation in bandwidth-constrained environments
• Federated Learning: Privacy-preserving distributed model training
• Stream Processing: Real-time data processing with optimized resource utilization

8. References

1. Li, S., Maddah-Ali, M. A., Yu, Q., & Avestimehr, A. S. (2017). A Fundamental Tradeoff between Computation and Communication in Distributed Computing. IEEE Transactions on Information Theory.
2. Dean, J., & Ghemawat, S. (2008). MapReduce: Simplified data processing on large clusters. Communications of the ACM.
3. Zaharia, M., et al. (2016). Apache Spark: A unified engine for big data processing. Communications of the ACM.
4. Isard, M., et al. (2007). Dryad: distributed data-parallel programs from sequential building blocks. ACM SIGOPS.
5. Apache Hadoop. (2023). Hadoop TeraSort Benchmark Documentation.