Tata Institute of Fundamental Research
Fault Tolerance in Distributed Systems: A Coding-Theoretic Approach
Seminar
Speaker:
Bharath B.
The University of Texas at Austin
Electrical and Computer Engineering
1 University Station C0803
Austin, TX 78712
United States of America
Organiser:
John Barretto
Date:
Monday, 6 Feb 2012, 16:00 to 17:00
Venue:
AG-66 (Lecture Theatre)
(Scan to add to calendar)
Abstract:
Distributed systems are rapidly increasing in importance due to the need for scalable computation on huge volumes of data. This fact is reflected in many distributed applications such as Amazon’s cloud computing service, Google’s BigTable or Apache’s Hadoop framework. Replication is the prevalent solution for fault tolerance in these systems. This solution, though simple, is wasteful in terms of both the space and infrastructure costs required to host the backups. We present a new paradigm to solve this problem, broadly referred to as fusion, that combines the operational efficiency of replication with the space efficiency of coding theory. To make our techniques generally applicable, we describe fusion in two separate contexts: finite state machines and infinite state machines.
For finite state machines, we present a polynomial time algorithm to generate efficient backup machines. For infinite state machines, we consider programs that host large data structures such as linked lists, stacks, vectors and maps. Using a combination of erasure codes and selective replication, we present an algorithm to generate efficient backup data structures. We prove the minimality of our schemes and also provide experimental results that confirm the same. Finally, we present a fusion-based design for fault tolerance in two real world applications: Amazon’s key-value store, Dynamo, and Google's Map Reduce framework, that is much more efficient than the current replication-based approach.
| Speaker: | Bharath B. The University of Texas at Austin Electrical and Computer Engineering 1 University Station C0803 Austin, TX 78712 United States of America |
| Organiser: | John Barretto |
| Date: | Monday, 6 Feb 2012, 16:00 to 17:00 |
| Venue: | AG-66 (Lecture Theatre) |
(Scan to add to calendar)
Abstract:
Distributed systems are rapidly increasing in importance due to the need for scalable computation on huge volumes of data. This fact is reflected in many distributed applications such as Amazon’s cloud computing service, Google’s BigTable or Apache’s Hadoop framework. Replication is the prevalent solution for fault tolerance in these systems. This solution, though simple, is wasteful in terms of both the space and infrastructure costs required to host the backups. We present a new paradigm to solve this problem, broadly referred to as fusion, that combines the operational efficiency of replication with the space efficiency of coding theory. To make our techniques generally applicable, we describe fusion in two separate contexts: finite state machines and infinite state machines.
For finite state machines, we present a polynomial time algorithm to generate efficient backup machines. For infinite state machines, we consider programs that host large data structures such as linked lists, stacks, vectors and maps. Using a combination of erasure codes and selective replication, we present an algorithm to generate efficient backup data structures. We prove the minimality of our schemes and also provide experimental results that confirm the same. Finally, we present a fusion-based design for fault tolerance in two real world applications: Amazon’s key-value store, Dynamo, and Google's Map Reduce framework, that is much more efficient than the current replication-based approach.
For finite state machines, we present a polynomial time algorithm to generate efficient backup machines. For infinite state machines, we consider programs that host large data structures such as linked lists, stacks, vectors and maps. Using a combination of erasure codes and selective replication, we present an algorithm to generate efficient backup data structures. We prove the minimality of our schemes and also provide experimental results that confirm the same. Finally, we present a fusion-based design for fault tolerance in two real world applications: Amazon’s key-value store, Dynamo, and Google's Map Reduce framework, that is much more efficient than the current replication-based approach.