Locality-sensitive hashing (LSH) is an established method for fast data indexing and approximate similarity search, with useful parallelism properties. Although indexes and similarity measures are key for data clustering, little has been investigated on the multifaceted benefits of LSH in the problem. We show how approximate DBSCAN clustering can be fused into the process of creating an LSH index, and, through parallelization and fine-grained synchronization, also utilize efficiently available computing capacity. The resulting algorithm, I P . L S H . D B S C A N , described in this article, can support a wide range of applications with diverse distance functions, as well as data distributions and dimensionality. We analyse the algorithm’s asymptotic completion time and provide an open-source prototype implementation. We also conduct a detailed evaluation measuring latency and accuracy metrics of I P . L S H . D B S C A N , on a 36-core machine with 2-way hyper threading on massive data-sets with various numbers of dimensions. The analysis and the empirical study of I P . L S H . D B S C A N show how it complements the landscape of established state-of-the-art methods, by offering up to several orders of magnitude speed-up on higher dimensional datasets, with tunable high clustering accuracy.

Computer Vision (CV) tasks are among the most pivotal, yet challenging, operations for Uncrewed Aerial Vehicles (UAVs), especially in mission-critical applications. They require processing complex image data through Deep Neural Networks (DNNs), which demand computational resources far beyond UAVs’ capacity. To address this limitation, Split DNNs offer a promising solution by partitioning the model into: (i) a lightweightHead, deployed on the UAV for rapid, albeit less precise, initial image representations, and (ii) a more complexTail, executed at the network edge for refined, higher-accuracy results. However, this solution necessitates transmitting large tensor data from the UAV to the edge server, leading to significant bandwidth consumption. We tackle this challenge by introducing a goal-oriented framework named Compressed Tensor-based DNN Split (CoTeD). Our framework integrates an application- and system-aware optimization model that orchestrates computing and transmission resources in real time. At the UAV, CoTeD dynamically selects relevant tensor information and optimally trades-off between DNN detection quality and bandwidth consumption, guided by application requirements and system operational conditions. At the edge server, CoTeD reconstructs the tensor, enabling efficient inference by the Tail model. This approach effectively balances bandwidth usage with quality of the CV task output. Experimental results, obtained through our hardware-software testbed and using datasets with different sizes and characteristics, show that CoTeD can reduce data transmission over the radio link by up to 90% without noticeable loss in object detection quality and inference latency by up to 70% compared to local DNN deployment onboard the UAV. Also, CoTeD yields an inference request success rate of at least 90%, with an increase of 20%-80% compared to direct DNN splitting, static JPEG compression, and DNN model quantization.

Data sketches balance resource efficiency with controllable approximations for extracting features in high-volume, high-rate data. Two important points of interest are highlighted separately in recent works; namely, to (1) answer multiple types of queries from a single data structure built in one pass over the data, and (2) perform both queries and updates concurrently. In this work, we now tackle the new challenges arising when combining these useful directions together.We investigate the trade-offs around efficiency, consistency, and accuracy to be balanced and synthesize key ideas into LMQ-Sketch, a single, composite data sketch supporting concurrent updates and multiple queries (frequency point queries, frequency moments F₁, and F₂ as representative selection). Our method "Lagom" is a cornerstone of LMQ-Sketch for low-latency global querying (<100µs), combining freshness, timeliness, and accuracy with a low memory footprint and high throughput (>2B updates/s). We analyze and evaluate the accuracy of Lagom, which builds on a simple geometric argument and efficiently combines work distribution with synchronization for proper concurrency semantics - monotonicity of operations and intermediate value linearizability. Comparing with state-of-the-art methods, which, as mentioned, provide either mixed queries or concurrency separately, LMQ-Sketch shows highly competitive throughput, with additional accuracy guarantees and concurrency semantics, while also reducing the required memory budget by an order of magnitude. We expect the methodology to have broader impact on concurrent multi-query sketches.

The frequent elements problem, a key component in demanding stream-data analytics, involves selecting elements whose occurrence exceeds a user-specified threshold. Fast, memory-efficient ϵ -approximate synopsis algorithms select all frequent elements but may overestimate them depending on ϵ (user-defined parameter). Evolving applications demand performance only achievable by parallelization. However, algorithmic guarantees concerning concurrent updates and queries have been overlooked. We propose Query and Parallelism Optimized Space-Saving (QPOPSS ), providing concurrency guarantees. A cornerstone of the design is a new approach for the main data structure for the Space-Saving algorithm, enabling support of very fast queries. QPOPSS integrates this, minimal overlap with concurrent updates, with the distribution of work and fine-grained synchronization among threads, swiftly balancing high throughput, high accuracy, and low memory consumption. Our analysis shows space and approximation bounds under various concurrency and data distribution conditions. Our empirical evaluation relative to representative state-of-the-art methods reveals that QPOPSS 's multi-threaded throughput scales linearly while maintaining the highest accuracy, with orders of magnitude smaller memory footprint.

Finding heavy hitters in databases and data streams is a fundamental problem with applications ranging from network monitoring to database query optimization, machine learning, and more. Approximation algorithms offer practical solutions, but they present tradeoffs involving throughput, memory usage, and accuracy. Moreover, modern applications further complicate these trade-offs by demanding capabilities beyond sequential processing that require both parallel scaling and support for concurrent queries and updates. Analysis of these trade-offs led us to the key idea behind our proposed streaming algorithm, Cuckoo Heavy Keeper (CHK). The approach introduces an inverted process for distinguishing frequent from infrequent items, which unlocks new algorithmic synergies that were previously inaccessible with conventional approaches. By further analyzing the competing metrics with a focus on parallelism, we propose an algorithmic framework that balances scalability aspects and provides options to optimize query and insertion efficiency based on their relative frequencies. The framework is capable of parallelizing any heavy-hitter detection algorithm. Besides the algorithms' analysis, we present an extensive evaluation on both real-world and synthetic data across diverse distributions and query selectivity, representing the broad spectrum of application needs. Compared to state-of-the-art methods, CHK improves throughput by 1.7–5.7X and accuracy by up to four orders of magnitude even under low-skew data and tight memory constraints. These properties allow its parallel instances to achieve near-linear scale-up and low latency for heavy-hitter queries, even under a high query rate. We expect the versatility of CHK and its parallel instances to impact a broad spectrum of tools and applications in large-scale data analytics and stream processing systems.

Forward Provenance for streaming queries run by distributed and parallel Stream Processing Engines gives fine-grained insights on input-output data dependencies enabling, e.g., precise debugging and smart data selection. State-of-the-art provenance frameworks, though, build on an assumption that is unrealistic for distributed systems like Vehicular Networks and Smart Grids, namely, that the whole set of queries in need of provenance is known in advance and static. In real-world use cases, queries are continuously added, removed, and modified over time by both data analysts and SPE systems themselves. Motivated by the lack of solutions for the forward provenance of dynamic sets of queries, we introduce a novel framework, named Nona, for parallel and distributed streaming queries. We formalize the notion of forward provenance for evolving query sets and prove it is possible to extend the same guarantees the state-of-the-art offers for static query sets. Our evaluation shows that Nona can cope with adaptations to changes in query sets with sub-second responsiveness; moreover, it incurs negligible overheads compared to the state-of-the-art, during the periods in which a query set does not undergo changes.

Stream Processing Engines (SPEs) extract value from data streams in the Edge-to-Cloud continuum through graphs of operators that progressively transform data.

Clustering is a common task in data analysis applications. Despite the extensive literature, the continuously increasing volumes of data produced by sensors (e.g., rates of several MB/s by 3D scanners such as LIDAR sensors), and the time-sensitivity of the applications leveraging the clustering outcomes (e.g., detecting critical situations such as detecting boundary crossing from a robot arm that could injure human beings) demand for efficient data clustering algorithms that can effectively utilize the increasing computational capacities of modern hardware. To that end, we leverage approximation and parallelization, where the former is to scale down the amount of data, and the latter is to scale up the computation. Regarding parallelization, we explore a design space for synchronization and workload distribution among the threads. As we study different parts of the design space, we propose representative Parallel Multiphase Approximate Cluster Combining, abbreviated as PARMA-CC, algorithms. We show that PARMA-CC algorithms yield equivalent clustering outcomes despite their different approaches. Furthermore, we show that certain PARMA-CC algorithms can achieve higher efficiency with respect to certain properties of the data to be clustered. Generally speaking, in PARMA-CC algorithms, parallel threads compute summaries associated with clusters of data (sub)sets. As the threads concurrently combine the summaries, they construct a comprehensive summary of the sets of clusters. By approximating a cluster with its respective geometrical summaries, PARMA-CC algorithms scale well with increased data volumes, and, by computing and efficiently combining the summaries in parallel, they enable latency improvements. PARMA-CC algorithms utilize special data structures that enable parallelism through in-place data processing. As we show in our analysis and evaluation, PARMA-CC algorithms can complement and outperform well-established methods, with significantly better scalability, while still providing highly accurate results in a variety of data sets, even with skewed data distributions, which cause the traditional approaches to exhibit their worst-case behaviour.

Concurrent algorithmic implementations of Stochastic Gradient Descent (SGD) give rise to critical questions for compute-intensive Machine Learning (ML). Asynchrony implies speedup in some contexts, and challenges in others, as stale updates may lead to slower, or non-converging executions. While previous works showed asynchrony-adaptiveness can improve stability and speedup by reducing the step size for stale updates according to static rules, there is no one-size-fits-all adaptation rule, since the optimal strategy depends on several factors. We introduce (i) $\mathtt{ASAP.SGD}$, an analytical framework capturing necessary and desired properties of staleness-adaptive step size functions and (ii) \textsc{tail}-$\tau$, a method for utilizing key properties of the execution instance, generating a tailored strategy that not only dampens the impact of stale updates, but also leverages fresh ones. We recover convergence bounds for adaptiveness functions satisfying the $\mathtt{ASAP.SGD}$ conditions for general, convex and non-convex problems, and establish novel bounds for ones satisfying the Polyak-Lojasiewicz property. We evaluate \textsc{tail}-$\tau$ with representative AsyncSGD concurrent algorithms, for Deep Learning problems, showing \textsc{tail}-$\tau$ is a vital complement to AsyncSGD, with (i) persistent speedup in wall-clock convergence time in the parallelism spectrum, (ii) considerably lower risk of non-convergence, as well as (iii) precision levels for which original SGD implementations fail.

In data streaming, why-provenance can explain why a given outcome is observed but offers no help in understanding why an expected outcome is missing. Explaining missing answers has been addressed in DBMSs, but these solutions are not directly applicable to the streaming setting, because of the extra challenges posed by limited storage and by the unbounded nature of data streams. With our framework, Erebus , we tackle the unaddressed challenges behind explaining missing answers in streaming applications. Erebus allows users to define expectations about the results of a query, verifying at runtime if such expectations hold, and also providing explanations when expected and observed outcomes diverge (missing answers). To the best of our knowledge, Erebus is the first such solution in data streaming. Our thorough evaluation on real data shows that Erebus can explain the (missing) answers with small overheads, both in low- and higher-end devices, even when large portions of the processed data are part of such explanations.

Stream processing applications extract value from raw data through Directed Acyclic Graphs of data analysis tasks. Shared-nothing (SN) parallelism is the de-facto standard to scale stream processing applications. Given an application, SN parallelism ins9tantiates several copies of each analysis task, making each instance responsible for a dedicated portion of the overall analysis, and relies on dedicated queues to exchange data among connected instances. On the one hand, SN parallelism can scale the execution of applications both up and out since threads can run task instances within and across processes/nodes. On the other hand, its lack of sharing can cause unnecessary overheads and hinder the scaling up when threads operate on data that could be jointly accessed in shared memory. This trade-off motivated us in studying a way for stream processing applications to leverage shared memory and boost the scale up (before the scale out) while adhering to the widely-adopted and SN-based APIs for stream processing applications. We introduceSTRETCH, a framework that maximizes the scale up and offers instantaneous elastic reconfigurations (without state transfer) for stream processing applications. We propose the concept of Virtual Shared-Nothing (VSN) parallelism and elasticity and provide formal definitions and correctness proofs for the semantics of the analysis tasks supported bySTRETCH, showing they extend the ones found in common Stream Processing Engines. We also provide a fully implemented prototype and show thatSTRETCH's performance exceeds that of state-of-the-art frameworks such as Apache Flink and offers, to the best of our knowledge, unprecedented ultra-fast reconfigurations, taking less than 40 ms even when provisioning tens of new task instances.

Stochastic Gradient Descent (SGD) is an essential element in Machine Learning (ML) algorithms. Asynchronous shared-memory parallel SGD (AsyncSGD), including synchronization-free algorithms, e.g. HOGWILD!, have received interest in certain contexts, due to reduced overhead compared to synchronous parallelization. Despite that they induce staleness and inconsistency, they have shown speedup for problems satisfying smooth, strongly convex targets, and gradient sparsity. Recent works take important steps towards understanding the potential of parallel SGD for problems not conforming to these strong assumptions, in particular for deep learning (DL). There is however a gap in current literature in understanding when AsyncSGD algorithms are useful in practice, and in particular how mechanisms for synchronization and consistency play a role. We contribute with answering questions in this gap by studying a spectrum of parallel algorithmic implementations ofAsyncSGD, aiming to understand how shared-data synchronization influences the convergence properties in fundamental DL applications. We focus on the impact of consistency-preserving non-blocking synchronization in SGD convergence, and in sensitivity to hyper-parameter tuning. We propose Leashed-SGD, an extensible algorithmic framework of consistency-preserving implementations of AsyncSGD, employing lock-free synchronization, effectively balancing throughput and latency. Leashed-SGD features a natural contention-regulating mechanism, as well as dynamic memory management, allocating space only when needed. We argue analytically about the dynamics of the algorithms, memory consumption, the threads' progress over time, and the expected contention. We provide a comprehensive empirical evaluation, validating the analytical claims, benchmarking the proposed Leashed-SGD framework, and comparing to baselines for two prominent deep learning (DL) applications: multilayer perceptrons (MLP) and convolutional neural networks (CNN). We observe the crucial impact of contention, staleness and consistency and show how, thanks to the aforementioned properties, Leashed-SGD provides significant improvements in stability as well as wall-clock time to convergence (from 20-80% up to 4 x improvements) compared to the standard lock-based AsyncSGD algorithm and HOGWILD!, while reducing the overall memory footprint.

Data streaming applications in Cyber-Physical Systems enable high-throughput, low-latency transformations of raw data into value. The performance of such applications, run by Stream Processing Engines (SPEs), can be boosted through custom CPU scheduling. Previous schedulers in the literature require alterations to SPEs to control the scheduling through user-level threads. While such alterations allow for fine-grained control, they hinder the adoption of such schedulers due to the high implementation cost and potential limitations in application semantics (e.g., blocking I/O).

The inherently large and varying volumes of information generated in large scale systems demand near real-time processing of data streams. In this context, data streaming is imperative for data-intensive processing infrastructures. Stream joins, the streaming counterpart of database joins, compare tuples coming from different streams and constitute one of the most important and expensive data streaming operators. Algorithmic implementations of stream joins have to be capable of efficiently processing bursty and rate-varying data streams in a deterministic and skew-resilient fashion. To leverage the design of modern multicore architectures, scalability and parallelism need to be addressed also in the algorithmic design. In this paper we present ScaleJoin, an algorithmic construction for deterministic and parallel stream joins that guarantees all the above properties, thus filling in a gap in the existing state-of-the-art. Key to the novelty of ScaleJoin is the ScaleGate data structure and its lock-free implementation. ScaleGate facilitates concurrent data exchange and balances independent actions among processing threads; enabling fine-grain parallelism and deterministic processing. It allows ScaleJoin to run on an arbitrary number of processing threads, evenly sharing the overall comparisons run in parallel and achieving disjoint and skew-resilient high processing throughput and low processing latency.

Sketches are data structures designed to answer approximate queries by trading memory overhead with accuracy guarantees. More specifically, sketches efficiently summarize large, high-rate streams of data and quickly answer queries on these summaries. In order to support such high throughput rates in modern architectures, parallelization and support for fast queries play a central role, especially when monitoring unpredictable data that can change rapidly as, e.g., in network monitoring for large-scale denial-of-service attacks. However, most existing parallel sketch designs have focused either on high insertion rate or on high query rate, and fail to support cases when these operations are concurrent.

Data streaming enables online monitoring of large and continuous event streams in Cyber-Physical Systems (CPSs). In such scenarios, fine-grained backward provenance tools can connect streaming query results to the source data producing them, allowing analysts to study the dependency/causality of CPS events. While CPS monitoring commonly produces many events, backward provenance does not help prioritize event inspection since it does not specify if an event's provenance could still contribute to future results. To cover this gap, we introduce Ananke , a framework to extend any fine-grained backward provenance tool and deliver a live bipartite graph of fine-grained forward provenance. With Ananke , analysts can prioritize the analysis of provenance data based on whether such data is still potentially being processed by the monitoring queries. We prove our solution is correct, discuss multiple implementations, including one leveraging streaming APIs for parallel analysis, and show Ananke results in small overheads, close to those of existing tools for fine-grained backward provenance.

Pattern matching is an important building block for many security applications, including Network Intrusion Detection Systems (NIDS). As NIDS grow in functionality and complexity, the time overhead and energy consumption of pattern matching become a significant consideration that limits the deployability of such systems, especially on resource-constrained devices. On the other hand, the emergence of new computing platforms, such as embedded devices with integrated, general-purpose Graphics Processing Units (GPUs), brings new, interesting challenges and opportunities for algorithm design in this setting: how to make use of new architectural features and how to evaluate their effect on algorithm performance. Up to now, work that focuses on pattern matching for such platforms has been limited to specific algorithms in isolation.

Stochastic Gradient Descent (SGD) is very useful in optimization problems with high-dimensional non-convex target functions, and hence constitutes an important component of several Machine Learning and Data Analytics methods. Recently there have been significant works on understanding the parallelism inherent to SGD, and its convergence properties. Asynchronous, parallel SGD (AsyncPSGD) has received particular attention, due to observed performance benefits. On the other hand, asynchrony implies inherent challenges in understanding the execution of the algorithm and its convergence, stemming from the fact that the contribution of a thread might be based on an old (stale) view of the state. In this work we aim to deepen the understanding of AsyncPSGD in order to increase the statistical efficiency in the presence of stale gradients. We propose new models for capturing the nature of the staleness distribution in a practical setting. Using the proposed models, we derive a staleness-adaptive SGD framework, MindTheStep-AsyncPSGD, for adapting the step size in an online-fashion, which provably reduces the negative impact of asynchrony. Moreover, we provide general convergence time bounds for a wide class of staleness-adaptive step size strategies for convex target functions. We also provide a detailed empirical study, showing how our approach implies faster convergence for deep learning applications.

Continuously monitoring sensor readings is an important building block for many IoT applications. The literature offers resourceful methods that minimize the amount of communication required for continuous monitoring, where Geometric Monitoring (GM) is one of the most generally applicable ones. However, GM has unique communication requirements that require specialized network protocols to unlock the full potential of the algorithm. In this work, we show how application and protocol co-design can improve the real-life performance of GM, making it an application of practical value for real IoT deployments. We orchestrate the communication of GM to utilize the properties of a state-of-the-art wireless protocol (Crystal) that relies on synchronous transmissions and is designed for aperiodic traffic, as needed by GM. We bridge the existing gap between the capabilities of the protocol and the requirements of GM, especially in the case of periods of heavy communication. We do so by introducing an in-network aggregation technique relying on latent opportunities for aggregation that we exploit in Crystal's design, allowing us to reliably monitor duplicate-sensitive aggregate functions, such as sum, average or variance. Our results from testbed experiments with a publicly available dataset show that the combination of GM and Crystal results in a very small duty-cycle, a 2.2x - 3.2x improvement compared to the baseline and up to 10x compared to previous work. We also show that our in-network aggregation technique reduces the duty-cycle by up to 1.38x.

Cloud computing is revolutionizing the backbone of data analysis applications, including industrial ones. One of its main pillars is the separation of the logic with which data is accessed (e.g., to study the efficiency of a manufacturing system) from the actual hardware (e.g., server) that maintains and analyses the data. Large distributed cyber-physical systems enabled by, among other technologies, the Internet of Things (IoT), made nonetheless clear that “what to do” with the data and “where to do it” are not disjoint problems; i.e., cloud computing on its own is not enough. Fog and edge computing have emerged as complementary options, to distribute the analysis, helping with challenges by means of close-to-the-source data analysis.We show for a key problem for industrial processes, that of shifting bottleneck detection, how to take advantage of such multi-tier computing architectures, to perform continuous and configurable analysis of data from Manufacturing Execution Systems. We propose a processing framework, STRATUM, and an algorithm, AMBLE, for continuous, data stream processing. STRATUM seamlessly distributes and parallelizes the processing across the tiers and AMBLE guarantees consistent analysis in spite of timing fluctuations, which are commonly introduced due to e.g. the communication system; it also achieves efficiency through appropriate data structures for in-memory processing. The experimental study on a real-world dataset, taken from a production line over two years and including 8.5 million entries, shows the benefits of the proposed solution in enabling configurable and efficient analysis.

Applications for adaptive (sometimes also called smart) Cyber-Physical Systems are blossoming thanks to the large volumes of data, sensed in a continuous fashion, in large distributed systems. The benefits of these applications come nonetheless with a price: the need for jointly addressing challenges in efficient data communication and analysis (among others). The goal of the DRIVEN framework, presented here, is to address these challenges for a data gathering and distance-based clustering tool in the context of vehicular networks. Because of the limited communication bandwidth (compared to the volume of sensed data) of vehicular networks and the monetary costs of data transmission, the intuition behind DRIVEN is to avoid gathering the data to be clustered in a raw format from each vehicle, but rather to allow for a streaming-based error-bounded approximation, through Piecewise Linear Approximation, to compress the volumes of data to be gathered. At the same time, rather than relying on a batch-based clustering algorithm that requires all the data to be first gathered (and then clustered), DRIVEN relies on and extends a streaming-based clustering algorithm that leverages the inherent ordering of the spatial and temporal data being collected, to perform the clustering in an online fashion, while data is being retrieved. As we show, based on our prototype implementation using Apache Flink and our evaluation with real-world data such as GPS and LiDAR, the accuracy loss for the clustering performed on the reconstructed data can be small, even when the raw data is compressed to 10-35% of its original size, and the transferring of data itself can be completed in up to one-tenth of the duration observed when gathering raw data.

In distributed digitalized environments in the context of the Internet of Things, we often need to do an analysis of big data originating at high rate-sensors at the edge of the infrastructure. A characteristic example is the light detection and ranging (LiDAR) technology, that allows sensing surrounding objects with fine-grained resolution in large areas. Their data (known as point clouds), generated continuously at very high rates, through appropriate analysis can provide information to support automated functionality in distributed cyber-physical? systems; clustering of point clouds is a key problem to extract this type of information. Methods for solving the problem in a continuous fashion can facilitate improved processing in fog architectures, through enabling low-latency, efficient continuous and streaming processing of data close to the sources; moreover, parallelism is a key requirement to exploit a variety of computing architectures in this context. We proposeLisco, a single-pass continuous Euclidean-distance-based clustering of LiDAR point clouds, that maximizes the granularity of the data processing pipeline and thus shows the potential for data-and pipeline-parallelism. We further present its parallel version, P-Lisco, that is architecture-independent and exploits the parallelism revealed byLisco'salgorithmic approach. Besides their algorithmic analysis, we provide a thorough experimental evaluation on architectures representative of high-end servers and of resource-constrained embedded devices and highlight the multiplicative improvements and scalability benefits of the proposed algorithms compared to the baseline, using both real-world datasets as well as synthetic ones to fully explore a wide spectrum of stress-levels for the algorithms.

Applications for IoT often continuously monitor sensor values and react if the network-wide aggregate exceeds a threshold. Previous work on Geometric monitoring (GM) has promised a several-fold reduction in communication but been limited to analytic or high-level simulation results. In this paper, we build and evaluate a full system design for GM on resource-constrained devices. In particular, we provide an algorithmic implementation for commodity IoT hardware and a detailed study regarding duty cycle reduction and energy savings. Our results, both from full-system simulations and a publicly available testbed, show that GM indeed provides several-fold energy savings in communication. We see up to 3x and 11x reduction in duty-cycle when monitoring the variance and average temperature of a real-world data set, but the results fall short compared to the reduction in communication (4.3x and 44x, respectively). Hence, we investigate the energy overhead imposed by the network stack and the communication pattern of the algorithm and summarize our findings. These insights may enable the design of protocols that will unlock more of the potential of GM and similar algorithms for IoT deployments.

Fine-grained data provenance in data streaming allows linking each result tuple back to the source data that contributed to it, something beneficial for many applications (e.g., to find the conditions triggering a security- or safety-related alert). Further, when data transmission or storage has to be minimized, as in edge computing and cyber-physical systems, it can help in identifying the source data to be prioritized.

Pattern matching is a key building block of Intrusion Detection Systems and firewalls, which are deployed nowadays on commodity systems from laptops to massive web servers in the cloud. In fact, pattern matching is one of their most computationally intensive parts and a bottleneck to their performance. In Network Intrusion Detection, for example, pattern matching algorithms handle thousands of patterns and contribute to more than 70% of the total running time of the system.In this paper, we introduce efficient algorithmic designs for multiple pattern matching which (a) ensure cache locality and (b) utilize modern SIMD instructions. We first identify properties of pattern matching that make it fit for vectorization and show how to use them in the algorithmic design. Second, we build on an earlier, cache-aware algorithmic design and we show how cache-locality combined with SIMD gather instructions, introduced in 2013 to Intel's family of processors, can be applied to pattern matching. We evaluate our algorithmic design with open data sets of real-world network traffic:Our results on two different platforms, Haswell and Xeon-Phi, show a speedup of 1.8x and 3.6x, respectively, over Direct Filter Classification (DFC), a recently proposed algorithm by Choi et al. for pattern matching exploiting cache locality, and a speedup of more than 2.3x over Aho-Corasick, a widely used algorithm in today's Intrusion Detection Systems.

Vehicle-to-vehicle (V2V) communication is a crucial component of the future autonomous driving systems since it enables improved awareness of the surrounding environment, even without extensive processing of sensory information. However, V2V communication is prone to failures and delays, so a distributed fault-tolerant approach is required for safe and efficient transportation. In this paper, we focus on the intersection crossing (IC) problem with autonomous vehicles that cooperate via V2V communications, and propose a novel distributed IC algorithm that can handle an unknown and large (yet finite) number of communication failures. Our analysis shows that both safety and liveness requirements are satisfied in all realistic situations. We also found, based on a real data set, that the crossing delay is only slightly increased even in the presence of highly correlated failures.

The introduction of Advanced Metering Infrastructures in electricity networks brings new means of dealing with issues influencing financial margins and system-safety problems, thanks to the information reported continuously by smart meters. Such an issue is the detection of Non-Technical Losses (NTLs) in electric power grids. We introduce a data-driven method, called Structure&Detect, to identify possible sources of NTLs; the method is based on spectral analysis of structural periodic patterns in consumption traces, that allows for scalable processing, using features in the frequency domain. Structure&Detect uses only on consumption traces, with no need for exogenous data about customers (e.g., trust or credit history) or explicit information from domain experts. As such, it complies better with privacy concerns that may be present when processing data from different sources. Using real-world consumption traces, we show that it provides high accuracy and detection rates comparable to methods that require additional, customer-specific information. Moreover, Structure&Detect can also be used orthogonally due to its high detection rate, as a filter, providing a narrowed-down input set to methods requiring different treatment (e.g. additional data or on-site inspection) and thus make the search for NTLs more scalable. Structure&Detect also enables processing each meter trace on-the-fly, as well as in a parallel and distributed fashion. These properties make Structure&Detect suitable for online analysis that can address common big data challenges such as the need for scalable, distributed and parallel analysis close to IoT edge devices, such as smart meters.

Vehicular sensors able to perceive and measure the environment, ranging from in-vehicle sensors to speed cameras, are revolutionizing how technology can interact with our daily lives, enabling Intelligent Vehicular Systems (IVSs). These sensors generate large volumes of data which can reveal useful information for enhancing the sustainable development (through improved utilization of resources), as well as the safety and functionality of the system. In this context, a key challenge is to reduce the large data streams into manageable sets of valuable information in a real-time, reliable and cost-affordable fashion. Due to the data volume size and velocity, relying exclusively on traditional data processing systems, such as databases and batch processing, is no longer a suitable option, since it is not feasible to store the data to later process it. Moreover, careful decisions should be made to leverage the existing computing capacity, from embedded devices found in the IVSs to cloud infrastructures. In this paper we study trade-offs of possible options for data-stream processing models and computing infrastructures. Through building an experimental platform that emulates realistic components of a future deployable IVS and validating two different data-stream processing systems with a wellknown benchmark for IVSs, we study options and trade-offs in real-time data stream processing in IVS infrastructures. Our evaluation shows that existing data-stream processing models can be leveraged in different ways, based on the processing requirements.

The inherently large and varying volumes of data generated to facilitate autonomous functionality in large scale cyber-physical systems demand near real-time processing of data streams, often as close to the sensing devices as possible. In this context, data streaming is imperative for data-intensive processing infrastructures. Stream joins, the streaming counterpart of database joins, compare tuples coming from different streams and constitute one of the most important and expensive data streaming operators. Dictated by the needs of big data streaming analytics, algorithmic implementations of stream joins have to be capable of efficiently processing bursty and rate-varying data streams in a deterministic and skew-resilient fashion. To leverage the design of modern multicore architectures, scalability and parallelism need to be addressed also in the algorithmic design. In this paper we present ScaleJoin, an algorithmic construction for deterministic and parallel stream joins that guarantees all the above properties, thus filling in a gap in the existing state-of-the art. Key to the novelty of ScaleJoin is a new data structure, Scalegate, and its lock-free implementation. ScaleGate facilitates concurrent data exchange and balances independent actions among processing threads; it also enables fine-grain parallelism while providing the necessary synchronization for deterministic processing. As a result, it allows ScaleJoin to run on an arbitrary number of processing threads that can evenly share the overall comparisons run in parallel and achieve high processing throughput and low processing latency. As we show, ScaleJoin not only guarantees deterministic, disjoint and skew-resilient parallelism, but also achieves higher throughput than state-of-the-art parallel stream joins.

Concurrent data structures provide the means to multi-threaded applications to share data. Data structures come with a set of predefined operations, specified by the semantics of the data structure. In the literature and in several contemporary commonly used programming environments, the notion of iteration has been introduced for collection data structures, as a bulk operation enhancing the native set of operations. Iterations in several of these contexts have been treated as sequential in nature and may provide weak consistency guarantees when running concurrently with the native operations of the data structures. In this work we study iterations in concurrent data structures in the context of concurrency with the native operations and the guarantees that they provide. Besides invariability, we propose a set of consistency specifications for such bulk operations, including also concurrency-aware properties by building on Lamppost's systematic definitions for registers. Furthermore, by using queues and composite registers as case-studies of underlying objects, we provide a set of constructions of iteration operations, satisfying the properties and showing containment relations. Besides the trade-off between consistency and throughput, we point out and study trade-off between the overhead of the bulk operation and possible support (helping) by the native operations of the data structure.

Cyber-Physical Systems (CPS) employ sensors to observe physical environments and to detect events of interest. Equipped with sensing, computing, and communication capabilities, Cyber-Physical Systems aim to make physical-systems smart(er). For example, smart electricity meters nowadays measure and report power consumption as well as critical events such as power outages. However, each day, such sensors report a variety of warnings and errors: many merely indicate transient faults or short instabilities of the physical system (environment). Thus, given the big volumes of data, the time-efficient processing of these events, especially in large-scale scenarios with hundreds of thousands of sensors, is a key challenge in CPSs. Motivated by the fact that critical events of CPSs often have temporal-spatial properties, we focus on identifying critical events by an online temporal-spatial analysis on the data stream of messages. We explicitly model the online detection problem as a single-linkage clustering on a data stream over a sliding-window, where the inherent computational complexity of the detection problem is derived. Based on this model, we propose a grid-based single-linkage clustering algorithm over a sliding-window, which is an online time-space efficient method satisfying the quick processing demand of big data streams. We analyze the performance of the proposed approach by both a series of propositions and a large, real-world data-set of deployed CPS, composing 300,000 sensors, over one year. We show that the proposed method identifies above 95% of the critical events in the data-set and save the time-space requirement by 4 orders of magnitude compared with the conventional clustering method.

We briefly describe our study on the problem of streaming multiway aggregation, where large data volumes are received from multiple input streams. Multiway aggregation is a fundamental computational component in data stream management systems, requiring low-latency and high throughput solutions.We focus on the problem of designing concurrent data structures enabling for low-latency and high-throughput multiway aggregation; an issue that has been overlooked in the literature. We propose two new concurrent data structures and their lock-free linearizable implementations, supporting both order-sensitive and order-insensitive aggregate functions.Results from an extensive evaluation show significant improvement in the aggregation performance,in terms of both processing throughput and latency over the commonly-used techniques based on queues.

Low Power Listening (LPL) MAC protocols are widely used in today's sensors networks for duty cycling. Their simplicity and power efficiency ensures a long network life when nodes are battery driven and their easy deployment and lower cost of maintenance makes them suitable to be used in hard-to-access places and harsh conditions. We argue that to fully utilize energy efficiency provided by LPL, other protocols in the protocol stack should be aware of mechanisms. In this paper, we focus on neighborhood discovery protocols and discuss their energy efficient integration with LPL. Then, we study the possibility of using a completely passive approach for neighborhood discovery in such networks and provide an analytical model for its performance characteristics. We verify our performance model both by simulation and implementation in TinyOS. Our evaluation results confirm the efficiency of our proposed method in duty-cycled sensor networks.

Synchronization is a central issue in concurrency and plays an important role in the behavior and performance of modern programmes. Programming languages and hardware designers are trying to provide synchronization constructs and primitives that can handle concurrency and synchronization issues efficiently. Programmers have to find a way to select the most appropriate constructs and primitives in order to gain the desired behavior and performance under concurrency. Several parameters and factors affect the choice, through complex interactions among (i) the language and the language constructs that it supports, (ii) the system architecture, (iii) possible run-time environments, virtual machine options and memory management support and (iv) applications. We present a systematic study of synchronization strategies, focusing on concurrent data structures. We have chosen concurrent data structures with different number of contention spots. We consider both coarse-grain and fine-grain locking strategies, as well as lock-free methods. We have investigated synchronization-aware implementations in C++, C# (.NET and Mono) and Java. Considering the machine architectures, we have studied the behavior of the implementations on both Intel's Nehalem and AMD's Bulldozer. The properties that we study are throughput and fairness under different workloads and multiprogramming execution environments. For NUMA architectures fairness is becoming as important as the typically considered throughput property. To the best of our knowledge this is the first systematic and comprehensive study of synchronization-aware implementations. This paper takes steps towards capturing a number of guiding principles and concerns for the selection of the programming environment and synchronization methods in connection to the application and the system characteristics.

SUMMARY Group communication is deployed in many evolving Internet‐scale cooperative applications such as multiplayer online games and virtual worlds to efficiently support interaction on information relevant to a potentially very large number of users or objects. Especially peer‐to‐peer based group communication protocols have evolved as a promising approach to allow intercommunication between many distributed peers. Yet, the delivery semantics of robust and scalable protocols such as gossiping is not sufficient to support consistency semantics beyond eventual consistency because no relationship on the order of events is enforced. On the other hand, traditional consistency models provided by reliable group communication providing causal or even total order are restricted to support only small groups. This article proposes thecluster consistencymodel which bridges the gap between traditional and current approaches in supporting both scalability and ordered event delivery. We introduce a dynamic and fault tolerant cluster management method that can coordinate concurrent access to resources in a peer‐to‐peer system and can be used to establishfault‐tolerantconfigurable cluster consistency with predictable reliability, running on top of decentralised probabilistic protocols supporting scalable group communication. This is achieved by a general two‐layered architecture that can be applied on top of the standard Internet communication layers and offers a modular, layered set of services to the applications that need them. Further, we present afault‐tolerantmethod implementing causal cluster consistency with predictable reliability, running on top of decentralised probabilistic protocols supporting group communication. This paper provides analytical and experimental evaluation of the properties regarding the fault tolerance of the approach. Furthermore, our experimental study, conducted by implementing and evaluating the two‐layered architecture on top of standard Internet transport services, shows that the approach scales well, imposes an even load on the system, and provides high‐probability reliability guarantees. Copyright © 2011 John Wiley & Sons, Ltd.

Distributed Denial of Service (DDoS) attacks are hard to deal with, due to the fact that it is difficult to distinguish legitimate traffic from malicious traffic, especially since the latter is from distributed sources. To accurately filter malicious traffic one needs (strong but costly) packet authentication primitives which increase the design complexity and typically affect throughput. It is a challenge to keep a balance between throughput and security/protection of the network core and end resources. In this paper, we propose SIEVE, a lightweight distributed filtering protocol/method. Depending on the attacker's ability, SIEVE can provide a standalone filter for moderate adversary models and a complementary filter which can enhance the performance of strong and more complex methods for stronger adversary models.

The problem of local clock synchronization is studied in the context of media access control (MAC) protocols, such as time division multiple access (TDMA), for dynamic and wireless ad hoc networks. In the context of TDMA, local pulse synchronization mechanisms let neighboring nodes align the timing of their packet transmissions, and by that avoid transmission interferences between consecutive timeslots. Existing implementations for Vehicular Ad-Hoc Networks (VANETs) assume the availability of common (external) sources of time, such as base-stations or geographical positioning systems (GPS). This work is the first to consider autonomic design criteria, which are imperative when no common time sources are available, or preferred not to be used, due to their cost and signal loss. We present self-*pulse synchronization strategies. Their implementing algorithms consider the effects of communication delays and transmission interferences. We demonstrate the algorithms via extensive simulations in different settings including node mobility. We also validate these simulations in the MicaZ platform, whose native clocks are driven by inexpensive crystal oscillators. The results imply that the studied algorithms can facilitate autonomous TDMA protocols for VANETs.

Vehicular system designers often use simulation tools in order to prove vehicular systems. The computational complexity of detailed simulations limits the scale of such testings. Therefore, it is often the case that the first full-scale demonstrations of new concepts for vehicular systems are done in proving grounds and testing tracks. We propose Gulliver as a platform for studying vehicular systems on a large scale open source test-bed of low cost miniature vehicles that use wireless communication and are equipped with onboard sensors. Our approach provides a simpler yet detailed investigation of vehicular systems. This paper presents the platform with its design and a set of applications that could be demonstrated by Gulliver. Gulliver allows the design of vehicular systems to focus on the cyber-physical aspects of the studied problems. We expect that Gulliver will allow affordability and flexibility for a wider range of researchers to directly contribute to the development of future vehicular systems, such as greener transportation initiatives and zero fatality objectives.

Network-based applications commonly open some known communication port(s), making themselves easy targets for (distributed) Denial of Service (DoS) attacks. Earlier solutions for this problem are based on port-hopping between pairs of processes which are synchronous or exchange acknowledgments. However, acknowledgments, if lost, can cause a port to be open for longer time and thus be vulnerable, while time servers can become targets to DoS attack themselves. Here, we extend port-hopping to support multiparty applications, by proposing the BIGWHEEL algorithm, for each application server to communicate with multiple clients in a port-hopping manner without the need for group synchronization. Furthermore, we present an adaptive algorithm, HOPERAA, for enabling hopping in the presence of bounded asynchrony, namely, when the communicating parties have clocks with clock drifts. The solutions are simple, based on each client interacting with the server independently of the other clients, without the need of acknowledgments or time server(s). Further, they do not rely on the application having a fixed port open in the beginning, neither do they require the clients to get a "first-contact” port from a third party. We show analytically the properties of the algorithms and also study experimentally their success rates, confirm the relation with the analytical bounds.

A lock-free bag data structure supporting unordered buffering is presented in this paper. The algorithm supports multiple producers and multiple consumers, as well as dynamic collection sizes. To handle concurrency efficiently, the algorithm was designed to thrive for disjoint-access-parallelism for the supported semantics. Therefore, the algorithm exploits a distributed design combined with novel techniques for handling concurrent modifications of linked lists using double marks, detection of total emptiness, and efficient memory management with hazard pointer handover. Experiments on a 24-way multi-core platform show significantly better performance for the new algorithm compared to previous algorithms of relevance.

A key property of overlay networks, that is going to play an important part in future networking solutions, is the peers' ability to establish connections with other peers based on some suitability metric related to e.g. the node's distance, interests, recommendations, transaction history or available resources. Each node may choose individually an appropriate metric and try to connect or be matched with the available peers that it considers best. When there are no preference cycles among the peers, it has been proven that a stable matching exists, where peers have maximized the individual satisfaction gleaned of their choices. However, no such guarantees are currently being given for the cases where cycles may exist and known methods may not be able to resolve ¿oscillations¿ in preference-based connectivity and reach stability. In this work we employ the use of node satisfaction to move beyond classic stable matchings and towards the overlay network context. We present a simple yet powerful distributed algorithm that uses aggregate satisfaction as an optimization metric. The algorithm is a generalization of an approximation one-to-one matching algorithm, into the many-to-many case. We prove that the total satisfaction achieved by our algorithm is a constant factor approximation of the maximum total satisfaction in the network, depending also on the maximum number of possible connections of a peer in the overlay.

Efficient, scalable memory allocation for multithreaded applications on multiprocessors is a significant goal of recent research. In the distributed computing literature it has been emphasized that lock-based synchronization and concurrency-control may limit the parallelism in multiprocessor systems. Thus, system services that employ such methods can hinder reaching the full potential of these systems. A natural research question is the pertinence and the impact of lock-free concurrency control in key services for multiprocessors, such as in the memory allocation service, which is the theme of this work. We show the design and implementation of NBmalloc , a lock-free memory allocator designed to enhance the parallelism in the system. The architecture of NBmalloc is inspired by Hoard, a well-known concurrent memory allocator, with modular design that preserves scalability and helps avoiding false-sharing and heap-blowup. Within our effort to design appropriate lock-free algorithms for NBmalloc , we propose and show a lock-free implementation of a new data structure, flat-set, supporting conventional “internal” set operations as well as “inter-object” operations, for moving items between flat-sets. The design of NBmalloc also involved a series of other algorithmic problems, which are discussed in the paper. Further, we present the implementation of NBmalloc and a study of its behaviour in a set of multiprocessor systems. The results show that the good properties of Hoard w.r.t. false-sharing and heap-blowup are preserved.

We present an efficient and practical lock-free method for semiautomatic (application-guided) memory reclamation based on reference counting, aimed for use with arbitrary lock-free dynamic data structures. The method guarantees the safety of local as well as global references, supports arbitrary memory reuse, uses atomic primitives that are available in modern computer systems, and provides an upper bound on the amount of memory waiting to be reclaimed. To the best of our knowledge, this is the first lock-free method that provides all of these properties. We provide analytical and experimental study of the method. The experiments conducted have shown that the method can also provide significant performance improvements for lock-free algorithms of dynamic data structures that require strong memory management.

A weak point in network-based applications is that they commonly open some known communication port(s), making themselves targets for denial of service (DoS) attacks. Considering adversaries that can eavesdrop and launch directed DoS attacks to the applications' open ports, solutions based on pseudo-random port-hopping have been suggested. As port-hopping needs that the communicating parties hop in a synchronized manner, these solutions suggest acknowledgment-based protocols between a client-server pair or assume the presence of synchronized clocks. Acknowledgments, if lost, can cause a port to be open for a longer time and thus be vulnerable to DoS attacks; Time servers for synchronizing clocks can become targets to DoS attack themselves. Here we study the case where the communicating parties have clocks with rate drift, which is common in networking. We propose an algorithm, BigWheel, for servers to communicate with multiple clients in a port-hopping manner, thus enabling support to multi-party applications as well. The algorithm does not rely on the server having a fixed port open in the beginning, neither does it require from the client to get a "first-contact" port from a third party. We also present an adaptive algorithm, HoPerAA, for hopping in the presence of clock-drift, as well as the analysis and evaluation of the methods. The solutions are simple, based on each client interacting with the server independently of the other clients, without the need of acknowledgments or time server. Provided that one has an estimation of the time it takes for the adversary to detect that a port is open and launch an attack, the method we propose doesnot make it possible to the eavesdropping adversary to launch an attack directed to the application's open port(s).

LYDIAN is an environment to support the teaching and learning of distributed algorithms. It provides a collection of distributed algorithms as well as continuous animations. Users can combine algorithms and animations with arbitrary network structures defining the interconnection and behavior of the distributed algorithm. Further, it facilitates the creation of algorithm descriptions as well as the creation of network structures. This makes LYDIAN a flexible tool to be used with students with different skills and backgrounds. This article gives an overview about various ideas and concepts behind LYDIAN by describing in detail the framework for an educational visualization and simulation environment for learning/teaching distributed algorithms as well as discussing possible extensions, which may improve possibilities for user interaction. Moreover, in our effort to understand better what visualization and simulation environments, such as LYDIAN, need to provide, we show results taken from a case study integrating LYDIAN in an undergraduate distributed-systems course.

Recent decentralised event-based systems have focused on providing event delivery which scales with increasing number of processes. While the main focus of research has been on ensuring that processes maintain only a small amount of information on maintaining membership and routing, an important factor in achieving scalability for event-based peer-to-peer dissemination system is the number of events disseminated at the same time. This work presents a dynamic and fault tolerant cluster management method which can be used to coordinate concurrent access to resources in a peer-to-peer system. In the context of event-based dissemination systems the cluster management can be used to control the number of concurrently disseminated events. We present and analyse an algorithm implementing the proposed cluster management model in a fault-tolerant and decentralised way. The algorithm provides for each cluster a limited set of tickets. A process which has obtained a ticket may send events corresponding to the resources of the cluster. The algorithm guarantees that no two processes ever issue an event corresponding to the same ticket at the same time. The cluster management model on its own has interesting properties which can be useful for many peer-to-peer applications.

Having small-sized logical clocks with high causal-ordering accuracy is useful, especially where (i) the precision of the knowledge of the causal dependencies among events implies savings in time overhead and (ii) the cost of transmitting full vector clock timestamps - that precisely characterise the causal relation - is high. Plausible clocks can be used as timestamps to order events in a distributed system in a way that is consistent with the causal order as long as the events are causally dependent. We introduce the nonuniformly mapped R-entries vector (NUREV) clocks, a general class of plausible clocks that allow accuracy adaptation and we analyse the ways that these clocks may relate causally independent event pairs. Our analysis resulted in a set of conclusions and the formulation of new, adaptive plausible clocks algorithms, with improved accuracy, even when the number of clock entries is very small, which is important in peer-to-peer communication systems.

Distributed algorithms can be difficult to understand as well as to teach. A way to provide students with an experience of the execution of a distributed algorithm is the use of a simulation-visualisation environment. In this work we present a case study of integrating a simulation-visualisation environment into a distributed system course. We evaluate a distributed system assignment in which students used LYDIAN, an extensible library for distributed algorithms and animations, to implement their algorithms. In our study neither the teachers nor the students had earlier class experience with LYDIAN. The feedback received gives valuable information on what simulation-visualisation environments for distributed algorithms need to provide in order to be successfully used in class. We are not aware of any similar study in the area of distributed computing. However, the feedback we have received shows the significance of such evaluations to help users improve their performance and help them to acknowledge the wealth of tools they are provided.

No abstract available.

The construction of shared data objects is a fundamental issue in asynchronous concurrent systems, since these objects provide the means for communication and synchronization between processes. Constructions which guarantee that concurrent access to the shared object by processes is free from waiting are of particular interest, since they help to increase the amount of parallelism and to provide fault-tolerance. The problem of constructing a $k$-valued wait-free shared register out of binary subregisters of the same type, where each write access consists of one subwrite (constructions with one-write) is important, since it lies at the heart of studying lower bounds of the complexities of register constructions and trade-offs between them. The first such construction was for the safe register case; it uses $k$ binary safe registers and exploits the properties of a rainbow colouring function of a hypercube graph. The best known construction for the regular (atomic) case uses ${k \choose 2}$ binary regular (resp. atomic) registers, while if the one-write requirement is lifted, there exists a construction that uses $4 (\log k+1)$ binary registers. Here we show how rainbow colouring can be extended to simulate handshaking between the reader and the writer of the register, thus offering a wait-free solution for the atomic case with one reader, using only $3k-2$ binary registers. The best known lower bound for such a construction is $k-1$.

We present our work on building interactive continuous visualisations of distributed algorithms for educational purposes. The animations are comprised by a set of visualisation windows. The visualisation windows are designed so that they demonstrate i) the different behaviours of the algorithms while running in different systems, ii) the different behaviours that the algorithms exhibit under different timing and workload of the system iii) the time and space complexities of the algorithms and iv) the "key ideas" of the functionality of the algorithms. Visualisations have been written for a set of lO algorithms that are tought in a Distributed Algorithms advanced undergraduate course.

No abstract available.