Cookies Policy
The website need some cookies and similar means to function. If you permit us, we will use those means to collect data on your visits for aggregated statistics to improve our service. Find out More
Accept Reject
  • Menu
Publications

Publications by Ali Shoker

2015

Exactly-Once Quantity Transfer

Authors
Shoker, A; Almeida, PS; Baquero, C;

Publication
2015 IEEE 34th Symposium on Reliable Distributed Systems Workshop (SRDSW)

Abstract
Strongly consistent systems supporting distributed transactions can be prone to high latency and do not tolerate partitions. The present trend of using weaker forms of consistency, to achieve high availability, poses notable challenges in writing applications due to the lack of linearizability, e.g., to ensure global invariants, or perform mutator operations on a distributed datatype. This paper addresses a specific problem: the exactly-once transfer of a "quantity" from one node to another on an unreliable network (coping with message duplication, loss, or reordering) and without any form of global synchronization. This allows preserving a global property (the sum of quantities remains unchanged) without requiring global linearizability and only through using pairwise interactions between nodes, therefore allowing partitions in the system. We present the novel quantity-transfer algorithm while focusing on a specific use-case: a redistribution protocol to keep the quantities in a set of nodes balanced; in particular, averaging a shared real number across nodes. Since this is a work in progress, we briefly discuss the correctness of the protocol, and we leave potential extensions and empirical evaluations for future work.

2016

Integration Challenges of Pure Operation-based CRDTs in Redis

Authors
Younes, G; Shoker, A; Almeida, PS; Baquero, C;

Publication
First Workshop on Programming Models and Languages for Distributed Computing, PMLDC@ECOOP 2016, Rome, Italy, July 17, 2016

Abstract
Pure operation-based (op-based) Conflict-free Replicated Data Types (CRDTs) are generic and very efficient as they allow for compact solutions in both sent messages and state size. Although the pure op-based model looks promising, it is still not fully understood in terms of practical implementation. In this paper, we explain the challenges faced in implementing pure op-based CRDTs in a real system: the well-known in-memory cache key-value store Redis. Our purpose of choosing Redis is to implement a multi-master replication feature, which the current system lacks. The experience demonstrates that pure op-based CRDTs can be implemented in existing systems with minor changes in the original API. © 2016 Copyright held by the owner/author(s).

2016

Join Decompositions for Efficient Synchronization of CRDTs after a Network Partition: Work in progress report

Authors
Enes, V; Baquero, C; Almeida, PS; Shoker, A;

Publication
First Workshop on Programming Models and Languages for Distributed Computing, PMLDC@ECOOP 2016, Rome, Italy, July 17, 2016

Abstract
State-based CRDTs allow updates on local replicas without remote synchronization. Once these updates are propagated, possible conflicts are resolved deterministically across all replicas. d-CRDTs bring significant advantages in terms of the size of messages exchanged between replicas during normal operation. However, when a replica joins the system after a network partition, it needs to receive the updates it missed and propagate the ones performed locally. Current systems solve this by exchanging the full state bidirectionally or by storing additional metadata along the CRDT. We introduce the concept of join-decomposition for state-based CRDTs, a technique orthogonal and complementary to delta-mutation, and propose two synchronization methods that reduce the amount of information exchanged, with no need to modify current CRDT definitions. © 2016 Copyright held by the owner/author(s).

2014

Efficient state-based CRDTs by decomposition

Authors
Almeida, PS; Shoker, A; Baquero, C;

Publication
Proceedings of the 1st Workshop on the Principles and Practice of Eventual Consistency, PaPEC 2014

Abstract
Eventual consistency is a relaxed consistency model used in large-scale distributed systems that seek better availability when consistency can be delayed. CRDTs are distributed data types that make eventual consistency of a distributed object possible and non ad-hoc. Specifically, state-based CRDTs achieve this through shipping the entire replica state that is, eventually, merged to other replicas ensuring conver- gence. This imposes a large communication overhead when the replica size or the number of replicas gets larger. In this work, we introduce a decomposable version of state-based CRDTs, called Delta State-based CRDTs (d-CRDT). A d-CRDT is viewed as a join of multiple fine-grained CRDTs of the same type, called deltas (d). The deltas are produced by applying d-mutators, on a replica state, which are mod- ified versions of the original CRDT mutators. This makes it possible to ship small deltas (or batches) instead of ship- ping the entire state. The challenges are to make the join of deltas equivalent to the join of the entire object in clas- sical state-based CRDTs, and to find a way to derive the d-mutators. We address this challenge in this work, and we explore the minimal requirements that a communication al- gorithm must offer according to the guarantees provided by the underlying messaging middleware. Copyright © 2007 by the Association for Computing Machinery, Inc.

2015

Efficient State-Based CRDTs by Delta-Mutation

Authors
Almeida, PS; Shoker, A; Baquero, C;

Publication
Networked Systems - Third International Conference, NETYS 2015, Agadir, Morocco, May 13-15, 2015, Revised Selected Papers

Abstract
CRDTs are distributed data types that make eventual consistency of a distributed object possible and non ad-hoc. Specifically, state-based CRDTs ensure convergence through disseminating the entire state, that may be large, and merging it to other replicas; whereas operation-based CRDTs disseminate operations (i.e., small states) assuming an exactly-once reliable dissemination layer. We introduce Delta State Conflict-Free Replicated Datatypes (d-CRDT) that can achieve the best of both worlds: small messages with an incremental nature, disseminated over unreliable communication channels. This is achieved by defining d-mutators to return a delta-state, typically with a much smaller size than the full state, that is joined to both: local and remote states. We introduce the d-CRDT framework, and we explain it through establishing a correspondence to current state-based CRDTs. In addition, we present an anti-entropy algorithm that ensures causal consistency, and two d-CRDT specifications of well-known replicated datatypes. © Springer International Publishing Switzerland 2015.

2014

Making operation-based CRDTs operation-based

Authors
Baquero, C; Almeida, PS; Shoker, A;

Publication
Proceedings of the 1st Workshop on the Principles and Practice of Eventual Consistency, PaPEC 2014

Abstract
Conict-free Replicated Datatypes can simplify the design of predictable eventual consistency. They can be classified into state-based or operation-based. Operation-based ap- proaches have the potential for allowing compact designs in both the sent message and the object state size, but cur- rent approaches are still far from this objective. Here we explore the design space for operation-based solutions, and we leverage the interaction with the middleware by offering a technique that delivers very compact solutions, while only broadcasting operation names and arguments. Copyright © 2007 by the Association for Computing Machinery, Inc.

  • 1
  • 4