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.
