Coding for Computing

  Halls department, Hall 2
  Wednesday, 27 December 2017
  11:00 - 12:00


In this talk we focus on the role of coding in dealing with two major challenges of distributed computing, i.e. communication load and straggler servers. We demonstrate that the gain of coding scales with the size of the network and is essential to achieve the fundamental limits of processing and delivering big data.

In the first part, we consider a large-scale matrix multiplication problem where a single node cannot handle the computation, and this the computation is carried out using a distributed system multiple servers. The challenge is that if some of the servers are slow, the overall processing time will increase. We propose a coding technique that resolves this issue and achieves the optimum delay by introducing some algebraic coded redundancy in computation.

In the second part, we focus on a distributed computing framework, motivated by Map-Reduce and Spark, and characterize the computation--communication tradeoff. We show that to achieve this tradeoff we need to use some sort of coding. The gain of coding scales with the size of the network.