UTCS Colloquium: Jay Wylie HP Labs Determining fault tolerance of XOR-based erasure codes efficiently ACES 6.304 Wednesday April 18 2007 at 2:00 p.m.

Contact Name: 
Jenna Whitney
Date: 
Apr 18, 2007 2:00pm - 3:00pm

There is a signup schedule for this event.

Speaker Name/Affi

liation: Jay Wylie/HP Labs

Date/Time: Wednesday April 18 2007 a

t 2:00p.m.

Location: ACES 6.304

Host: Lorenzo Alvisi

Talk Title: Determining fault tolerance of XOR-based erasure codes effici

ently

Talk Abstract:
XOR-based erasure codes have had a tremendou

s impact on
networked systems in the recent past. For example LDPC cod

es
digital fountain codes and rateless erasure codes have all been
deployed in P2P systems and streaming multicast systems. The
impact of

such codes on clustered storage systems has not yet been
felt. Replicati

on and RAID continue to dominate clustered storage
systems. We believe t

hat a clear understanding of XOR-based
erasure codes applicable to clust

ered storage systems rather than
networked systems will facilitate the

ir adoption in clustered storage
systems.

Towards this end we p

ropose a new fault tolerance metric for
XOR-based erasure codes: the min

imal erasures list (MEL). A
minimal erasure is a set of erasures that le

ads to irrecoverable
data loss and in which every erasure is necessary

and sufficient
for this to be so. The MEL is the enumeration of all min

imal erasures.
The MEL completely describes the fault tolerance of anXOR-based erasure code at and beyond its Hamming distance; it
is the

refore a useful metric for comparing the fault tolerance of
such codes.

We also propose an algorithm that efficiently
determines the MEL of an e

rasure code. We use the proposed
algorithm to identify the most fault to

lerant XOR-based erasure
code for all possible systematic erasure codes

with up to seven
data symbols and up to seven parity symbols. These cod

es are
directly applicable in clustered storage systems today.

Sp

eaker Bio:
Jay J. Wylie is a Research Scientist in the Storage Systems D

epartment
at Hewlett-Packard Labs. He received his Ph.D. and M.S. degree

s in
Computer Engineering from Carnegie Mellon University in 2005 and 20

00
respectively. He received his B.A.Sc. in Systems Design Engineering f

rom
the University of Waterloo in 1998. Jay''s interests are distributed
systems
storage systems erasure codes (Byzantine) fault-tolerance a

nd
dependability. Jay can be reached by email at jay.wylie%40hp.com