Replicated Abstract Data Types and Log Version Vectors - Two Building Blocks for Replication.

Presenter: Hyun-Gul Roh, PhD at KAIST

Abstract. For distributed collaborative applications responsive and transparent interactivity is highly desired. Though such interactivity can be achieved with optimistic replication, maintaining replica consistency is difficult. To support efficient implementations of collaborative applications, we extend a few representative abstract data types (ADTs), such as arrays, hash tables, and growable arrays (or linked lists), into replicated abstract data types (RADTs). In RADTs, a shared ADT is replicated and modified with optimistic operations. Operation commutativity and precedence transitivity are two principles enabling RADTs to maintain consistency despite different execution orders. Especially, replicated growable arrays (RGAs) support insertion/deletion/update operations. Over previous approaches to the optimistic insertion and deletion, RGAs show significant improvement in performance, scalability, and reliability.

Documents: PDF

Date and Place

On November 16th, 2010

INRIA
23, avenue d'Italie
75013 Paris
Meeting will take place in Room Orange