Fusible Data Structures for Fault Tolerance
Background The use of replication-based approaches for server backup in distributed environments—in which an exact replica of the data on each server is made—is computationally efficient, but can create significant hardware demands.In other domains, such as disk storage, coding theory techniques are employed to recover data in the event of faults in a much more space-efficient method than that used in replication-based approaches. However, in applying these coding theory techniques to server backup, the computational requirements are substantial, making this approach impractical for applications with very large data sets.
Invention Description The subject invention is a new methodology, called "fusible data structures" for server backup in distributed processing environments, that enjoys the computational efficiency of replication-based approaches and the space efficiency of coding theory techniques. Through use of fusible data structures, data from several servers can be efficiently backed up using a fraction of the space required by replication-based approaches.
The methodology relies on specific algorithms developed for each unique form of data structure (e.g., sets, queues, stacks, arrays, hash tables, link lists), allowing for computational efficiency in backup. These algorithms create a new data structure, called the fused data structure, which is a fusion of the data in the multiple servers being backed up. If one server fails, it is recovered based on the information in the other production servers and the information in the fused data structure on the backup server.
Market Potential/Applications - Databases - Programming languages - Multithreaded systems - Embedded systems and sensor networks
Development Stage Proof of concept
IP Status One PCT patent application filed
UT Researcher Vijay K. Garg, Ph.D., Electrical and Computer Engineering, The University of Texas at Austin Vinit A. Ogale, Electrical and Computer Engineering, The University of Texas at Austin
Type of Offer: Licensing
« More Computer Science Patents