Credence: Algorithm Based Fault Tolerance at Datacenter Scale

As an increasing number of modern big data systems utilize horizontal scaling,the general trend in the distributed systems world has been to use general purposecom- modity hardware to reduce capital expenditure. System failures resulting fromthe use of inferior hardware have therefore become common at scale. Further, congesteddatacenter networks can result in high communication latencies and packetdrops at network switches. Coded computing is a novel computing technique basedon error correcting codes that aims to achieve algorithm based fault tolerance in adistributed system that is composed of unreliable compute nodes and networks. Inthis thesis, we explore the application of coded computing techniques to the problemof distributed matrix multiplication. Matrix multiplication is foundational to anumber of applications today ranging from machine learning to scientic computing.We discuss some applications of coded matrix multiplication and then discussthe design and implementation of a Mesos framework that utilizes coded computingfor distributed matrix multiplication and the methodology used to evaluate it. Finally,we discuss a novel scheduling strategy to minimize the latency of coded matrixmultiplication jobs.