Technical Program

Paper Detail

Paper Title Universally Decodable Matrices for Distributed Matrix-Vector Multiplication
Paper IdentifierTH1.R2.1
Authors Aditya Ramamoorthy, Li Tang, Iowa State Univerisity, United States; Pascal Olivier Vontobel, The Chinese University of Hong Kong, Hong Kong SAR of China
Session Coded Computing II
Location Saint Germain, Level 3
Session Time Thursday, 11 July, 09:50 - 11:10
Presentation Time Thursday, 11 July, 09:50 - 10:10
Manuscript  Click here to download the manuscript
Abstract Coded computation is an emerging research area that leverages concepts from erasure coding to mitigate the effect of stragglers (slow nodes) in distributed computation clusters, especially for matrix computation problems. In this work, we present a class of distributed matrix-vector multiplication schemes that are based on codes in the Rosenbloom-Tsfasman metric and universally decodable matrices. Our schemes take into account the inherent computation order within a worker node. In particular, they allow us to effectively leverage partial computations performed by stragglers (a feature that many prior works lack). An additional main contribution of our work is a companion-matrix-based embedding of these codes that allows us to obtain sparse and numerically stable schemes for the problem at hand. Experimental results confirm the effectiveness of our techniques.