CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Block-Diagonal Coding for Distributed Computing With Straggling Servers

Albin Severinson (Institutionen för signaler och system) ; Alexandre Graell i Amat (Institutionen för elektroteknik) ; Eirik Rosnes
IEEE Information Theory Workshop (ITW) (2017)
[Konferensbidrag, refereegranskat]

We consider the distributed computing problem of multiplying a set of vectors with a matrix. For this scenario, Li et al. recently presented a unified coding framework and showed a fundamental tradeoff between computational delay and com- munication load. This coding framework is based on maximum distance separable (MDS) codes of code length proportional to the number of rows of the matrix, which can be very large. We propose a block-diagonal coding scheme consisting of partitioning the matrix into submatrices and encoding each submatrix using a shorter MDS code. We show that the assignment of coded matrix rows to servers to minimize the communication load can be formulated as an integer program with a nonlinear cost function, and propose an algorithm to solve it. We further prove that, up to a level of partitioning, the proposed scheme does not incur any loss in terms of computational delay (as defined by Li et al.) and communication load compared to the scheme by Li et al.. We also show numerically that, when the decoding time is also taken into account, the proposed scheme significantly lowers the overall computational delay with respect to the scheme by Li et al.. For heavy partitioning, this is achieved at the expense of a slight increase in communication load.

Den här publikationen ingår i följande styrkeområden:

Läs mer om Chalmers styrkeområden  

Denna post skapades 2017-09-29. Senast ändrad 2017-09-29.
CPL Pubid: 252124


Läs direkt!

Lokal fulltext (fritt tillgänglig)

Institutioner (Chalmers)

Institutionen för signaler och system (1900-2017)
Institutionen för elektroteknik


Informations- och kommunikationsteknik

Chalmers infrastruktur