Reports

Shoker A, Leitao J, Roy PV, Meiklejohn C.  2017.  LightKone: Towards General Purpose Computations on the Edge. H2020 LightKone Project. :0-12.lightkone.pdf
Moreno CB, Almeida PS, Shoker A.  2017.  Pure Operation-Based Replicated Data Types. arXiv. :0-30.PureCRDTsArXiv
Almeida PS, Shoker A, Moreno CB.  2015.  Efficient State-based CRDTs by Delta-Mutation. CoRR. abs/1410.2803:1-19. Abstractdelta-tr.pdf

CRDTs are distributed data types that make eventual consistency of a distributed object possible and non ad-hoc. Specifically, state-based CRDTs achieve this by sharing local state changes through shipping the entire state, that is then merged to other replicas with an idempotent, associative, and commutative join operation, ensuring convergence. This imposes a large communication overhead as the state size becomes larger. We introduce Delta State Conflict-Free Replicated Datatypes ({\delta}-CRDT), which make use of {\delta}-mutators, defined in such a way to return a delta-state, typically, with a much smaller size than the full state. Delta-states are joined to the local state as well as to the remote states (after being shipped). This can achieve the best of both worlds: small messages with an incremental nature, as in operation-based CRDTs, disseminated over unreliable communication channels, as in traditional state-based CRDTs. We introduce the {\delta}-CRDT framework, and we explain it through establishing a correspondence to current state- based CRDTs. In addition, we present two anti-entropy algorithms: a basic one that provides eventual convergence, and another one that ensures both convergence and causal consistency. We also introduce two {\delta}-CRDT specifications of well-known replicated datatypes.

Shoker A, Bahsoun JP.  2013.  BFT Selection. :1-15. AbstractPaper

One-size-fits-all protocols are hard to achieve in Byzantine fault tolerance (BFT). As an alternative, BFT users, e.g., enterprises, need an easy and efficient method to choose the most convenient protocol that matches their preferences best. The various BFT protocols that have been proposed so far differ significantly in their characteristics and performance which makes choosing the ‘preferred’ protocol hard. In addition, if the state of the deployed system is too fluctuating, then perhaps using multiple protocols at once is needed; this requires a dynamic selection mechanism to move from one protocol to another. In this paper, we present the first BFT selection model and algorithm that can be used to choose the most convenient protocol according to user preferences. The selection algorithm applies some mathematical formulas to make the selection process easy and automatic. The algorithm operates in three modes: Static, Dynamic, and Heuristic. The Static mode addresses the cases where a single protocol is needed; the Dynamic mode assumes that the system conditions are quite ?uctuating and thus requires run-time decisions, and the Heuristic mode is similar to the Dynamic mode but it uses additional heuristics to improve user choices. We give some examples to describe how selection occurs. We show that our approach is automated, easy, and yields reasonable results that match reality. To the best of our knowledge, this is the first work that addresses selection in BFT.

Shoker A, Yabandeh M, Guerraoui R, Bahsoun JP.  2012.  Obfuscated BFT. :1-15. AbstractPaper

A major assumption underlies the correctness of BFT services: failure independence. However, state of the art protocols rely on inter-replica communication in order to preserve consistency, and they implicitly require replicas to store access information about each other. This jeopardizes the independence of failure assumption since intruders can sneak from one replica to another and compromises the entire service. In this paper, we leverage this issue by exploring the idea of obfuscation in the BFT context: the replicas of a BFT service are completely unaware of each others identities. We present a new client-based replication BFT protocol, called OBFT, that assumes honest, but possibly crash-prone clients. The protocol imposes equivalent load on replicas to avoid bottlenecks, and reduces the load on the primary replica by distributing multi-cast and cryptographic tasks among clients. We evaluate OBFT on an Emulab cluster with a wide area topology and convey its scalability with respect to state of the art BFT protocols.

Shoker A, Bahsoun JP.  2009.  BFT for Three Decades, Yet Not Enough!. :1-6. AbstractPaper

Distributed systems are established to maintain safety and liveness while attending good performance. Nowadays, Byzantine Failures are considered the most critical threat for system’s safety. Various BFT protocols were found through the history; however, none has been adopted yet. The reason perhaps originates from the fact that Byzantine Fault Tolerance issue is hard by nature; add to this the complications underlying BFT protocols implementation. This paper represents a general overview on Byzantine Fault Tolerance, its evolution, and difficulties disturbing its realization. First, we introduce the subject by defining replication, its importance and some problems; then we describe in brief the basic BFT protocols reporting some comparisons. Then we expose some problems that BFT protocols implementations are facing and we give a solution proposed by Guerraoui et al.; finally, we summarize our paper and conclude.