Erasure Coding Makes Distributed Systems Efficient -- in a not-so traditional way

Wednesday, October 16, 2013
7:00 PM
POB 5.444
Free and open to the public

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.

x x


Guanfeng Liang

Guanfeng Liang

Research Engineer
DOCOMO Innovations Inc.

Since 2012, Guanfeng Liang has been a research engineer at DOCOMO Innovations Inc. (formerly known as DOCOMO Communication Laboratory USA), which is a subsidiary of NTT DOCOMO, Inc. in Japan. He received a PhD in ECE from University of Illinois at Urbana-Champaign in 2012, a M.A.Sc in ECE from University of Toronto, Canada in 2007 and a B.A from University of Science and Technology of China in 2004. His research interests include distributed algorithms (especially fault-tolerance), cloud computing, and network coding.