Login
Talks & Seminars
Title: Fault Tolerance in Distributed Systems: A Coding-Theoretic Approach
Mr. Bharath Balasubramanian, University of Texas at Austin
Date & Time: January 31, 2012 15:00
Venue: Conference Room, 01st Floor, C Block, Dept. of Computer Science & Engg., Kanwal Rekhi Bldg.
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 Profile:
Bharath is currently a doctoral candidate in the dept. of Computer Engineering at UT Austin working under the guidance of Prof. Vijay Garg in the area of distributed systems. More details available at http://pdsl.ece.utexas.edu/bharath/.
List of Talks

Webmail

Username:
Password:
Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback