Erasure coding is a popular tool that have been widely used in various communications and networking systems. For example, Hybrid Automatic Repeat reQuest (HARQ) and Redundant Array of Independent Disks (RAID). As suggested by its name, the purpose of using erasure code has traditionally been to recover corrupted/lost data. In this talk, I will discuss two not-so-traditional applications of erasure coding.
In the first part, I will discuss a classic distributed fault-tolerant computing problem: the Byzantine Generals' problem (a.k.a. Byzantine consensus) and present an algorithm that solves this problem using erasure codes. The presented algorithm is perfectly secure (error-free) and costs only O(n) per input bit. All previously known perfectly secure algorithms cost at least O(n^2) per input bit.
In the second part, I will talk about how to use erasure coding to significantly improve the access delay of cloud storage systems and data centers. This problem is modeled by a novel queueing system, the operating points of which is the choice of erasure code for accessing data. A backlog-driven online adaptive scheme that achieves the optimal delay-throughput tradeoff will then be presented.