The Experts below are selected from a list of 21 Experts worldwide ranked by ideXlab platform

Sathiya Prabhu Kumar - One of the best experts on this subject based on the ideXlab platform.

  • Adaptive Consistency Protocols for Replicated Data in Modern Storage Systems with a High Degree of Elasticity
    2016
    Co-Authors: Sathiya Prabhu Kumar
    Abstract:

    The main contributions of this thesis are three folds. The first contribution of the thesis focuses on an efficient way to control stale reads in modern database systems with the help of a new consistency protocol called LibRe. LibRe is an acronym for Library for Replication. The main goal of the LibRe protocol is to ensure data consistency by contacting a minimum number of replica nodes during read and write operations with the help of a library information. According to the protocol, during write operations each replica node updates a registry (library) asynchronously with the recent version identifier of the updated data. Forwarding the read requests to a right replica node referring the registry information helps to control stale reads during read operations. Evaluation of data consistency remains challenging both via simulation as well as in a real world setup. Hence, we implemented a new simulation toolkit called Simizer that helps to evaluate the performance of different consistency policies in a fast and efficient way. We also extended an existing benchmark tool YCSB that helps to evaluate the consistency-latency tradeoff offered by modern database systems. The codebase of the simulator and the extended YCSB are made open-source for public access. The performance of the LibRe protocol is validated both via simulation as well as in a real setup with the help of extended YCSB.Although the modern database systems adapt the consistency guarantees of the system per query basis, anticipating the consistency level of an application query in advance during application development time remains challenging for the application developers. In order to overcome this limitation, the second contribution of the thesis focuses on enabling the database system to override the application-defined consistency options during run time with the help of an external input. The external input could be given by a data administrator or by an external service. The thesis validates the proposed model with the help of a prototype implementation inside the Cassandra distributed storage system.The third contribution of the thesis focuses on resolving update conflicts. Resolving update conflicts often involve maintaining all possible values and perform the resolution via domain-specific knowledge at the client side. This involves additional cost in terms of network bandwidth and latency, and considerable complexity. In this thesis, we discuss the motivation and design of a novel data type called Priority Register that implements a domain-specific conflict detection and resolution scheme directly at the database side, while leaving open the option of additional reconciliation at the application level. Our approach uses the notion of an application-defined replacement ordering and we show that a data type parameterized by such an order can provide an efficient solution for applications that demand domain-specific conflict resolution. We also describe the proof of concept implementation of the Priority Register inside Cassandra. The conclusion and perspectives of the thesis work are summarized at the end.

  • Priority Register: Application-defined replacement orderings for ad hoc reconciliation
    2015 IEEE International Conference on Big Data (Big Data), 2015
    Co-Authors: Sathiya Prabhu Kumar, Sylvain Lefebvre, Mark Oliver Stehr
    Abstract:

    Reconciliation of replicated data objects is tedious and error-prone in eventually consistent systems. Syntactic reconciliation techniques use serializability or causality as the basis for conflict-detection and resolution. These techniques are fast and efficient and the resolutions can be directly managed at the database side. However, for use cases where conflict resolution demands knowledge of the application semantics, domain-specific semantic reconciliation is required. Semantic reconciliation techniques often involve maintaining all possible values and perform the resolution via domain-specific knowledge at the client side. This involves additional cost in terms of network bandwidth and latency, and considerable complexity. In this paper, we discuss the motivation and design of a novel data type called Priority Register that implements a domain-specific conflict detection and resolution scheme directly at the database side, while leaving open the option of additional reconciliation at the application level. Our approach uses the notion of an application-defined replacement ordering and we show that a data type parameterized by such an order can provide an efficient solution for applications that demand domain-specific conflict resolution. We also describe the proof-of-concept implementation of the Priority Register inside the Cassandra distributed storage system.

  • Big Data - Priority Register: Application-defined replacement orderings for ad hoc reconciliation
    2015 IEEE International Conference on Big Data (Big Data), 2015
    Co-Authors: Sathiya Prabhu Kumar, Sylvain Lefebvre, Minyoung Kim, Mark Oliver Stehr
    Abstract:

    Reconciliation of replicated data objects is tedious and error-prone in eventually consistent systems. Syntactic reconciliation techniques use serializability or causality as the basis for conflict-detection and resolution. These techniques are fast and efficient and the resolutions can be directly managed at the database side. However, for use cases where conflict resolution demands knowledge of the application semantics, domain-specific semantic reconciliation is required. Semantic reconciliation techniques often involve maintaining all possible values and perform the resolution via domain-specific knowledge at the client side. This involves additional cost in terms of network bandwidth and latency, and considerable complexity. In this paper, we discuss the motivation and design of a novel data type called Priority Register that implements a domain-specific conflict detection and resolution scheme directly at the database side, while leaving open the option of additional reconciliation at the application level. Our approach uses the notion of an application-defined replacement ordering and we show that a data type parameterized by such an order can provide an efficient solution for applications that demand domain-specific conflict resolution. We also describe the proof-of-concept implementation of the Priority Register inside the Cassandra distributed storage system.

Mark Oliver Stehr - One of the best experts on this subject based on the ideXlab platform.

  • Priority Register: Application-defined replacement orderings for ad hoc reconciliation
    2015 IEEE International Conference on Big Data (Big Data), 2015
    Co-Authors: Sathiya Prabhu Kumar, Sylvain Lefebvre, Mark Oliver Stehr
    Abstract:

    Reconciliation of replicated data objects is tedious and error-prone in eventually consistent systems. Syntactic reconciliation techniques use serializability or causality as the basis for conflict-detection and resolution. These techniques are fast and efficient and the resolutions can be directly managed at the database side. However, for use cases where conflict resolution demands knowledge of the application semantics, domain-specific semantic reconciliation is required. Semantic reconciliation techniques often involve maintaining all possible values and perform the resolution via domain-specific knowledge at the client side. This involves additional cost in terms of network bandwidth and latency, and considerable complexity. In this paper, we discuss the motivation and design of a novel data type called Priority Register that implements a domain-specific conflict detection and resolution scheme directly at the database side, while leaving open the option of additional reconciliation at the application level. Our approach uses the notion of an application-defined replacement ordering and we show that a data type parameterized by such an order can provide an efficient solution for applications that demand domain-specific conflict resolution. We also describe the proof-of-concept implementation of the Priority Register inside the Cassandra distributed storage system.

  • Big Data - Priority Register: Application-defined replacement orderings for ad hoc reconciliation
    2015 IEEE International Conference on Big Data (Big Data), 2015
    Co-Authors: Sathiya Prabhu Kumar, Sylvain Lefebvre, Minyoung Kim, Mark Oliver Stehr
    Abstract:

    Reconciliation of replicated data objects is tedious and error-prone in eventually consistent systems. Syntactic reconciliation techniques use serializability or causality as the basis for conflict-detection and resolution. These techniques are fast and efficient and the resolutions can be directly managed at the database side. However, for use cases where conflict resolution demands knowledge of the application semantics, domain-specific semantic reconciliation is required. Semantic reconciliation techniques often involve maintaining all possible values and perform the resolution via domain-specific knowledge at the client side. This involves additional cost in terms of network bandwidth and latency, and considerable complexity. In this paper, we discuss the motivation and design of a novel data type called Priority Register that implements a domain-specific conflict detection and resolution scheme directly at the database side, while leaving open the option of additional reconciliation at the application level. Our approach uses the notion of an application-defined replacement ordering and we show that a data type parameterized by such an order can provide an efficient solution for applications that demand domain-specific conflict resolution. We also describe the proof-of-concept implementation of the Priority Register inside the Cassandra distributed storage system.

Zhiying Wang - One of the best experts on this subject based on the ideXlab platform.

  • A Cache Coherence Protocol Using Distributed Data Dependence Violation Checking in TLS
    2013 Third International Conference on Intelligent System Design and Engineering Applications, 2013
    Co-Authors: Xin Lai, Cong Liu, Zhiying Wang, Quanyou Feng
    Abstract:

    Current hardware implementations of TLS (thread-level speculation) in both Hydra and Renau's SESC simulator use a global component to check data dependence violations, e.g. L2 Cache or hardware list. Frequent memory accesses cause global component bottlenecks. Implementation and verification of the global component dramatically slows the processor's frequency. In this paper, we propose a cache coherence protocol using a distributed data dependence violation checking mechanism for TLS. The proposed protocol extends the current MESI cache coherence protocol by including several methods to exceed the present limits of centralized violation checking methods. In order not to broadcast every exposed write to the snooping bus, the protocol adds an invalidation vector to each private L1 cache to record threads that violate RAW data dependence. It also adds a versioning Priority Register that compares data versions. Added to each private L1 cache block is a snooping bit which indicates whether the thread possesses a bus snooping right for the block. The L1 Cache gets a bus snooping right when setting snooping bit. The L1 Cache catches exposed read miss whose address matching cache block address field. If a read miss from a remote core with a lower versioning Priority, the L1 Cache updates the invalidation vector according to the core ID on the bus. If TLS runtime is going to commit or invalidate a thread, then L1 Cache invalidates threads whose bits have been set in the invalidation vector and changes any cache blocks to a corresponding non-speculative state. In order to implement the proposed protocol, we modified the SESC simulator, which is an open-source cycle-accurate simulator, to confirm its correctness and analyze its performance.

  • EMS - Applying Formal Verification to a Cache Coherence Protocol in TLS
    2011 UKSim 5th European Symposium on Computer Modeling and Simulation, 2011
    Co-Authors: Xin Lai, Cong Liu, Zhiying Wang
    Abstract:

    Current hardware implementations of TLS (thread-level speculation) in both Hydra and Renau's SESC simulator use a global component to check data dependence violations, e.g. L2 Cache or hardware list. Frequent memory accesses cause global component bottlenecks. In this paper, we propose a cache coherence protocol using a distributed data dependence violation checking mechanism for TLS. The proposed protocol extends the traditional MESI cache coherence protocol by including several methods to exceed the present limits of centralized violation checking methods. The protocol adds an invalidation vector to each private L1 cache to record threads that violate RAW data dependence. It also adds a versioning Priority Register that compares data versions. Added to each private L1 cache block is a snooping bit which indicates whether the thread possesses a bus snooping right for the block. The proposed protocol is much more complicated than the traditional MESI protocol and hard to be completely verified only through simulation. So we applied formal verification to the proposed cache protocol to confirm its correctness. The verification result shows that the proposed protocol will function correctly in TLS system.

Sylvain Lefebvre - One of the best experts on this subject based on the ideXlab platform.

  • Priority Register: Application-defined replacement orderings for ad hoc reconciliation
    2015 IEEE International Conference on Big Data (Big Data), 2015
    Co-Authors: Sathiya Prabhu Kumar, Sylvain Lefebvre, Mark Oliver Stehr
    Abstract:

    Reconciliation of replicated data objects is tedious and error-prone in eventually consistent systems. Syntactic reconciliation techniques use serializability or causality as the basis for conflict-detection and resolution. These techniques are fast and efficient and the resolutions can be directly managed at the database side. However, for use cases where conflict resolution demands knowledge of the application semantics, domain-specific semantic reconciliation is required. Semantic reconciliation techniques often involve maintaining all possible values and perform the resolution via domain-specific knowledge at the client side. This involves additional cost in terms of network bandwidth and latency, and considerable complexity. In this paper, we discuss the motivation and design of a novel data type called Priority Register that implements a domain-specific conflict detection and resolution scheme directly at the database side, while leaving open the option of additional reconciliation at the application level. Our approach uses the notion of an application-defined replacement ordering and we show that a data type parameterized by such an order can provide an efficient solution for applications that demand domain-specific conflict resolution. We also describe the proof-of-concept implementation of the Priority Register inside the Cassandra distributed storage system.

  • Big Data - Priority Register: Application-defined replacement orderings for ad hoc reconciliation
    2015 IEEE International Conference on Big Data (Big Data), 2015
    Co-Authors: Sathiya Prabhu Kumar, Sylvain Lefebvre, Minyoung Kim, Mark Oliver Stehr
    Abstract:

    Reconciliation of replicated data objects is tedious and error-prone in eventually consistent systems. Syntactic reconciliation techniques use serializability or causality as the basis for conflict-detection and resolution. These techniques are fast and efficient and the resolutions can be directly managed at the database side. However, for use cases where conflict resolution demands knowledge of the application semantics, domain-specific semantic reconciliation is required. Semantic reconciliation techniques often involve maintaining all possible values and perform the resolution via domain-specific knowledge at the client side. This involves additional cost in terms of network bandwidth and latency, and considerable complexity. In this paper, we discuss the motivation and design of a novel data type called Priority Register that implements a domain-specific conflict detection and resolution scheme directly at the database side, while leaving open the option of additional reconciliation at the application level. Our approach uses the notion of an application-defined replacement ordering and we show that a data type parameterized by such an order can provide an efficient solution for applications that demand domain-specific conflict resolution. We also describe the proof-of-concept implementation of the Priority Register inside the Cassandra distributed storage system.

Xin Lai - One of the best experts on this subject based on the ideXlab platform.

  • A Cache Coherence Protocol Using Distributed Data Dependence Violation Checking in TLS
    2013 Third International Conference on Intelligent System Design and Engineering Applications, 2013
    Co-Authors: Xin Lai, Cong Liu, Zhiying Wang, Quanyou Feng
    Abstract:

    Current hardware implementations of TLS (thread-level speculation) in both Hydra and Renau's SESC simulator use a global component to check data dependence violations, e.g. L2 Cache or hardware list. Frequent memory accesses cause global component bottlenecks. Implementation and verification of the global component dramatically slows the processor's frequency. In this paper, we propose a cache coherence protocol using a distributed data dependence violation checking mechanism for TLS. The proposed protocol extends the current MESI cache coherence protocol by including several methods to exceed the present limits of centralized violation checking methods. In order not to broadcast every exposed write to the snooping bus, the protocol adds an invalidation vector to each private L1 cache to record threads that violate RAW data dependence. It also adds a versioning Priority Register that compares data versions. Added to each private L1 cache block is a snooping bit which indicates whether the thread possesses a bus snooping right for the block. The L1 Cache gets a bus snooping right when setting snooping bit. The L1 Cache catches exposed read miss whose address matching cache block address field. If a read miss from a remote core with a lower versioning Priority, the L1 Cache updates the invalidation vector according to the core ID on the bus. If TLS runtime is going to commit or invalidate a thread, then L1 Cache invalidates threads whose bits have been set in the invalidation vector and changes any cache blocks to a corresponding non-speculative state. In order to implement the proposed protocol, we modified the SESC simulator, which is an open-source cycle-accurate simulator, to confirm its correctness and analyze its performance.

  • EMS - Applying Formal Verification to a Cache Coherence Protocol in TLS
    2011 UKSim 5th European Symposium on Computer Modeling and Simulation, 2011
    Co-Authors: Xin Lai, Cong Liu, Zhiying Wang
    Abstract:

    Current hardware implementations of TLS (thread-level speculation) in both Hydra and Renau's SESC simulator use a global component to check data dependence violations, e.g. L2 Cache or hardware list. Frequent memory accesses cause global component bottlenecks. In this paper, we propose a cache coherence protocol using a distributed data dependence violation checking mechanism for TLS. The proposed protocol extends the traditional MESI cache coherence protocol by including several methods to exceed the present limits of centralized violation checking methods. The protocol adds an invalidation vector to each private L1 cache to record threads that violate RAW data dependence. It also adds a versioning Priority Register that compares data versions. Added to each private L1 cache block is a snooping bit which indicates whether the thread possesses a bus snooping right for the block. The proposed protocol is much more complicated than the traditional MESI protocol and hard to be completely verified only through simulation. So we applied formal verification to the proposed cache protocol to confirm its correctness. The verification result shows that the proposed protocol will function correctly in TLS system.