Recent Publications

Shoker A.  2018.  Brief Announcement: Sustainable Blockchains through Proof of eXercise.. ACM Symposium on Principles of Distributed Computing (PODC). Abstractpox-podc.pdf


Shoker A.  2017.  Sustainable Blockchain through Proof of eXercise. The 16th IEEE International Symposium on Network Computing and Applications (NCA 2017). PoX
Kassam Z, Shoker A, Almeida PS, Moreno CB.  2017.  Aggregation Protocols in Light of Reliable Communication. The 16th IEEE International Symposium on Network Computing and Applications (NCA 2017). Aggregation Protocols in Light of Reliable Communication
Shoker A.  2016.  Exploiting Universal Redundancy. The 15th IEEE International Symposium on Network Computing and Applications. Abstractartira.pdf

Fault tolerance is essential for building reliable services; however, it comes at the price of redundancy, mainly the “replication factor” and “diversity”. With the increasing reliance on Internet-based services, more machines (mainly servers) are needed to scale out, multiplied with the extra expense of replication. This paper revisits the very fundamentals of fault tolerance and presents “artificial redundancy”: a formal generalization of “exact copy” redundancy in which new sources of redundancy are exploited to build fault tolerant systems. On this concept, we show how to build “artificial replication” and design “artificial fault tolerance” (AFT). We discuss the properties of these new techniques showing that AFT extends current fault tolerant approaches to use other forms of redundancy aiming at reduced cost and high diversity.

Bahsoun JP, Guerraoui R, Shoker A.  2015.  Making BFT Protocols Really Adaptive. In the Proceedings of the 29th IEEE International Parallel & Distributed Processing Symposium. Abstractadapt.pdf

Many state-machine Byzantine Fault Tolerant (BFT) protocols have been introduced so far. Each protocol addressed a different subset of conditions and use-cases. However, if the underlying conditions of a service span different subsets, choosing a single protocol will likely not be a best fit. This yields robustness and performance issues which may be even worse in services that exhibit fluctuating conditions and workloads.
In this paper, we reconcile existing state-machine BFT protocols in a single adaptive BFT system, called ADAPT, aiming at covering a larger set of conditions and use-cases, probably the union of individual subsets of these protocols. At anytime, a launched protocol in ADAPT can be aborted and replaced by another protocol according to a potential change (an event) in the underlying system conditions. The launched protocol is chosen according to an “evaluation process” that takes into consideration both: protocol characteristics and its performance. This is achieved by applying some mathematical formulas that match the profiles of protocols to given user (e.g., service owner) preferences. ADAPT can assess the profiles of protocols (e.g., throughput) at run-time using Machine Learning prediction mechanisms to get accurate evaluations. We compare ADAPT with well known BFT protocols showing that it outperforms others as system conditions change and under dynamic workloads.

Almeida PS, Shoker A, Moreno CB.  2015.  Efficient State-based CRDTs by Delta-Mutation. In the Proceedings of the International Conference on NETworked sYStems}. 9466 Abstractdeltacrdt.pdf

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 (δ-CRDT) that 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. This is achieved by defining δ-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 δ-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 we introduce two δ-CRDT specifications of well-known replicated datatypes.

Moreno CB, Almeida PS, Shoker A.  2014.  Making Operation-Based CRDTs Operation-Based. The International Conference on Distributed Applications and Interoperable Systems - DAIS. 8460:126–140. AbstractBest paper (joint)

Conflict-free Replicated Datatypes (CRDT) can simplify the design of eventually consistent systems. They can be classified into state- based or operation-based. Operation-based designs have the potential for allowing very compact solutions in both the sent messages and the object state size. Unfortunately, the current approaches are still far from this objective. In this paper, we introduce a new ‘pure’ operation-based frame- work that makes the design and the implementation of these CRDTs more simple and efficient. We show how to leverage the meta-data of the messaging middleware to design very compact CRDTs, while only disseminating operation names and their optional arguments.

Shoker A, Bahsoun JP.  2013.  BFT Selection. Proceedings of the International Conference of Networked Systems - NETYS. 7853 AbstractPaper

This paper presents the first BFT selection model and algorithm that can be used to choose the most convenient protocol according to the BFT user (i.e., an enterprise) 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 fluctuating and thus requires runtime decisions, and the Heuristic mode uses additional heuristics to improve user choices. To the best of our knowledge, this is the first work that addresses selection in BFT.

Shoker A, Bahsoun JP, Yabandeh M.  2013.  Improving Independence of Failures in BFT. The 12th International Symposium on Network Computing and Applications - NCA. AbstractPaper

Independence of failures is a basic assumption for the correctness of BFT protocols. In literature, this subject was addressed by providing N-version like abstractions. Though this can provide a good level of obfuscation against semantic- based attacks, if the replicas know each others identities then non-semantic attacks like DoS can still compromise all replicas together. In this paper, we address the obfuscation problem in a different way by keeping replicas unaware of each other. This makes it harder for attackers to sneak from one replica to another and reduces the impact of simultaneous attacks on all replicas. For this sake, we present a new obfuscated BFT protocol, called OBFT, where the replicas remain unaware of each other by exchanging their messages through the clients. Thus, OBFT assumes honest, but possibly crash-prone clients. We show that obfuscation in our context could not be achieved without this assumption, and we give possible applications where this assumption can be accepted. We evaluated our protocol on an Emulab cluster with a wide area topology. Our experiments show that the scalability and throughput of OBFT remain comparable to existing BFT protocols despite the obfuscation overhead.

Sonia Ben Mokhtar, Gautier Berthou ADVQ, Shoker A.  2013.  RAC: a Freerider-resilient, Scalable, Anonymous Communication Protocol. Proceedings of the 33rd International Conference on Distributed Computing Systems - ICDCS. AbstractPaper

Enabling anonymous communication over the Internet is crucial. The first protocols that have been devised for anonymous communication are subject to freeriding. Recent protocols have thus been proposed to deal with this issue. However, these protocols do not scale to large systems, and some of them further assume the existence of trusted servers. In this paper, we present RAC, the first anonymous communication protocol that tolerates freeriders and that scales to large systems. Scalability comes from the fact that the complexity in terms of the number of message exchanges is independent from the number of nodes in the system. Another important aspect of RAC is that it does not rely on any trusted third party. We theoretically prove, using game theory that our protocol is a Nash equilibrium, i.e, that freeriders have no interest in deviating from the protocol. Further, we experimentally evaluate RAC using simulations. Our evaluation shows that, whatever the size of the system (up to 100.000 nodes), the nodes participating in the system observe the same throughput.

Shoker A, Bahsoun JP.  2012.  Towards Byzantine Resilient Directories. The 11th International Symposium on Network Computing and Applications - NCA. AbstractPaper

Notable Byzantine Fault Tolerant protocols have been designed so far. These protocols are often evaluated on simple benchmarks, and few times on NFS systems. On the contrary, studies that addressed the behaviour of BFT on large back-ends, like Directories, are rare. We believe that studying such systems is crucial for practice community due to their popularity. In this paper, we integrate BFT with OpenLDAP Directory. We introduce the design of the integrated system, that we call BFT-LDAP. Then, we study its behaviour accompanied with some useful observations. In addition, we discuss the cost overhead of this integration. Our approach ensures that OpenLDAP legacy code remains completely intact, and that the integration with BFT is straightforward using APIs. Moreover, we convey that the additional performance cost of BFT-LDAP is negligible as compared to that of stand-alone OpenLDAP. We conducted our experiments on Emulab. The experiments indicate that the performance discrepancy of BFT-LDAP is negligible whenever different state-of-the-art BFT protocols are used. Other experiments demonstrate that a little sacrifice in throughput (less than 10%) is needed in order to leverage the resiliency of OpenLDAP against Byzantine faults (i.e., through applying BFT).

Shoker A, Yactine H, Moreno CB.  2017.  As Secure as Possible Eventual Consistency (Work in Progress). EuroSys PAPOC'17 workshops: International Workshop on Principles and Practice of Consistency for Distributed Data. :1-5.Secure EC
Shoker A, Yactine H, Moreno CB.  2017.  As Secure as Possible Eventual Consistency. In the proceedings of the 3rd International Workshop on Principles and Practice of Consistency for Distributed Data (EuroSys PAPOC’17). As Secure as Possible Eventual Consistency.pdf