cc 15(6): e4

Research Article

A Highly Concurrent Replicated Data Structure EAI Endorsed Transactions

Download376 downloads
  • @ARTICLE{10.4108/eai.21-12-2015.150820,
        author={Mumtaz Ahmad and Abdessamad Imine and Mahfoud Houari},
        title={A Highly Concurrent Replicated Data Structure EAI Endorsed Transactions},
        journal={EAI Endorsed Transactions on Collaborative Computing},
        volume={1},
        number={6},
        publisher={EAI},
        journal_a={CC},
        year={2015},
        month={12},
        keywords={collaborative editing, optimistic replication, concurrent data structures.},
        doi={10.4108/eai.21-12-2015.150820}
    }
    
  • Mumtaz Ahmad
    Abdessamad Imine
    Mahfoud Houari
    Year: 2015
    A Highly Concurrent Replicated Data Structure EAI Endorsed Transactions
    CC
    EAI
    DOI: 10.4108/eai.21-12-2015.150820
Mumtaz Ahmad1,*, Abdessamad Imine1, Mahfoud Houari2
  • 1: LORIA/INRIA, Nancy Grand Est, France
  • 2: Abou-Bekr Belkaïd Université, Tlemcen
*Contact email: mumtazzahmed@gmail.com

Abstract

Well defined concurrent replicated data structure is very important to design collaborative editing system, particularly, certain properties like out-of-order execution of concurrent operations and data convergence. In this paper, we introduce novel linear data structure based on unique identifier scheme required for indexed communication. These identifiers are real numbers holding specific pattern of precision. Based on the uniqueness and the total order of these identifiers, here, we present two concurrency control techniques to achieve high degree of concurrency according to strong and lazy happened-before relations. Our data structure preserves data convergence, yields better performance and avoids overheads as compared to existing approaches.