Pulkit Grover (SONIC PI - CMU) ‘Codes for Distributed Computing’ Tutorial at ISIT 2017

Grover along with Viveck Cadambe of Penn State presented a tutorial that showcased the importance of information theory in today and tomorrow’s distributed computing systems via two fundamental and practically relevant applications. 1) Consistent shared memory emulation; 2) Distributed Processor Matrix-Vector Multiplications, and more generally, linear algebraic operations. For each application, they discussed (a) classical papers in computing methods for the appropriate task, (b) the current-state of the art in research and practice, and (c) how information theory can be applied to undertake a fundamental study of the performance, and improve it. Connections to practice were established via review of practical systems, models, and experimental results.

Consistent shared memory emulation is a well-known task in distributed computing with applications to modern cloud-based key value stores and computing systems. They reviewed the basic system model and definitions related to consistent shared memory emulation, and explained a famous shared memory emulation algorithm that used replication to build fault tolerance. They then described erasure coding based algorithms and a new information-theoretic framework that studies the storage cost incurred in shared memory emulation.

Matrix-vector products are the critical building block of modern computations such as machine-learning and inference problems, and massive simulations in basic science problems. These computations are often implemented in delay and fault-prone distributed computing systems. To address these, repetition and coding techniques (e.g. in Algorithm-Based Fault Tolerance, ABFT) have been studied by the distributed and parallel computing community since the 1980s. They reviewed relevant literature and discussed recent advances showing how an information-theoretic approach can improve the speed, reliability, and energy-efficiency of matrix-vector products and other linear algebraic operations. Fundamental limits and coding-theoretic achievabilities were also discussed for faults/delays at two levels: processor-level, and gate-level.

For more information IEEE International Symposium on Information Theory (ISIT) 2017, please visit https://isit2017.org/.