Networked Systems

Frontmatter

Keynote Talk: Communication Without Repudiation: The Unanswered Question

Abstract

A non-repudiation protocol is to be executed by two parties, say \(S\) and \(R\), in order to (1) enable \(S\) to send some text to \(R\) then receive some non-repudiated evidence that \(R\) has indeed received the text, and (2) enable \(R\) to receive both the sent text from \(S\) and some non-repudiated evidence that this text was indeed sent from \(S\) to \(R\). Since 1995, tens of non-repudiation protocols have been proposed, but every one of these protocols seems to suffer from one or more well-known problems. For example, most protocols assume the existence of a third party that is trusted by both \(S\) and \(R\). This observation reminds us that the following core question has never been answered. Can there be a non-repudiation protocol that does not suffer from any of these problems?

Mohamed G. Gouda

Leader Election in Rings with Homonyms

Abstract

Considering the case of homonyms processes (some processes may share the same identifier) on a ring, we give here a necessary and sufficient condition on the number of identifiers to enable leader election. We prove that if \(l\) is the number of identifiers then message-terminating election is possible if and only if \(l\) is greater than the greatest proper divisor of the ring size even if the processes do not know the ring size. If the ring size is known, we propose a process-terminating algorithm exchanging \(O(n \log (n))\) messages that is optimal.

Carole Delporte-Gallet, Hugues Fauconnier, Hung Tran-The

Abort Free SemanticTM by Dependency Aware Scheduling of Transactional Instructions

Abstract

We present a TM system that executes transactions without ever causing any aborts. The system uses a set of t-var lists, one for each transactional variable. The instructions of each transaction are placed in the appropriate t-var lists based on which t-variable each of them accesses. A set of worker threads are responsible to execute these instructions. Because of the way instructions are inserted in and removed from the lists, by the way the worker threads work, and by the fact that all the instructions of a transaction are placed in the appropriate t-var lists before doing so for the instructions of any subsequent transaction, it follows that no conflict will ever occur. Parallelism is fine-grained since it is achieved at the level of transactional instructions instead of transactions themselves (i.e., the instructions of a transaction may be executed concurrently).

Hillel Avni, Shlomi Dolev, Panagiota Fatourou, Eleftherios Kosmas

Disjoint-Access Parallelism Does Not Entail Scalability

Abstract

Disjoint Access Parallelism (DAP) stipulates that operations involving disjoint sets of memory words must be able to progress independently, without interfering with each other. In this work we argue towards revising the two decade old wisdom saying that DAP is a binary condition that splits concurrent programs into scalable and non-scalable. We first present situations where DAP algorithms scale poorly, thus showing that not even algorithms that achieve this property provide scalability under all circumstances. Next, we show that algorithms which violate DAP can sometimes achieve the same scalability and performance as their DAP counterparts. We continue to show how by violating DAP and without sacrificing scalability we are able to circumvent three theoretical results showing that DAP is incompatible with other desirable properties of concurrent programs. Finally we introduce a new property called generalized disjoint-access parallelism (GDAP) which estimates how much of an algorithm is DAP. Algorithms having a large DAP part scale similar to DAP algorithms while not being subject to the same impossibility results.

Rachid Guerraoui, Mihai Letia

Linearizability Is Not Always a Safety Property

Abstract

We show that, in contrast to the general belief in the distributed computing community, linearizability, the celebrated consistency property, is not always a safety property. More specifically, we give an object for which it is possible to have an infinite history that is not linearizable, even though every finite prefix of the history is linearizable. The object we consider as a counterexample has infinite nondeterminism. We show, however, that if we restrict attention to objects with finite nondeterminism, we can use König’s lemma to prove that linearizability is indeed a safety property. In the same vein, we show that the backward simulation technique, which is a classical technique to prove linearizability, is not sound for arbitrary types, but is sound for types with finite nondeterminism.

Rachid Guerraoui, Eric Ruppert

Fair Linking Mechanisms for Resource Allocation with Correlated Player Types

Abstract

Resource allocation is one of the most relevant problems in the area of Mechanism Design for computing systems. Devising algorithms capable of providing efficient and fair allocation is the objective of many previous research efforts. Usually, the mechanisms they propose use payments in order to deal with selfishness. Since using payments is undesirable in some contexts, a family of mechanisms without payments is proposed in this paper. These mechanisms extend the Linking Mechanism of Jackson and Sonnenschein introducing a generic concept of fairness with correlated preferences. We prove that these mechanisms have good incentive, fairness, and efficiency properties. To conclude, we provide an algorithm, based on the mechanisms, that could be used in practical computing environments.

Agustín Santos, Antonio Fernández Anta, José A. Cuesta, Luis López Fernández

Iterative Approximate Consensus in the Presence of Byzantine Link Failures

Abstract

This paper explores the problem of reaching approximate consensus in synchronous point-to-point networks, where each directed link of the underlying communication graph represents a communication channel between a pair of nodes. We adopt the transient Byzantine link failure model [15, 16], where an omniscient adversary controls a subset of the directed communication links, but the nodes are assumed to be fault-free.

Recent work has addressed the problem of reaching approximate consensus in incomplete graphs with Byzantine nodes using a restricted class of iterative algorithms that maintain only a small amount of memory across iterations [12, 21, 23, 24]. This paper addresses approximate consensus in the presence of Byzantine links. We extend our past work [21, 23] that provided exact characterization of graphs in which the iterative approximate consensus problem in the presence of Byzantine node failures is solvable. In particular, we prove a tight necessary and sufficient condition on the underlying communication graph for the existence of iterative approximate consensus algorithms under transient Byzantine link model [15, 16].

Lewis Tseng, Nitin Vaidya

Practically Self-stabilizing Paxos Replicated State-Machine

Abstract

We present the first (practically) self-stabilizing replicated state machine for asynchronous message passing systems. The scheme is based on a variant of the Paxos algorithm and ensures that starting from an arbitrary configuration, the replicated state-machine eventually exhibits the desired behaviour for a long enough execution regarding all practical considerations.

Peva Blanchard, Shlomi Dolev, Joffroy Beauquier, Sylvie Delaët

An Architecture for Automatic Scaling of Replicated Services

Abstract

Replicated services that allow to scale dynamically can adapt to requests load. Choosing the right number of replicas is fundamental to avoid performance worsening when input spikes occur and to save resources when the load is low. Current mechanisms for automatic scaling are mostly based on fixed thresholds on CPU and memory usage, which are not sufficiently accurate and often entail late countermeasures. We propose Make Your Service Elastic (MYSE), an architecture for automatic scaling of generic replicated services based on queuing models for accurate response time estimation. Requests and service times patterns are analyzed to learn and predict over time their distribution so as to allow for early scaling. A novel heuristic is proposed to avoid the flipping phenomenon. We carried out simulations that show promising results for what concerns the effectiveness of our approach.

Leonardo Aniello, Silvia Bonomi, Federico Lombardi, Alessandro Zelli, Roberto Baldoni

CEP4CMA: Multi-layer Cloud Performance Monitoring and Analysis via Complex Event Processing

Abstract

This paper presents a multi-layer monitoring and analysis approach for Cloud computing environments based on the methodology of Complex Event Processing (CEP). Instead of having to manually specify continuous queries on monitored event streams, CEP queries are derived from analyzing the correlations between monitored metrics across multiple Cloud layers. The results of our correlation analysis allow us to reduce the number of monitored parameters and enable us to perform a root cause analysis to identify the causes of performance-related problems. The derived analysis rules are implemented as queries in a CEP engine. The results of several experiments demonstrate the benefits of the proposed approach in terms of precision and recall in comparison with threshold-based methods. They also show the accuracy of our approach in identifying the causes of performance-related problems.

Afef Mdhaffar, Riadh Ben Halima, Mohamed Jmaiel, Bernd Freisleben

Hardness of Firewall Analysis

Abstract

We identify 13 problems whose solutions can significantly enhance our ability to design and analyze firewalls and other packet classifiers. These problems include the firewall equivalence problem, the firewall redundancy problem, the firewall verification problem, and the firewall completeness problem. The main result of this paper is to prove that every one of these problems is NP-hard. Our proof of this result is interesting in the following way. Only one of the 13 problems, the so called slice probing problem, is shown to be NP-hard by a reduction from the well-known 3-SAT problem. Then, the remaining 12 problems are shown to be NP-hard by reductions from the slice probing problem. The negative results of this paper suggest that firewalls designers may need to rely on SAT solvers to solve instances of these 13 problems or may be content with probabilistic solutions of these problems.

Ehab S. Elmallah, Mohamed G. Gouda

Privacy-Preserving Distributed Collaborative Filtering

Abstract

We propose a new mechanism to preserve privacy while leveraging user profiles in distributed recommender systems. Our mechanism relies on (i) an original obfuscation scheme to hide the exact profiles of users without significantly decreasing their utility, as well as on (ii) a randomized dissemination protocol ensuring differential privacy during the dissemination process.

We compare our mechanism with a non-private as well as with a fully private alternative. We consider a real dataset from a user survey and report on simulations as well as planetlab experiments. We dissect our results in terms of accuracy and privacy trade-offs, bandwidth consumption, as well as resilience to a censorship attack. In short, our extensive evaluation shows that our twofold mechanism provides a good trade-off between privacy and accuracy, with little overhead and high resilience.

Antoine Boutet, Davide Frey, Rachid Guerraoui, Arnaud Jégou, Anne-Marie Kermarrec

A Scalable P2P RIA Crawling System with Partial Knowledge

Abstract

Rich Internet Applications are widely used as they are interactive and user friendly. Automated tools for crawling Rich Internet Applications have become needed for many reasons such as content indexing or testing for correctness and security. Due to the large size of RIAs, distributed crawling has been introduced to reduce the amount of time required for crawling. However, having one controller may result in a performance bottleneck resulting from a single database simultaneously accessed by many crawlers. It may also be vulnerable to complete data loss if a node failure occurs at the storage unit. We present a distributed decentralized scheme for crawling large-scale RIAs capable of partitioning the search space among several controllers in which the information is partially stored, which allows for fault tolerance and for the scalability of the system. Our results are significantly better than for non-distributed crawling, and outperforms the distributed crawling using one coordinator.

Khaled Ben Hafaiedh, Gregor von Bochmann, Guy-Vincent Jourdan, Iosif Viorel Onut

GDist-RIA Crawler: A Greedy Distributed Crawler for Rich Internet Applications

Abstract

Crawling web applications is important for indexing, accessibility and security assessment. Crawling traditional web applications is an old problem, for which good and efficient solution are known. Crawling Rich Internet Applications (RIA) quickly and efficiently, however, is an open problem. Technologies such as AJAX and partial Document Object Model (DOM) updates only make the problem of crawling RIA more time consuming to the web crawler. One way to reduce the time to crawl a RIA is to crawl a RIA in parallel with multiple computers. Previously published Dist-RIA Crawler presents a distributed breath-first search algorithm to crawl RIAs. This paper expands Dist-RIA Crawler in two ways. First, it introduces an adaptive load-balancing algorithm that enables the crawler to learn about the speed of the nodes and adapt to changes, thus better utilize the resources. Second, it present a distributed greedy algorithm to crawl a RIA in parallel, called GDist-RIA Crawler. The GDist-RIA Crawler uses a server-client architecture where the server dispatched crawling jobs to the crawling clients. This paper illustrates a prototype implementation of the GDist-RIA Crawler, explains some of the techniques used to implement the prototype and inspects empirical performance measurements.

Seyed M. Mirtaheri, Gregor von Bochmann, Guy-Vincent Jourdan, Iosif Viorel Onut

A New Preference Based Model for Relevant Dimension Identification in Contextual Mobile Search

Abstract

Mobile search is a significant task in information retrieval and when coupled with context awareness technologies they can become key tools for mobile users for Web search applications. Context awareness techniques can increase the usability of mobile search providing personalized and more focussed content. However, Contextualized Mobile Information Retrieval still remains a challenging problem. This problem is to identify contextual dimensions that improve search effectiveness and should therefore be in the user’s focus. We propose a context filtering process based on a new Preference Language Model, and a new relevance measurement. The experiments have been performed with over than 6000 contextual dimensions. The results show the potential of our Preference model in limiting the negative effects of contextual information overload by using the relevance measurement.

Sondess Missaoui, Rim Faiz

Intelligent Multipath Optimized Link State Routing Protocol for QoS and QoE Enhancement of Video Transmission in MANETs

Abstract

Video transmission over Mobile Ad hoc Networks (MANETs) is a challenging task due to instability and limited resources in such networks. Transmission of video streams through multipath routing protocols in MANETs can enhance the quality of video transmission. To this end, we propose an extension of MP-OLSR (Multipath Optimized Link State Routing Protocol), named FQ-MP-OLSR (Fuzzy based Quality of service MP-OLSR), which integrates two fuzzy systems. The first receives as inputs three links Quality of Service (QoS) metrics: delay, throughput and Signal to Interference plus Noise Ratio (SINR) and return as output multi-constrained QoS metric used to find the best paths. The second fuzzy system is applied to adapt cost functions used to penalize paths previously computed by Dijkstra’s algorithm. To schedule multimedia traffic among heterogeneous multiple paths, FQ-MP-OLSR integrates also the Weighted Round-Robin (WRR) scheduling algorithm, where the path weights, needed for scheduling, are computed using the multi-constrained QoS metric provided by the first fuzzy system. These mechanisms allow FQ-MP-OLSR to improve video QoS and QoE (Quality of Experiment), against the MP-OLSR that uses classical mechanisms such as hop count as single metric, cost functions without adaptation and Round-Robin (RR) as scheduling algorithm. Implementation and simulation experiments with Network Simulator NS2 are presented in order to validate our proposed approach. The results show that FQ-MP-OLSR achieves a significant improvement of the video streaming quality in term of QoS and QoE.

Abdelali Boushaba, Adil Benabbou, Rachid Benabbou, Azeddine Zahi, Mohammed Oumsis

Improved Ant Colony Optimization Routing Protocol for Wireless Sensor Networks

Abstract

Wireless Sensor Networks (WSNs) consist of autonomous nodes, deployed to monitor various environments (even under hostility). Major challenges arise from its limited energy, communication failures and computational weakness. Many issues in WSNs are formulated as NP-hard optimization problems, and approached through metaheuristics. This paper outlines an Ant Colony Optimization (ACO) used to solve routing problems in WSNs. We have studied an approach based on ACO. So, we designed an improved one that reduces energy consumption and prolongs WSN lifetime. Through simulation results, our proposal efficiency is validated.

Asmae El Ghazi, Belaïd Ahiod, Aziz Ouaarab

UMTS Base-Station Location Problem for Uplink Direction Using Genetic Algorithms and Fuzzy Logic

Abstract

In this paper, we address the problem of planning the universal mobile telecommunication system (UMTS) base stations location for uplink direction. The objective is to maximize the total trafic covered and minimize the total installation cost. To define the cost, researchers used the current period market prices. But prices may change over time. Our aim here is to deal with the imprecise and uncertain information of prices. For this we address this problem using fuzzy Logic. We propose an algorithm based on the hybridization of genetic algorithm (GA) with Local Search method (LS). To code the solutions of the problem, we have used an encoding method which combines binary and integer coding. To validate the proposed method some numerical examples are given. The obtained results show the efficiency of our approach.

Mohammed Gabli, El Miloud Jaara, El Bekkaye Mermri

FL-EDCA: A QoS-Aware and Energy-Efficient Mechanism for IEEE 802.11e EDCA Standard

Abstract

The IEEE 802.11e EDCA standard was developed to guarantee the Quality of Service (QoS) requirements of the different traffic types (voice, video, data, etc.) in WLAN. However, several studies have shown that this standard performs poorly under heavy load traffic due to the high collision rate. On the other hand, EDCA was also used in the battery constrained devices. But, very few studies have tried to improve the energy-efficiency of this standard. For these reasons, we propose in this paper a Fuzzy-Logic-based (FL) mechanism to improve both energy-efficiency and traffic performance of the IEEE 802.11e EDCA, and also to favor real-time traffic when traffic load is heavy. The proposed FL-EDCA decreases the collision probability considerably, through a dynamic adaptation of the contention windows, using fuzzy logic controller. Our simulation results show that FL-EDCA outperforms EDCA by improving significantly energy-efficiency and traffic performance.

Hicham Touil, Youssef Fakhri

Loss Minimization and Delay Differentiation for Optical Burst Switching Over Star Networks

Abstract

In OBS networks, lost bursts can be recovered proactively using burst cloning, or reactively using burst retransmission. Burst cloning has advantage of low delay but it suffers from low throughput. Burst retransmission has advantage of high throughput but at the cost of high delay. To minimize delay while keeping high throughput in star OBS networks, we propose three schemes: (1) enhanced burst retransmission scheme that controls the retransmissions; (2) hybrid loss recovery scheme that integrates efficiently burst cloning and burst retransmission; (3) differentiated QoS scheme that provides differentiation between two classes in terms of delay using burst cloning and burst retransmission. Both analytical and simulation results show that the proposed schemes achieve high throughput. We find that, compared to basic burst retransmission scheme, first scheme reduces delay only at moderate and high load, however, second and third scheme reduce delay at every load. Third scheme can also give good differentiation.

Salek Riadi, Abdelilah Maach, Driss El Ghanami

A Formal Driving Behavior Model for Intelligent Transportation Systems

Abstract

Vehicular Ad hoc Networks are considered recently as a fertile field of research. Their applications are showing a growing importance as they are expected to improve road safety and traffic efficiency, through the development of vehicle safety applications whose main goal is to provide the driver with assistance in dangerous situations. Thanks to vehicular communications, drivers can permanently receive information about road conditions which help them to make more reliable decisions. The idea behind this paper is to enable an adaptive assistance to drivers in different situations, based on their past driving experience. As a first step, we focus on the modeling and learning of individual driving behavior at a picoscopic level. This paper proposes a formal description of a driver-centric model, using the formalisms of hybrid IO automata and rectangular automata. Then, an online passive learning based approach for the construction of the described model is proposed. Having a model that describe the behavior of drivers can enable us to predict and recognize a driver preferences in different driving context, enabling thus an adaptive assistance.

Afaf Bouhoute, Ismail Berrada, Mohamed El Kamili

Short: Blind Separation of the Multiarray Multisensor Systems Using the CP Decomposition

Abstract

Sensor arrays are used in many applications, where their ability to localize signal sources is essential. One of the sensor applications is the signal processing of multi antennas with multi sensors. In this paper, we present an application of the proposed Canonical Polyadic decomposition (CP decomposition), with isolation of scaling matrix to multiarray multisensor systems. A simple blind receiver based on the enhanced alternating least squares (E-ALS) algorithm is presented. For illustrating this application, computer simulations are provided and demonstrate the good behavior of these algorithm compared to the old ALS algorithm.

Awatif Rouijel, Khalid Minaoui, Pierre Comon, Driss Aboutajdine

Short: A Lightweight and Secure Session Management Protocol

Abstract

Secure session management is a challenging problem for Web applications. In fact, three of the ten most critical security risks included in the OWASP top ten 2013 can lead to session hijacking attacks. Best practices advocate the transmission of the session identifiers over HTTPS. However, this approach does not solve the session problems, and can’t be deployed on a wide range of HTTP-only applications. This paper presents a lightweight session management design deployed over HTTP, which allows much of the existing infrastructure of the web to remain unchanged, while at the same time strengthening authentication. Our work leverages the following key insights. (1) Users already have shared secrets with their web applications (e.g. password). (2) HTTPS is primarily used to protect the authentication information. (3) A secure session management should be built on a secure initial mutual authentication. Our proposed protocol guaranties the authenticity, confidentiality, integrity, and anti-reply of authentication credentials.

Yassine Sadqi, Ahmed Asimi, Younes Asimi

Short: Intrusion Detection Quality Analysis for Homogeneous Wireless Sensor Networks

Abstract

In this paper we analyze the intrusion detection in a homogeneous Wireless Sensor Network that is defined as a mechanism to monitor and detect unauthorized intrusions or anomalous moving attackers in area of interest. The quality of deterministic deployment can be determined sufficiently by analysis, before the deployment. However, when random deployment is required, determining the deployment quality becomes challenging and depends directly on node density. The major question is centered on the network coverage problem, how can we guarantee that each point of the region is covered by the required number of sensors? To deal with this, probabilistic intrusion detection models are adopted, called single and multi sensing probability detection and the deployment quality issue is surveyed and analyzed in terms of coverage. We evaluate our probabilistic model in homogeneous wireless sensor network, in term of sensing range, node density, and intrusion distance.

Noureddine Assad, Brahim Elbhiri, Sanaa El Fkihi, My Ahmed Faqihi, Mohamed Ouadou, Driss Aboutajdine

Short: A Case Study of the Performance of an OpenFlow Controller

Abstract

Over the last four years there has been significant growth in the interest that researchers and IT industry have shown in a new network architecture approach called Software-Defined Networking (SDN). This new approach is based on the separation between the control plane (routing decisions) and the data plane (packet forwarding). Communication between these two planes is mainly established today by the OpenFlow protocol. The interest of SDN is that it allows network programmability through applications acting on the control plane and hence it facilitates the development of new network protocols and services. However, there are some problems of performance and scalability when a single centralized controller is deployed in an SDN architecture. In this paper, we briefly introduce SDN, OpenFlow and review performance studies. After, we study through some experiments the performance issues of the Ruy OpenFlow controller especially in a large-scale network case.

Fouad Benamrane, Mouad Ben Mamoun, Redouane Benaini

Short: Gossip-Based Sampling in Social Overlays

Abstract

Performance of many P2P systems depends on the ability to construct a random overlay network among the nodes. Current state-of-the-art techniques for constructing random overlays have an implicit requirement that any two nodes in the system should always be able to communicate and establish a link between them. However, this is not the case in some of the environments where distributed systems are required to be deployed, e.g., Decentralized Online Social Networks, Wireless networks, or networks with limited connectivity because of NATs/firewalls, etc. In this paper we propose a gossip based peer sampling service capable of running on top of such restricted networks and producing an on-the-fly random overlay. The service provides every participating node with a set of uniform random nodes from the network, as well as efficient routing paths for reaching those nodes via the restricted network.

Mansour Khelghatdoust, Sarunas Girdzijauskas

Short: Graphical Specification and Automatic Verification of Business Process

Abstract

This paper deals with the integration of the formal verification techniques of business process (BP) in the design phase. In order to achieve this purpose, we use the graphical notation of Business Process Modeling Notation (BPMN) for modeling BP and specifying constraint properties to be verified. A formal semantics for some response properties are given.

Outman El Hichami, Mohammed Al Achhab, Ismail Berrada, Badr Eddine El Mohajir

Backmatter