Serverless computing has gained increasing interest in recent years for enabling large-scale machine learning tasks. However, training a machine learning model in a serverless setting is a complex task and several challenges need to be addressed particularly in data distribution, result aggregation, resource heterogeneity, failures, container ephemerality, network and execution cost. These difficulties stem from the inherent complexity of distributed computation and the coordination demands of the machine learning algorithms. We propose STRATA2.0, a serverless middleware for Machine Learning training in serverless environments. STRATA2.0 provides a comprehensive suite of mechanisms designed to support efficient training of machine learning models on serverless infrastructures and address key challenges related to efficient data communication, coordination and synchronization, scalable and time efficient training of ML models using heterogeneous containers. Our extensive experimental results demonstrate that STRATA2.0 achieves the same level of accuracy with fewer data points, is on average three times faster in training time compared to centralized approaches, reduces energy consumption by up to 50%, and remains resilient when up to 60% of training instances fail.

This paper addresses the challenges of hosting multiple GPU workloads in resource-constrained edge environments where GPU computation demands often exceeds availability. Traditional approaches to GPU sharing, such as NVIDIA MPS and MIG, have limitations regarding dynamic priority adjustments and hardware compatibility, as several of them require specialized data-center oriented GPUs. To overcome these limitations, we propose a novel, hardware-agnostic GPU spatio-temporal sharing and scheduling mechanism for GPU-intensive, long-running jobs in shared edge clusters requiring non-to-minimum changes in the workload source code. A Local GPU Scheduler Component, can prioritize the execution of each workload based on a set of scheduling policies, including Priority Based Scheduling and Real-Time, Laxity based scheduling in order to achieve the SLOs of time-critical real-time workloads that runs concurrently in the shared GPU. Extensive evaluation on a set of non specialized GPUs with different architectures provides fully insight on the efficiency and the efficacy of the proposed technique.

Routing through large urban areas is a daily problem for the vast majority of the commuters. In this paper, we consider the extension of the routing problem where we want to find the optimal path for different objectives. Specifically, we consider the problem for finding paths that are quick, safe or efficient in the use of resources. Multi-objective routing path optimization is an active research field in the area of path optimization. We present an efficient technique for finding the optimal path which satisfies user defined constraints. Experimental evaluation leads us to the conclusion that multi-objective routing path optimization can be deployed efficiently in terms of computational cost and solution accuracy. We perform experiments comparing our work with a state of the art technique which concerns the multi-objective shortest path optimization problem.

To adapt to the growth of data access resiliency, distributed cloud storage systems are increasingly deploying erasure coding methods with redundancy conversion which adjust their parameters to encode and repair constantly expanding data sets. However, while new parity blocks are generated for updated data groups, any parity blocks created from previous data group updates are not exploited further, or even entirely discarded. This paper proposes EDIC (Elastic Diagonally Interleaved Coding), a middleware that optimizes fault tolerance for converted data groups. EDIC deploys diagonally interleaved coding, an advanced erasure coding method, enhanced by leveraging multiple versions of parity blocks, inspired by the principles of Elastic Reed-Solomon codes. EDIC exploits the parity blocks of a previous version of a converted data group to repair the original, non-converted blocks within the group, while the new parity blocks will cover the recently added blocks, incurring only a minimal storage overhead.

The radical advances in mobile computing, the IoT technological evolution along with cyberphysical components (e.g., sensors, actuators, control centers) have led to the development of smart city applications that generate raw or preprocessed data, enabling workflows involving the city to better sense the urban environment and support citizens’ everyday lives. Recently, a new era of Mobile Edge Cloud (MEC) infrastructures has emerged to support smart city applications that aim to address the challenges raised due to the spatio-temporal dynamics of the urban crowd as well as bring scalability and on-demand computing capacity to urban system applications for timely response. In these, resource capabilities are distributed at the edge of the network and in close proximity to end-users, making it possible to perform computation and data processing at the network edge. However, there are important challenges related to real-time execution, not only due to the highly dynamic and transient crowd, the bursty and highly unpredictable amount of requests but also due to the resource constraints imposed by the Mobile Edge Cloud environment. In this paper, we present TIMBER, our framework for efficiently supporting mobile daTa processing pIpelines in MoBile cloud EnviRonments that effectively addresses the aforementioned challenges. Our detailed experimental results illustrate that our approach can reduce the operating costs by 66.245% on average and achieve up to 96.4% similar throughput performance for agnostic workloads.

Serverless computing has received growing interest in recent years for supporting large-scale machine learning tasks. However, training a machine learning model in a serverless environment is a nontrivial procedure and several challenges still need to be addressed in the data distribution and result aggregation steps as well as the cost of execution due to the inherent complexity of the distributed computation and the coordination required in the learning algorithm. In this work, we focus on Random Forests, a state-of-the-art technique in many Machine Learning applications. We propose STRATA, a cost-effective middleware to train Random Forests atop a serverless environment that successfully addresses these training challenges. As we show in our extensive experimental evaluation STRATA achieves 3X better training times on average compared to a centralized approach and can withstand up to 70% of failures during training.

No abstract available.

The proliferation of smartphone devices has led to the emergence of powerful user services from enabling interactions with friends and business associates to mapping, finding nearby businesses and alerting users in real-time. Moreover, users do not realize that continuously sharing their trajectory data with online systems may end up revealing a great amount of information in terms of their behavior, mobility patterns and social relationships. Thus, addressing these privacy risks is a fundamental challenge. In this work, we present$TP^{3}$, a Privacy Protection system for Trajectory analytics. Our contributions are the following: (1) we model a new type of attack, namely “social link exploitation attack”, (2) we utilize the coresets theory, a fast and accurate technique which approximates well the original data using a small data set, and running queries on the coreset produces similar results to the original data, and (3) we employ the Serverless computing paradigm to accommodate a set of privacy operations for achieving high system performance with minimized provisioning costs, while preserving the users' privacy. We have developed these techniques in our$TP^{3}$system that works with state-of-the-art trajectory analytics apps and applies different types of privacy operations. Our detailed experimental evaluation illustrates that our approach is both efficient and practical.

The problem of privacy protection of trajectory data has received increasing attention in recent years with the significant grow in the volume of users that contribute trajectory data with rich user information. This creates serious privacy concerns as exposing an individual's privacy information may result in attacks threatening the user's safety. In this demonstration we present$TP^{3}$a novel practical framework for supporting trajectory privacy preservation in Mobile Cloud Environments (MCEs). In$TP^{3}$, non-expert users submit their trajectories and the system is responsible to determine their privacy exposure before sharing them to data analysts in return for various benefits, e.g. better recommendations.$TP^{3}$makes a number of contributions: (a) It evaluates the privacy exposure of the users utilizing various privacy operations, (b) it is latency-efficient as it implements the privacy operations as serverless functions which can scale automatically to serve an increasing number of users with low latency, and (c) it is practical and cost-efficient as it exploits the serverless model to adapt to the demands of the users with low operational costs for the service provider. Finally,$TP^{3}$'s Web-UI provides insights to the service provider regarding the performance and the respective revenue from the service usage, while enabling the user to submit the trajectories with recommended preferences of privacy.

In recent years, Sports Analytics has attracted a lot of interest in the research community. This presents an exciting opportunity as there is a plethora of complex, real-time events that can be analyzed to gain better insights or assist in decision-making. In this paper, we address the problem of evaluating actions of players in a football game using Deep Learning techniques. We propose and evaluate four different Deep Learning models, namely, Fully Convolutional Neural Networks, Long Short Term Models and combinations of them, to make more robust predictions for unseen data. Our detailed experimental evaluation illustrates that our approach can be successfully applied to structural data to compute the probabilities of scoring and conceding a goal in future actions.

While there has been a lot of effort in recent years in optimising Big Data systems like Apache Spark and Hadoop, the all-to-all transfer of data between a MapReduce computation step, i.e., the shuffle data mechanism between cluster nodes remains always a serious bottleneck. In this work, we present Cherry, an open-source distributed task-aware Caching sHuffle sErvice for seRveRless analYtics. Our thorough experiments on a cloud testbed using realistic and synthetic workloads showcase that Cherry can achieve an almost 23% to 39% reduction in completion of the reduce stage with small shuffle block sizes, a 10% reduction in execution time on real workloads, while it can efficiently handle Spark execution failures with a constant task time re-computation overhead compared to existing approaches.

Pub/sub systems have been widely utilized in the industry as the connecting piece between high rate producers or mobile clients and end-services, due to their ability to handle messages of high volume and velocity and achieve high throughput. Apache Kafka is one of the most popular Big Data messaging systems. Although Kafka's modular Consumer API allows businesses to take advantage of the rich set of features it provides, it often suffers from improper configured topics/partitions or load imbalances due to spikes or high volume of messages injected in the same topic. In our research our goal is to develop a novel framework which investigates smart queuing mechanisms to overcome these issues and deal effectively with sudden bursts and overloads which are frequently experienced in these systems. Our approach provides rate control capabilities to the Kafka's consumer API which allows us to effectively meet the requirements of different end-services without interference among them.

News portals, such as Yahoo News or Google News, collect large amounts of news articles from a variety of sources on a daily basis. Only a small portion of these documents can be selected and displayed on the homepage. Thus, there is a strong preference for major, recent events. In this work, we propose a scalable First Story Detection (FSD) pipeline that identifies fresh news. This pipeline is used in order to instantiate a variety of FSD approaches. In addition we suggest a novel FSD technique that in comparison to existing systems, relies on relation extraction algorithms and exploits the named entities and their relations in order to decide about the freshness of an article. We evaluate our technique by instantiating existing state of art FSD techniques within our generic pipeline. As ground truth we use multiple datasets that cover different categories. Experimental results demonstrate that our FSD method in many cases provides an improvement over state-of-the-art techniques. In addition, we show using a large synthetic dataset that our general FSD pipeline has constant space and time requirements and is suitable for very high volume streams.

The popularity of Online Social Networks (OSNs) led to numerous applications that harness the benefits of immediate information exchange among numerous users of the network. This property is particularly utilized by OSNs campaigns that exploit of the "word-of-mouth" effect exhibited in the network. The problem Influence Maximization (IM), i.e., identifying the appropriate subset of users to initiate the propagation of a specific campaign, is widely studied in the literature. Various models have been proposed to capture the way information propagates in the network, yet a unified model that considers the important parameters of (i) correlation among campaigns propagating in the network and (ii) the different attributes of the propagating entities coupled with the users distinct preferences in certain attributes, is lacking. Additionally, the majority of the works assume uniform costs and revenues among users. Finally, the IM problem is addressed solely offline, i.e., after the seed selection process no further action is defined. In this work we propose the Multi-Attribute Correlated Independent Cascade (MAC-IC) propagation model to tackle the aforementioned limitations of existing propagation models. Given the MAC-IC model we design a two-phase Greedy Offer Selection (GOES) algorithm to address the IM problem under variable costs and revenues generated by the users. During the offline phase, the seeds to initiate the propagation of a specific item are identified. In the online phase, the propagation is monitored, the blockers are detected and real-time incentives may be offered to convince them to participate in the campaign. We prove that the GOES offline phase achieves an approximation ratio of 1 - 1/e. Through an extensive experimental evaluation we demonstrate the efficiency of our approach compared to state-of-the-art schemes.

In this work we aim to provide an efficient solution to the problem of online task allocation in spatial crowdsourcing systems. We focus on the objectives of platform utility maximization and worker utility maximization, yet the proposed schema is generic enough to accommodate more objectives. The goal is to find an allocation of tasks to workers that maximizes the platform's profit and reliability of the results, while simultaneously assigns tasks based on the users' interests to increase user engagement and hence the probability that the users will complete the tasks on time. Our scheme works well in highly fluctuating environments where the tasks to be executed require that the workers meet certain criteria of expertise, availability, reliability, etc. Our detailed experimental evaluation illustrates the benefits and practicality of our approach and demonstrates that our approach outperforms its competitors.

In recent years we observe a rapid growth in the deployment of machine learning workloads on big data analytics frameworks like Apache Spark and Apache Flink. These workloads are typically represented as graphs, run on shared infrastructures and often have much more demanding resource requirements than those traditionally found in typical enterprise settings. However, predicting the execution times of the workloads is important as they often run on shared public or private infrastructures and, thus, their execution is greatly affected by the resource sharing, the hardware infrastructure utilized as well as the choice of the configuration parameters provided by the frameworks. In this work, we propose a fast and efficient performance prediction system to address the challenge of predicting the execution times of big data workloads, exploiting the fact that workloads are represented as processing graphs and often share similar structures and parameters. Thus, we can use the performance models we have built for already deployed workloads, to estimate the end-to-end execution time for a new workload. Previous works assume that a large number of profiling runs can be utilized for building the prediction models. However, this assumption is not always valid and more elaborate mechanisms need to be applied. Our detailed experimental evaluation on our local Spark cluster illustrates that our approach can predict accurately the execution time of a wide range of Spark workloads.

In recent years, in-memory cache systems have been commonly utilized to help maintain low application response times, compared to traditional relational databases, where the data items are stored in disk drives. Although cache memory systems offer improved performance, running everything in memory might not be cost-effective. In this paper, we present ESCAPe, an elastic high throughput and low latency key-value in-memory cache system. Unlike existing schemes, ESCAPe offers an elastic mechanism that proactively adds or removes nodes to scale-down or scale-up to meet fluctuating application demands, and incorporates a dynamic redistribution scheme that prioritizes the distribution of the keys at the nodes, while keeping the overhead cost as low as possible. We have evaluated our approach in a real cluster, using ESCAPe as the memcache system for Web Applications using different workload traces and comparing our approach with state of the art schemes. Our results illustrate that ESCAPe is able to select the most useful items to keep in memory, significantly reducing the end-to-end latency experienced by the applications.

In this demonstration we present ESCAPe, a framework for automatically monitoring and managing an elastic Redis cache. System administrators can configure ESCAPe in concert with their Redis cluster, to meet application real-time objectives while minimizing the cost associated with scaling the applications. ESCAPe comprises Agents that are deployed at each node in the Redis cluster in order to implement the scaling decisions and apply the proposed eviction policy, and a ESCAPe Manager that communicates with all other nodes and makes the scaling decisions in response to the monitored response times and costs. Finally ESCAPe's Web User Interface visualizes realtime statistics related to response time and the distribution of object types in the cluster nodes as well as historical statistics. The system administrators can further fine-tune the cluster parameters and monitor the impact of their decisions on the application performance and cost.

In recent years we have experienced a wide adoption of novel distributed processing frameworks such as Apache Spark for handling batch and stream processing big data applications. An important aspect that has not been examined in these systems yet, is the energy consumption during the applications' execution. Reducing the energy consumption of modern datacenters is a necessity, as datacenters contribute over 2 percent of the total US electric usage. However, efficiently scheduling applications in distributed processing systems can be challenging as there is a trade-off between minimizing the datacenter's energy usage and satisfying the application performance requirements. In this work we propose, ExpREsS, a scheduler for orchestrating the execution of Spark applications in a way that enables us to minimize the energy consumption while ensuring that the applications' performance requirements are met. Our approach exploits time-series segmentation for capturing the applications' energy usage and execution times, and then applies a novel DVFS technique to minimize the energy consumption. In order to tackle the limited number of application's profiling runs, we exploit regression techniques to predict the applications' execution times and power consumption. Our detailed experimental evaluation using realistic workloads on our local cluster illustrates the working and benefits of our approach.

Online Social Networks (OSNs) are being extensively used in a variety of campaigns, with the objective to raise the awareness of the audience regarding a specific piece of information, e.g, product awareness, political positions, etc. An important characteristic is the correlations of different strength and types, i.e., either positive or negative, that appear among the plethora of information diffused in the network. Therefore, the breadth of the diffusion of a specific campaign is significantly affected by the spread of the correlated information. In addition to the correlations of the diffusing information, another important factor affecting the spread of a specific information, is the network connectivity. Social networks are constantly evolving, with links among users being continuously formed or discontinued and communication patterns being highly fluctuating. The aim of this work is to address the problem of Influence Maximization in Online Social Networks by bridging the gap of the existing literature regarding the plethora of correlated information simultaneously propagating in the network and the dynamic communication patterns observed among users in the network. Towards this, we propose a mechanism that estimates users' interaction probabilities and formulate a propagation model that captures how the exposure to many correlated campaigns impacts on the users' behavior to support any of them. We finally design a greedy seed selection approach that approximates the optimal solution at a ratio of 1 - 1/e and prove through extensive experimental evaluation the superiority of our approach compared to state-of-the-art approaches.

In this paper, we provide a novel approach that enables the execution of top-k join queries over sliding windows in a way that reduces the amount of data that need to be analyzed by the stream processing operators. The main idea is that brokers individually invoke the query on their received messages and forward the top-k results to a stream processing operator that performs the merging of the results and provides to the end-user the final top-k results. Moreover, our system exploits the Bayesian Optimization technique to determine automatically the number of top-k results that should be provided by each broker. Our approach has been developed in the Kappa architecture that exploits topic-based scalable publish/subscribe (pub/sub) systems like Apache Kafka to efficiently forward the high volume of incoming messages to distributed processing systems (i.e., Apache Spark or Apache Flink) that perform the batch and stream analytics operations. Our detailed experimental evaluation on our local cluster illustrates that we can efficiently execute top-k join queries on our system with high accuracy and low latency.

Distributed topic-based publish/subscribe systems like Apache Kafka provide a scalable and decentralized approach to achieve data dissemination. However, despite their wide adoption they can suffer from performance degradation due to the uneven load distribution between the nodes that receive and forward the messages (i.e., brokers). This problem occurs due to the lack of effective load balancing mechanisms that consider the impact of (i) the amount of topics that are handled by a specific broker and (ii) changes in the input rate during the course of the system execution. Furthermore, while there have been some previous works that examine the problem, most of them focus on content-based pub/sub systems or require a centralized coordinator for determining the appropriate assignments. In this work we propose a novel decentralized load balancing technique for topic-based publish/subscribe systems. More specifically, we exploit the fact that brokers in systems like Kafka can communicate using inner topics to exchange their load-related information and propose a novel decentralized algorithm that executes on each individual broker to determine the topics' partitions that should be migrated in order to avoid overloaded conditions. Our detailed experimental evaluation on our local cluster, using different applications that process various data forms from different topics, illustrate the benefits of our approach and show that we can efficiently balance the load between the brokers without the need of a centralized coordination mechanism.

A major challenge for social event organizers (e.g., event planning and marketing companies, venues) is attracting the maximum number of participants, since it has great impact on the success of the event, and, consequently, the expected gains (e.g., revenue, artist/brand publicity). In this paper, we introduce the Social Event Scheduling (SES) problem, which schedules a set of social events considering user preferences and behavior, events' spatiotemporal conflicts, and competing events, in order to maximize the overall number of attendees. We show that SES is strongly NP-hard, even in highly restricted instances. To cope with the hardness of the SES problem we design a greedy approximation algorithm. Finally, we evaluate our method experimentally using a dataset from the Meetup event-based social network.

In this demonstration we presentDionea novel framework for automatic profiling and tuning big data applications. Our system allows a non-expert user to submit Spark or Flink applications to his/her cluster and Dione automatically determines the impact of different configuration parameters on the application's execution time and monetary cost. Dione is the first framework that exploits similarities in the execution plans of different applications to narrow down the amount of profiling runs that are required for building prediction models that capture the impact of the configuration parameters on the metrics of interest. Dione exploits these prediction models to tune the configuration parameters in a way that minimizes the application's execution time or the user's budget. Finally, Dione's Web-UI visualizes the impact of the configuration parameters on the execution time and the monetary cost, and enables the user to submit the application with the recommended parameters' values.

The rapid growth of ubiquitous mobile smart devices has led to the creation of a new era of mobile crowdsourcing applications, where human workers participate and perform tasks in exchange of a monetary reward. Such crowdsourcing systems can play a vital role during emergency events, where fast and accurate responses are needed. However, a commonly ignored aspect is how the price (i.e. the reward paid to workers) must be set in order for the system to meet two important requirements: (i) to timely receive an adequate number of responses which is crucial during emergencies, and (ii) to meet budget constraints. In the majority of the existing systems, the price per task is set up-front and remains unchanged for all upcoming tasks, leading to either higher monetary cost than necessary or to significantly larger latency than expected. In this work, we provide a formulation based on Kalman Filters that enables the system to estimate the user/worker behavior, i.e., the likelihood over time for a user to provide answers for a specific reward. Specifically, we focus on the problem of developing an adaptive pricing policy to incentivize the users to rapidly provide their responses. Our mechanism can be adjusted dynamically to bridge the gap among the users' behavior and the system's needs so as to maximize the overall utility of the system. We simulate our model and through extensive experimental evaluation we show how our system performs and provides benefits to both the users and the system operator.

In recent years we have witnessed a growing interest in trip planning systems aiming at organizing daily travel schedules in smart cities. Such systems use specialized engines to find optimal means of transport between two geospatial endpoints to provide recommendations to citizens for short routes across the city. At the same time, alternative means of transportation, such as bike sharing systems, have enjoyed tremendous success since they offer a green and facile solution for daily commuters and tourists. However, one major challenge of the bike sharing systems is that the distribution of bikes among the stations can be quite uneven during rush hours or due to topography. This often results in shortage of bikes and increasing numbers of disappointed users. Existing works in the literature are limited since they only focus on predicting the demand or apply a-posteriori methods for balancing the load of stations. Furthermore, none of these works consider the benefit of these systems in concert. In this work, we present "MOToR" (MultimOdal Trip Rebalancing), a system that builds upon the OpenTripPlanner framework to incorporate dynamic transit schedule data while balancing the availability of bikes among the bike stations. Our experimental evaluation shows that our approach is practical, efficient and outperforms state-of-the-art methods for route planning.

Bike-sharing systems have enjoyed tremendous success in many major cities around the world today as a new means of urban public transportation offering a green and facile solution for daily commuters and tourists. One common problem featured in these systems is that the distribution of bikes among stations can be quite uneven, due to topography, rush hours or during the occurrence of major events around the city. This often results in shortage of bikes or bike parking racks. An unbalanced bike system means an unreliable form of transportation and disappointed users. Existing works in the literature are limited as they are not designed to handle fluctuating, high or unpredictable demand during large city events that typically affect multiple stations and require rebalancing in real-time, during the event, to ensure seamless operation. In this work, we present “SmartBIKER”, a cost-effective framework for bike sharing systems focusing on major city events. SmartBIKER models bike demand trends during major events, identifies bike stations with low or high demand using a trend forecasting model and determines a relocation strategy that minimizes the relocation cost while maximizing the utility of the stations. Our experimental evaluation shows that our approach is practical, efficient and outperforms state-of-the-art relocation and prediction schemes.

In recent years we are witnessing a growing interest in identifying various aspects affecting the quality of life in smart cities, such as traffic congestion and pollution levels, in order to provide services that enhance the public welfare. In smart cities, sensor infrastructures are deployed around the city combined with data analytics, to monitor and detect in real-time possible anomalies or events of interest. One major challenge that arise in smart-cities is to evaluate the health state of an urban city using heterogeneous multi-source urban data, i.e., pollution and traffic data. Existing works in the literature are limited since they analyze a single source of data, either inferring the air quality or estimating traffic congestion. However, none of these works considers both data sources in concert for estimating the city's health state. In this work, we present “HELIoS” (HEalthy LIving Smart), a framework that combines multiple heterogeneous sources of data, i.e., urban traffic and pollution data, to diagnose the health state of urban areas in a smart city. Our experimental evaluation provides valuable insights into identifying the health state of an urban area, and shows that our approach is both practical and efficient.

In recent years distributed processing frameworks such as Apache Spark have been utilized for running big data applications. Predicting the application's execution time has been an important goal since it can help the end user to determine the necessary processing resources to be reserved. While there have been some previous works that examine the problem of profiling Spark applications, they mainly focus on specific application types (e.g., Machine learning applications) and rely on the existence of a large number of previous execution runs. In this work we aim at overcoming these limitations by minimizing the number of past execution runs needed for the profiling phase. Furthermore, we identify patterns of continuous identical dataset transformations between different applications to cope with the limited historical data availability. We propose an on-line profiling framework, called Dione, that estimates the running times of new applications, even if no historical data is available. Finally, in our detailed experimental evaluation, using practical workloads on our local cluster, we illustrate that our approach accurately predicts the execution times of Spark applications and requires 30% less training time and monetary cost compared to the current state-of-the-art techniques.

Social networks have become the de facto online resource for people to share, comment on and be informed about events pertinent to their interests and livelihood, ranging from road traffic or an illness to concerts and earthquakes, to economics and politics. This has been the driving force behind research endeavors that analyse such data. In this paper, we focus on how Content Networks can help us identify events effectively. Content Networks incorporate both structural and content-related information of a social network in a unified way, at the same time, bringing together two disparate lines of research: graph-based and content-based event discovery in social media. We model interactions of two types of nodes, users and content, and introduce an algorithm that builds heterogeneous, dynamic graphs, in addition to revealing content links in the network's structure. By linking similar content nodes and tracking connected components over time, we can effectively identify different types of events. Our evaluation on social media streaming data suggests that our approach outperforms state-of-the-art techniques, while showcasing the significance of hidden links to the quality of the results.

Social media constitute nowadays one of the most common communication mediums. Millions of users exploit them daily to share information with their community in the network via messages, referred as posts. The massive volume of information shared is extremely diverse and covers a vast spectrum of topics and interests. Automatically identifying the topics of the posts is of particular interest as this can assist in a variety of applications, such as event detection, trends discovery, expert finding etc. However, designing an automated system that requires no human agent participation to identify the topics covered in posts published in Online Social Networks (OSNs) presents manifold challenges. First, posts are unstructured and commonly short, limited to just a few characters. This prevents existing classification schemes to be directly applied in such cases, due to sparseness of the text. Second, new information emerges constantly, hence building a learning corpus from past posts may fail to capture the ever evolving information emerging in OSNs. To overcome the aforementioned limitations we have designed Pythia, an automated system for short text classification that exploits the Wikipedia structure and articles to identify the topics of the posts. The topic discovery is performed in two phases. In the first step, the system exploits Wikipedia categories and articles of the corresponding categories to build the training corpus for the suppervised learning. In the second step, the text of a given post is augmented using a text enrichment mechanism that extends the post with relevant Wikipedia articles. After the initial steps are performed, we deploy k-NN classifier to determine the topic(s) covered in the original post.

Online Social Networks (OSNs) are widely utilized in viral marketing campaigns exploiting the word-of-mouth effect. Various propagation models have been proposed to describe the way cascades unfold in OSNs. Based on the existing propagation models, several studies address the problem of influence maximization, where the objective is to identify an appropriate subset of users to initiate the spread of a contagion. However, existing approaches ignore an important factor in the propagation process, i.e., the correlation of multiple contagions simultaneously cascading in the social network and how these affect the users' decisions regarding the adoption of a contagion. Although recent works look into either the competition or the complementarity among a pair of contagions, a uniform model that describes the propagation of multiple cascades with varying types and degrees of correlations is lacking. This work constitutes the first attempt to fill this gap. We formulate a novel propagation model, the Correlated Contagions Dynamic Linear Threshold (CCDLT), that considers the correlation of many contagions in either competitive or complementary manner. Our proposed model allows for different degrees of competition/complementarity among cascades. We further consider that users may dynamically switch states regarding the contagion they promote during the propagation process, based on the influence of their neighborhoods. We then design a greedy seed selection algorithm that identifies the appropriate subset of users to participate in a specific contagion in order to maximize its spread and we formally prove that it approximates the best solution at a ratio of 1 - 1/e. Through an extensive experimental evaluation we demonstrate the superiority of our approach over existing schemes.

Nowadays distributed processing frameworks like Apache Spark have been successfully used for the execution of big data applications. Despite their wide adoption little work has been done in terms of controlling the applications' energy consumption. Datacenters contribute over 2 % of the total US electric usage therefore minimizing the energy utilization of Spark application can be extremely helpful. Solving this energy consumption problem requires the scheduling of Spark applications in an energy-efficient way. However, the problem is challenging as we also have to consider application performance requirements. In this work, we provide the overview of a novel framework that orchestrates the execution order of Spark applications, exploiting DVFS to tune the computing nodes CPU frequencies in order to minimize the energy consumption and satisfy application's performance requirements. Our early experimental results illustrate the working and benefits of our framework.

In this paper we tackle the recently proposed problem of hidden streams. In many situations, the data stream that we are interested in, is not directly accessible. Instead, part of the data can be accessed only through applying filters (e.g. keyword filtering). In fact this is the case of the most discussed social stream today, Twitter. The problem in this case is how to retrieve as many relevant documents as possible by applying the most appropriate set of filters to the original stream and, at the same time, respect a number of constrains (e.g. maximum number of filters that can be applied). In this work we introduce a search approach on a dynamic filter space. We utilize heterogeneous filters (not only keywords) making no assumptions about the attributes of the individual filters. We advance current research by considering realistically hard constraints based on real-world scenarios that require tracking of multiple dynamic topics. We demonstrate the effectiveness of our approaches on a set of topics of static and dynamic nature. The development of the approach was motivated by a real application. Our system is deployed in Dublin City's Traffic Management Center and allows the city officers to analyze large sources of heterogeneous data and identify events related to traffic as well as emergencies.

The wide adoption of Location Based Social Networks along with advances in mobile technology, has brought forth as a core service the analysis of large volumes of location-based data for personalized Point of Interest (POIs) recommendations. The majority of the existing recommendation systems take advantage of Collaborative Filtering, but they fail to exploit the contextual information involved with POI checkins (i.e., POI category, location, or the checkin timestamp). In this paper we propose CoTF, a Context-Aware Point of Interest Recommendation system using Tensor Factorization, that aims at enhancing the user experience by providing personalized context aware POI recommendations. Our approach exploits Category-based context related to checkins without the need of any pre-or post-filtering techniques. Our detailed experimental evaluation using real data from the Foursquare location-based social network illustrates that our approach can efficiently produce personalized recommendations to users, while significantly reducing the training time compared to current state-of-the-art methods.

News portals, such as Yahoo News or Google News, collect large amounts of documents from a variety of sources on a daily basis. Only a small portion of these documents can be selected and displayed on the homepage. Thus, there is a strong preference for major, recent events. In this work, we propose a scalable and accurate First Story Detection (FSD) pipeline that identifies fresh news. In comparison to other FSD systems, our method relies on relation extraction methods exploiting entities and their relations. We evaluate our pipeline using two distinct datasets from Yahoo News and Google News. Experimental results demonstrate that our method improves over the state-of-the-art systems on both datasets with constant space and time requirements.

Applying real-time, cost-effective Complex Event processing (CEP) in the cloud has been an important goal in recent years. Distributed Stream Processing Systems (DSPS) have been widely adopted by major computing companies such as Facebook and Twitter for performing scalable event processing in streaming data. However, dynamically balancing the load of the DSPS’ components can be particularly challenging due to the high volume of data, the components’ state management needs, and the low latency processing requirements. Systems should be able to cope with these challenges and adapt to dynamic and unpredictable load changes in real-time. Our approach makes the following contributions: (i) we formulate the load balancing problem in distributed CEP systems as an instance of the job-shop scheduling problem, and (ii) we present a novel framework that dynamically balances the load of CEP engines in real-time and adapts to sudden changes in the volume of streaming data by exploiting two balancing policies. Our detailed experimental evaluation using data from the Twitter social network indicates the benefits of our approach in the system’s throughput. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Recently, the massive prevalence of mobile devices has led to the development of mobile social sensing systems where humans are enlisted to act as social sensors to perform geo-located tasks that require human intelligence or intervention. Social sensing from ubiquitous users can provide significant benefits particularly during crisis management and emergency scenarios. However, an important problem during such emergencies is how to exploit social sensors to accurately determine the location, extent and severity of the event. In this paper we develop a social sensing system that uses humans as social sensors where we apply particle filtering to iteratively determine the spatial areas to be investigated to accurately detect the location and state of the target event. Our experiments illustrate that our approach can accurately identify critical real-world events using feedback from the social sensors.

Recommending nearby Points of Interest (POI) has received growing interest in mobile location-based networks today, where users share content embedded with location information. In this work, we propose a novel caching framework to support personalised proactive caching for mobile location-based social networks. We propose "LOCAI", which uses a probabilistic approach in order to predict the POIs that users will access and retrieve the appropriate data objects that will fulfill user preferences. Our detailed experimental evaluation, using data from the Foursquare location-based social network, illustrates that LOCAI minimizes the user latency to retrieve the data objects they are interested in, is efficient and practical.

With the massive prevalence of smartphones, mobile social sensing systems in which humans acting as social sensors respond to geo-located crowdsourcing tasks, became extremely popular. Such systems can provide significant benefits particularly during crisis management and emergency situations. However, not only querying users can be extremely costly but also human sensors are mobile, subjective and their response delays can highly vary. In this paper we develop a social sensing system that performs sampling on mobile social sensors to achieve accurate and real-time detection of the state of emergency events. Our contributions are two-fold: (i) our approach can capture well emergencies even in large geographical regions, and (ii) our sampling approach considers the individual characteristics of the social sensors to maximize the probability of receiving accurate responses in a timely manner. We provide comprehensive experiments that indicate that our approach accurately identifies critical real-world events, has low overhead and reduces the classification error up to 90% compared to traditional approaches.

This paper contributes to mobile crowdsourcing applications by developing a privacy preserving framework that enables users to contribute content to the community while controlling their privacy exposure. One fundamental challenge in such applications is how to preserve user privacy, as participants may end up revealing a great deal of user-identified, geo-located data, which can easily unfold user trajectories or sensitive locations (e.g., user's home or work location). In this paper we develop PROMPT, a highly efficient privacy preserving framework that runs locally on mobile devices. PROMPT relies on a novel geometric approximation approach to preserve user privacy, by evaluating the privacy exposure of users before sharing their geo-located data. Our detailed experimental evaluation using real-world datasets illustrates that our approach is effective, practical and has low overhead on smartphones.

In recent years we are observing an increased demand for processing large amounts of data. The MapReduce programming model has been utilized by major computing companies in order to perform large-scale data processing. However, the problem of efficiently scheduling MapReduce workloads in cluster environments, like Amazon's EC2, can be challenging due to the observed tradeoff between the need for performance and the corresponding monetary cost. The problem is exacerbated by the fact that cloud providers tend to charge users based on their I/O operations increasing dramatically the spending budget. In this paper we describe our approach for scheduling MapReduce workloads in cluster environments taking into consideration the performance/budget tradeoff. Our approach makes the following contributions: (i) a novel Pareto-based scheduler for identifying near-optimal resource allocations for user's workloads with respect to performance and monetary cost, and (ii) automatic configuration of tasks' buffer sizes to minimize the I/Os impact on the users' budget. Our detailed experimental evaluation using both real and synthetic datasets illustrate that our approach can improve the performance of the workloads as much as 50%, compared to its competitors.

Online Social Networks (OSNs) constitute one of the most important communication channels and are widely utilized as news sources. Information spreads widely and rapidly in OSNs through the word-of-mouth effect. However, it is not uncommon for misinformation to propagate in the network. Misinformation dissemination may lead to undesirable effects, especially in cases where the non-credible information concerns emergency events. Therefore, it is essential to timely limit the propagation of misinformation. Towards this goal, we suggest a novel propagation model, namely the Dynamic Linear Threshold (DLT) model, that effectively captures the way contradictory information, i.e., misinformation and credible information, propagates in the network. The DLT model considers the probability of a user alternating between competing beliefs, assisting in either the propagation of misinformation or credible news. Based on the DLT model, we formulate an optimization problem that aims in identifying the most appropriate subset of users to limit the spread of misinformation by initiating the propagation of credible information. Through extensive experimental evaluation we demonstrate that our approach outperforms its competitors.

Supporting real-time, cost-effective execution of Complex Event processing applications in the cloud has been an important goal for many scientists in recent years. Distributed Stream Processing Systems (DSPS) have been widely adopted by major computing companies as a powerful approach for large-scale Complex Event processing (CEP). However, determining the appropriate degree of parallelism of the DSPS' components can be particularly challenging as the volume of data streams is becoming increasingly large, the rule set is becoming continuously complex, and the system must be able to handle such large data stream volumes in real-time, taking into consideration changes in the burstiness levels and data characteristics. In this paper we describe our solution to building elastic complex event processing systems on top of our distributed CEP system which combines two commonly used frameworks, Storm and Esper, in order to provide both ease of usage and scalability. Our approach makes the following contributions: (i) we provide a mechanism for predicting the load and latency of the Esper engines in upcoming time windows, and (ii) we propose a novel algorithm for automatically adjusting the number of engines to use in the upcoming windows, taking into account the cost and the performance gains of possible changes. Our detailed experimental evaluation with a real traffic monitoring application that analyzes bus traces from the city of Dublin indicates the benefits in the working of our approach. Our proposal outperforms the current state of the art technique in regards to the amount of tuples that it can process by four orders of magnitude.

Complex Event Processing (CEP) systems process large streams of data trying to detect events of interest. Traditional CEP systems, such as Esper, lack the required scalability and processing capability to cope with the constantly increasing amount of data that needs to be processed. Furthermore, user defined rules are static so changes in the monitored environment cannot be easily detected. In this paper we investigate the development of a scalable and dynamic traffic management system. Our work makes several contributions: We propose a novel system that combines Esper with a stream processing framework, Storm, in order to parallelize the processing of larger amounts of data. We propose a novel rules’ assignment algorithm for distributing Esper rules to the available CEP engines, in a way that maximizes the overall system’s throughput. Finally, our system adapts to changes of the environment by processing historical data via Hadoop and dynamically updating the Esper rules based on the generated results. Our work has been evaluated using real data, in several traffic monitoring scenarios for the city of Dublin. Our detailed experimental results indicate the benefits in the working of our approach and the significant increase in the system’s throughput when a large number of Esper rules were examined concurrently.

In recent years we have observed a significant increase in the popularity of location-based social networks for exchanging news and experiences, sharing location information, or publishing real world events. One important challenge in such networks is to understand human crowd mobility behavior based on user social activities and interactions. In this paper we introduce PRESENT, our middleware that utilizes a Mixed Markov Model to extract the behavioral patterns of the users in social groups, to make personalized event recommendations. Our detailed experimental evaluation, using data from the Meet up location-based social network, illustrates that our approach is efficient, practical and achieves an average prediction for the user attendance of over 73%.

Urban traffic gathers increasing interest as cities become bigger, crowded and “smart”. We present a system for het-erogeneous stream processing and crowdsourcing supporting intelligent urban traffic management. Complex events related to traffic congestion (trends) are detected from heterogeneous sources involving fixed sensors mounted on intersections and mobile sensors mounted on public transport vehicles. To deal with data veracity, a crowdsourcing component handles and resolves sensor disagreement. Furthermore, to deal with data sparsity, a traffic modelling component offers information in areas with low sensor coverage. We demonstrate the system with a real-world use-case from Dublin city, Ireland.

With the rapid growth of mobile smartphone users, several commercial mobile companies have exploited crowd sourcing as an effective approach to collect and analyze data, to improve their services. In a crowd sourcing system, "human workers" are enlisted to perform small tasks, that are difficult to be automated, in return for some monetary compensation. This paper presents our crowd sourcing system that seeks to address the challenge of determining the most efficient allocation of tasks to the human crowd. The goal of our algorithm is to efficiently determine the most appropriate set of workers to assign to each incoming task, so that the real-time demands are met and high quality results are returned. We empirically evaluate our approach and show that our system effectively meets the requested demands, has low overhead and can improve the number of tasks processed under the defined constraints over 71% compared to traditional approaches.

Location-based social networks have evolved into powerful tools in recent years. The ability to embed location information in Social Networks such as Facebook, Foursquare and Twitter creates exciting opportunities for users to disseminate and exchange geolocation information in a variety of domains. The problem of exploiting the social ties between the users for maximizing information reach has become a topic of great interest, and many challenges have to be met. In this work we study the problem of efficient information dissemination in location-based social networks under time constraints. The objective is to identify a subset of individuals to propagate the information and make intelligent route selection that can result in maximizing the reach within a time window. Our detailed experimental results illustrate the feasibility and performance of our approach.

research-article Free Access Share on Event Recognition Challenges and Techniques: Guest Editors' Introduction Authors: Alexander Artikis NCSR "Demokritos", Greece NCSR "Demokritos", GreeceView Profile , Avigdor Gal Technion -- Israel Institute of Technology, Israel Technion -- Israel Institute of Technology, IsraelView Profile , Vana Kalogeraki Athens University of Ecenomics and Business, Greece Athens University of Ecenomics and Business, GreeceView Profile , Matthias Weidlich Imperial College London, UK Imperial College London, UKView Profile Authors Info & Claims ACM Transactions on Internet TechnologyVolume 14Issue 1July 2014 Article No.: 1pp 1–9https://doi.org/10.1145/2632220Published:07 August 2014Publication History 8citation511DownloadsMetricsTotal Citations8Total Downloads511Last 12 Months31Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Intelligent transport management involves the use of voluminous amounts of uncertain sensor data to identify and effectively manage issues of congestion and quality of service. In particular, urban traffic has been in the eye of the storm for many years now and gathers increasing interest as cities become bigger, crowded, and “smart”. In this work we tackle the issue of uncertainty in transportation systems stream reporting. The variety of existing data sources opens new opportunities for testing the validity of sensor reports and self-adapting the recognition of complex events as a result. We report on the use of a logic-based event reasoning tool to identify regions of uncertainty within a stream and demonstrate our method with a real-world use-case from the city of Dublin. Our empirical analysis shows the feasibility of the approach when dealing with voluminous and highly uncertain streams.

In the recent years we are experiencing the rapid growth of crowdsourcing systems, in which “human workers” are enlisted to perform tasks more effectively than computers, and get compensated for the work they provide. The common belief is that the wisdom of the “human crowd” can greatly complement many computer tasks which are assigned to machines. A significant challenge facing these systems is determining the most efficient allocation of tasks to workers to achieve successful completion of the tasks under real-time constraints. This paper presents REACT, a crowdsourcing system that seeks to address this challenge and proposes algorithms that aim to stimulate user participation and handle dynamic task assignment and execution in the crowdsourcing system. The goal is to determine the most appropriate workers to assign incoming tasks, in such a way so that the realtime demands are met and high quality results are returned. We empirically evaluate our approach and show that REACT meets the requested real-time demands, achieves good accuracy, is efficient, and improves the amount of successful tasks that meet their deadlines up to 61% compared to traditional approaches like AMT.

In the recent years we have witnessed a proliferation of distributed stream processing systems that need to operate efficiently, even when data bursts occur. Examples include road traffic networks, processing of financial feeds, network monitoring and real-time sensor data analysis systems. An important challenge in managing these systems is effective resource management and meeting the QoS demands of the stream processing applications under different workload conditions, even under bursts. In this paper we present our approach that aims to predict the execution times of the distributed stream processing applications by taking into account the effects of the bursts and what is the typical workload of the stream processing system. Our approach builds application data rate patterns at run-time and predicts the effect of the burst on the performance of the applications, to identify whether there is a need to react on the onset of a burst. Our detailed experimental results over our Synergy middleware illustrate that our approach is practical, depicts good performance and has low resource overhead.

The proliferation of mobile networking and the increasing capabilities of smartphone devices in the recent years have resulted in transforming mobile smartphone devices into ubiquitous sensing platforms. In this new class of “Community-based Participatory Sensing” systems, users actively participate in the data collection and sharing for the benefit of the community, in a wide range of application areas from entertainment, to transportation, to environmental monitoring. These approaches, however, generate large amounts of transient data streams, leading to real-time computational challenges. In this paper we propose sampling algorithms on streams of mobile data generated by ubiquitous sensing devices that need to be processed under time constraints. In our approach users participate in the system by sensing and sharing streams of data. The system then uses a sampling mechanism to select a subset of data streams that preserves the characteristics of the stream data and provides the highest “information gain” to the system, given the real-time, budget and resource constraints. Detailed experimental results illustrate that our approach is practical, efficient and depicts good performance.

Over the recent years, the proliferation of mobile networking and the increasing capabilities of smartphone devices have led to the development of “Participatory Sensing” applications, where users actively participate in data collection and sharing in a wide range of application domains from entertainment, to transportation, to environmental monitoring. One important challenge in these settings is privacy preservation for participatory sensing data, such as user trajectories. This paper develops a participatory sensing system for Android smartphones and proposes an efficient approach for privacy preservation which enables users to disclose their trajectory information without compromising their privacy. Existing approaches for privacy-aware data sharing operate under the assumption that user data is maintained in a centralized database. In our work we assume that user data is generated and stored locally on the individual smartphone devices. Our technique is distributed and low cost. We present detailed experimental results to illustrate that our approach is practical, efficient and with low overhead.

In this demonstration, we are presenting SmartMonitor, a distributed Structural Health Monitoring (SHM) system consisting of smart devices. Over the last few years, the vast majority of smart devices is equipped with accelerometers that can be utilized towards building SHM systems with hundreds of nodes. We describe a scalable, fault-tolerant communication protocol, that performs best-effort time synchronization of the nodes and is used to implement a decentralized version of the popular peak-picking SHM method. The implemented interactive system can be easily installed in any accelerometer-equipped Android device and the user has a number of options for configuring the system or analyzing the collected data and computed outcomes.

Overlay network architectures that use orthogonal channels have been known to provide effective additional resources to underlying networks in high demand. Overlays are composed of relay nodes provided with rich computational resources and multiple wireless interfaces that make them capable of establishing several non-interfering networks. These networks can be used to move traffic around in a non-interfering manner. It is possible to deploy such overlays in sensor networks where sensors suffer from the funnel effect caused by excess traffic flows, to help mitigate this effect. In this paper we address the geographical placement of relay nodes in the region to mitigate the funnel effect in sensor networks. We provide an O (mlog (h) ) algorithm of congested region size m and computed Convex Hull size h that finds the placement of the minimum number of relay nodes to cover the entire congested region. In a greedy fashion, we place a relay node given the following placement conditions: the closest position such that it covers the largest amount of peers up to an extent parameter bounded by its transmission range, and that is closest to the sink. Our simulated results show that using a minimum number of relays, we could save up to 43% of nodes compared to a simple placement strategy, the underlying network increases its delivery ratio and throughput, improves its jitter, and opens the possibility of load balancing and fairness advantages.

The recent years have seen a proliferation of community sensing or participatory sensing paradigms, where individuals rely on the use of smart and powerful mobile devices to collect, store and analyze data from everyday life. Due to this massive collection of the data, a key challenge to all such developments, is to provide a simple but efficient way to facilitate the programming of distributed applications on the embedded devices. We will demonstrate a novel system that provides a principled approach to developing distributed data clustering applications on networks of smartphones and other mobile devices. The system comprises three components: (a) a distributed framework, implemented on mobile phones that eases the programmability and deployment of applications on the devices using simple programming primitives, (b) a data gathering component that tracks the movement of wireless device users and collects sensor data (i.e., GPS and accelerometer sensor data), and (c) a distributed data clustering algorithm that allows users to combine their individual data, that is distributed and energy efficient. Using a road traffic monitoring application we demonstrate how MISCO can efficiently identify anomalies in the road surface conditions and illustrate that our system is practical and has low energy and resource overhead.

In the recent years we have witnessed a proliferation of distributed stream processing systems that need to operate under bursty workloads. Examples include road traffic control, processing of financial feeds, network monitoring and real-time sensor data analysis systems. Meeting the QoS requirements of the stream processing systems under burstiness is a challenging process. In this paper we present our approach for adaptive rate allocation within the distributed stream processing system to meet the end-to-end execution time and rate demands of the applications. Our algorithm determines the rates of the application components at runtime, with respect to the QoS constraints, to compensate for delays experienced by the components or to react to sudden bursts of load. Our technique is distributed and low-cost. Our detailed experimental results over our Synergy middleware illustrate that our approach is practical, depicts good performance and has low resource overhead.

Replication is commonly used to address the scalability and availability requirements of collaborative web applications in domains such as computer supported cooperative work, social networking, e-commerce and e-banking. While providing substantial benefits, replication also introduces the ov

The imminent growth of user-centric, pervasive sensing environments promotes sink mobility in an increasing number of event-based, sensor network applications including rescue missions, intrusion detection, and smart buildings. In these settings, one of the most critical challenges toward supporting quality of service, is effective distributed congestion avoidance. Congestion control techniques have been proposed in sensor networks mostly in the context of a static sink. In our work, we study the problem of traffic management in the context of sensor networks with a mobile sink. Under sink mobility, various new challenges arise that need to be effectively addressed. Adaptation to sink mobility requires agile as well as effective load estimation techniques. In addition, unlike static networks, path reliability often fluctuates due to path reconfigurations. Thus, injecting traffic during transient periods of poor path quality might wastefully detain network resources. In this work, we first study the effect of sink mobility on traffic load in sensor networks. We then propose adaptive routing as well as load estimation techniques that effectively adapt to sink relocations. A novel aspect of our approach is that it jointly considers the network load as well as path quality variations to facilitate intelligent, mobility-adaptive rate regulation at the sources. We provide a thorough study of the trade-offs induced due to persistent path quality variations and conduct extensive real MICA2-based testbed experiments to study the performance of the sensor network under sink mobility.

Distributed object search is the primary function of peer-to-peer (P2P) file sharing system to locate and transfer the file. The predominant search schemes in unstructured P2P systems have their problems: flooding creates excessive traffic overhead and random walk prolongs search delay. Moreover, both use uniform time-to-live (TTL) control for all users, which makes them vulnerable to selfish user attacks, and results in the "free-riding" and "tragedy of the commons" problems. In this paper, we propose a budget-based self-optimized incentive search (BuSIS) protocol for unstructured P2P file sharing systems, which is robust to and restricts selfish user behaviors. Furthermore, our protocol lowers the search overhead while keeping high hit rate. BuSIS provides differentiated search service for selfish users and ties a user's contribution to its service level. We present the analytical models on expected search performance, associated search cost and the user satisfaction level. Extensive emulations have been conducted at large scale network scenarios to compare performance of BuSIS with flooding and random walk searches with and without selfish user behaviors. The experimental results show that BuSIS always has the lowest search overhead without sacrificing the hit rate. When serving selfish users, flooding and random walk performance degrade dramatically, while BuSIS gracefully keeps the hit rate only with 20% overhead of flooding and 25% of random walk.

Stream processing systems have become important, as applications like media broadcasting, sensor network monitoring and on-line data analysis increasingly rely on real-time stream processing. Such systems are often challenged by the bursty nature of the applications. In this paper, we present BARRE (Burst Accommodation through Rate REconfiguration), a system to address the problem of bursty data streams in distributed stream processing systems. Upon the emergence of a burst, BARRE dynamically reserves resources dispersed across the nodes of a distributed stream processing system, based on the requirements of each application as well as the resources available on the nodes. Our experimental results over our Synergy distributed stream processing system demonstrate the efficiency of our approach.

Many emerging online data analysis applications require applying continuous query operations such as correlation, aggregation, and filtering to data streams in real time. Distributed stream processing systems allow in-network stream processing to achieve better scalability and quality-of-service (QoS) provision. In this paper, we present Synergy, a novel distributed stream processing middleware that provides automatic sharing-aware component composition capability. Synergy enables efficient reuse of both result streams and processing components, while composing distributed stream processing applications with QoS demands. It provides a set of fully distributed algorithms to discover and evaluate the reusability of available result streams and processing components when instantiating new stream applications. Specifically, Synergy performs QoS impact projection to examine whether the shared processing can cause QoS violations on currently running applications. The QoS impact projection algorithm can handle different types of streams including both regular traffic and bursty traffic. If no existing processing components can be reused, Synergy dynamically deploys new components at strategic locations to satisfy new application requests. We have implemented a prototype of the Synergy middleware and evaluated its performance on both PlanetLab and simulation testbeds. The experimental results show that Synergy can achieve much better resource utilization and QoS provisioning than previously proposed schemes, by judiciously sharing streams and components during application composition.

Many emerging distributed applications require the real-time processing of large amounts of data that are being updated continuously. Distributed stream processing systems offer a scalable and efficient means of in-network processing of such data streams. However, the large scale and the distributed nature of such systems, as well as the fluctuation of their load render it difficult to ensure that distributed stream processing applications meet their Quality of Service demands. We describe a decentralized framework for proactively predicting and alleviating hot-spots in distributed stream processing applications in real-time. We base our hot-spot prediction techniques on statistical forecasting methods, while for hot-spot alleviation we employ a non-disruptive component migration protocol. The experimental evaluation of our techniques, implemented in our Synergy distributed stream processing middleware over PlanetLab, using a real stream processing application operating on real streaming data, demonstrates high prediction accuracy and substantial performance benefits.

In this paper we describe our approach for developing a QoS-aware, dependable execution environment for large-scale distributed stream processing applications. Distributed stream processing applications have strong timeliness and security demands. In particular, we address the following challenges: (1) propose a real-time dependable execution model by extending the component-based execution model with real-time and dependability properties, and (2) develop QoS-aware application composition and adaptation techniques that employ resource management strategies and security policies when discovering and selecting application components. Our approach enables us to develop a distributed stream processing environment that is predictable, secure, flexible and adaptable.

In this paper we propose a suite of index structures and algorithms which permit us to efficiently support querying of historical data in flash-equipped sensor devices. Our techniques are designed to consider the unique read, write and wear constraints of the flash memories; this combined with very limited data memory on sensor devices prohibits the direct application of most existing indexing methods. We have implemented our methods using nesC and have run extensive experiments in TOSSIM, the simulation environment of TinyOS. Our experimental evaluation using trace-driven real world data sets demonstrates the efficiency of our indexing algorithms.

In wireless sensor networks, multiple flows from data collecting sensors to an aggregating sink could traverse paths that are largely interference coupled. These interference effects manifest themselves as congestion, and cause the flows to experience high packet loss and arbitrary packet delays. This is particularly problematic in event-based sensor networks (such as those in disaster recovery missions) where some flows are of greater importance than others and require a higher fidelity in terms of packet delivery and timeliness. In this paper we present COMUT (COngestion control for MUlti-class Traffic), a distributed cluster-based mechanism for supporting multiple classes of traffic in sensor networks. COMUT is based on the self-organization of the network into clusters , each of which autonomously and proactively monitors congestion within its localized scope. The clusters then exchange appropriate information to facilitate system wide rate control where, each data source, depending on the relative importance of its data flow and the experienced congestion en route the sink, is coerced into controlling its rate. Our simulation results demonstrate that (i) our techniques are highly effective in dealing with multiple, interfering flows and in achieving high delivery ratios and low delays compared to traditional approaches, (ii) operate successfully over multiple underlying routing protocols, (iii) provide higher throughput to higher importance flows, (iv) are responsive to failures and, finally, (v) achieve substantial energy savings due to the considerable reduction in packet drops via the effective regulation of the network load.

Wireless sensor networks are small, inexpensive and flexible computational platforms, that have found popular applications in various areas including environmental monitoring, health care and disaster recovery. One fundamental question is how to place the nodes in the network so that complete coverage of the monitored area is achieved. In this paper, we use techniques from discrepancy theory that accurately represent the uncovered area using just a few discrete points, to make sure that every point in the network is covered by at least k sensors, where k is calculated based on user reliability requirements. Our technique is fully distributed, deploying a low number of sensors, and minimizes the communication costs. Our experiments demonstrate that our technique is highly effective in achieving a reliable restoration of a given sensor network area.

In today's world, stream processing systems have become important, as applications like media broadcasting, sensor network monitoring and on-line data analysis increasingly rely on real-time stream processing. In this paper, we propose a distributed stream processing system that composes stream processing applications dynamically, while meeting their rate demands. Our system consists of the following components: (1) a distributed component discovery algorithm that discovers components available at nodes on demand, (2) resource monitoring techniques to maintain current resource availability information, (3) a scheduling algorithm that schedules application execution, and (4) a minimum cost composition algorithm that composes applications dynamically based on component and resource availability and scheduling demands. Our detailed experimental results, over the PlanetLab testbed, demonstrate the performance and efficiency of our approach.

The imminent growth of user-centric, pervasive sensing environments promotes sink mobility in an increasing number of event-based, sensor network applications including rescue missions, intrusion detection and smart buildings. In these settings, one of the most critical challenges toward supporting quality of service, is effective distributed congestion avoidance. Congestion control techniques have been proposed in sensor networks mostly in the context of a static sink. In our work, we study the problem of congestion avoidance in the context of sensor networks with a mobile sink. Under sink mobility, various new challenges arise that need to be effectively addressed. Adaptation to sink mobility requires agile as well as effective load estimation techniques. In addition, unlike static networks, path reliability often fluctuates due to path reconfigurations. Thus, injecting traffic during transient periods of poor path quality might wastefully detain network resources. Our approach jointly considers the network load and path quality variations to facilitate intelligent, mobility-adaptive rate regulation at the sources. We implemented our techniques over a Mica2 testbed and through extensive experimental results, we demonstrate the working and benefits of our approach.

Peer-to-peer (P2P) databases are becoming prevalent on the Internet for distribution and sharing of documents, applications, and other digital media. The problem of answering large-scale ad hoc analysis queries, for example, aggregation queries, on these databases poses unique challenges. Exact solutions can be time consuming and difficult to implement, given the distributed and dynamic nature of P2P databases. In this paper, we present novel sampling-based techniques for approximate answering of ad hoc aggregation queries in such databases. Computing a high-quality random sample of the database efficiently in the P2P environment is complicated due to several factors: the data is distributed (usually in uneven quantities) across many peers, within each peer, the data is often highly correlated, and, moreover, even collecting a random sample of the peers is difficult to accomplish. To counter these problems, we have developed an adaptive two-phase sampling approach based on random walks of the P2P graph, as well as block-level sampling techniques. We present extensive experimental evaluations to demonstrate the feasibility of our proposed solution.

The emerging peer-to-peer (p2p) model has become a very powerful and attractive paradigm for developing Internet-scale systems for sharing resources, including files and documents. The distributed nature of these systems, where nodes are typically located across different networks and domains, inherently hinders the efficient retrieval of information. In this paper, we consider the effects of topologically aware overlay construction techniques on efficient p2p keyword search algorithms. We present the peer fusion (pFusion) architecture that aims to efficiently integrate heterogeneous information that is geographically scattered on peers of different networks. Our approach builds on work in unstructured p2p systems and uses only local knowledge. Our empirical results, using the pFusion middleware architecture and data sets from Akamai's Internet mapping infrastructure (AKAMAI), the active measurement project (NLANR), and the text retrieval conference (TREC) show that the architecture we propose is both efficient and practical

In the emerging area of wireless sensor networks, one of the most typical challenges is to retrieve historical information from the sensor nodes. Due to the resource limitation of sensor nodes (processing, memory, bandwidth, and energy), the collected information of sensor nodes has to be compressed quickly and precisely for transmission. In this paper, we propose a new technique -- the ALVQ (Adoptive Learning Vector Quantization) algorithm to compress this historical information. The ALVQ algorithm constructs a codebook to capture the prominent features of the data and with these features all the other data can be piece-wise encoded for compression. In addition, with two-level regression of the codebook's update, ALVQ algorithm saves the data transfer bandwidth and improves the compression precision further. Finally, we consider the problem of transmitting data in a sensor network while maximizing the precision. We show how we apply our algorithm so that a set of sensors can dynamically share a wireless communication channel.

Peer-to-peer databases are becoming prevalent on the Internet for distribution and sharing of documents, applications, and other digital media. The problem of answering large scale, ad-hoc analysis queries ― e.g., aggregation queries ― on these databases poses unique challenges. Exact solutions can be time consuming and difficult to implement given the distributed and dynamic nature of peer-to-peer databases. In this paper we present novel sampling-based techniques for approximate answering of ad-hoc aggregation queries in such databases. Computing a high-quality random sample of the database efficiently in the P2P environment is complicated due to several factors ― the data is distributed (usually in uneven quantities) across many peers, within each peer the data is often highly correlated, and moreover, even collecting a random sample of the peers is difficult to accomplish. To counter these problems, we have developed an adaptive two-phase sampling approach, based on random walks of the P2P graph as well as block-level sampling techniques. We present extensive experimental evaluations to demonstrate the feasibility of our proposed solutio

Service overlays that support distributed stream processing applications are increasingly being deployed in wide-area environments. The inherent heterogeneous, dynamic and large-scale nature of these systems makes it difficult to meet the quality of service (QoS) requirements of the distributed stream processing applications. In this paper we address the load balancing problem for distributed stream processing applications and present a decentralized and adaptive algorithm that allows the composition of distributed stream processing applications on the fly across a large-scale system, while satisfying their QoS demands. The algorithm fairly distributes the load on the resources and adapts dynamically to changes in the resource utilization or the QoS requirements of the applications. Our experimental results demonstrate the scalability, efficiency and performance of our approach

Sensor networks are being deployed for tracking events of interest in many environmental or monitoring applications. Because of their distributed nature of operation, a challenging issue is how to accurately identify the aggregate state of the phenomenon that is being observed. This work presents an online mechanism for efficiently determining the overall network status, employing distributed operations that minimize the communication costs. Experiments on real data, suggest that the proposed metholology can be a viable solution for real world systems.

In this work we propose a traffic management mechanism to support real-time flows in highly unpredictable sensor network environments. The mechanism is based on a joint traffic regulation and end-to-end scheduling approach; a traffic regulation component adjusts the incoming packet rate to implicitly control the channel load and intelligently rejects packets that are more likely to miss their deadline while a laxity-based scheduling component projects the packets' per-hop delay and compensates for network end-to-end delays. Thus, high success ratios without severely degrading the fidelity are achieved. Our mechanism attempts to maintain accuracy in a resource-efficient manner even under extremely unstable network conditions where delays are difficult to model and compute. Furthermore, the adoption of a component-based approach allows for substantial independence from both the MAC and routing layers. We thoroughly evaluate our mechanism and demonstrate its accuracy and performance merits

In many applications we can deploy large number of sensors spanning wide geographical areas, to monitor environmental phenomena. The analysis of the data collected by such sensor network can help us to understand the field dynamics, and optimize the deployment of other solutions. We define a group of sensors having similar underlying distribution over a period of time as a homogeneous region. In this paper we propose distributed algorithms to detect such regions, approximate their boundary with a piece-wise linear curve and track the boundary in real-time. Experimental results show the accuracy and efficiency of our detection and tracking algorithms

Flash memory is the most prevalent storage medium found on modern wireless sensor devices (WSDs) . In this article we present two external memory index structures for the efficient retrieval of records stored on the local flash memory of a WSD. Our index structures, MicroHash and MicroGF (micro grid files) , exploit the asymmetric read/write and wear characteristics of flash memory in order to offer high-performance indexing and searching capabilities in the presence of a low-energy budget, which is typical for the devices under discussion. Both structures organize data and index pages on the flash media using a sorted by timestamp file organization. A key idea behind these index structures is that expensive random access deletions are completely eliminated. MicroHash enables equality searches by value in constant time and equality searches by timestamp in logarithmic time at a small cost of storing index pages on the flash media. Similarly, MicroGF enables spatial equality and proximity searches in constant time. We have implemented these index structures in nesC, the programming language of the TinyOS operating system. Our trace-driven experimentation with several real datasets reveals that our index structures offer excellent search performance at a small cost of constructing and maintaining the index.

Software DSMs (SDSMs) are an appealing alternative to message passing, since they facilitate the programmability of clusters. However the ease of programming comes at the expense of performance. Although accesses of data that reside to the memory of remote nodes are transparent to the programmer, they suffer from significantly higher latencies compared to local accesses. As a consequence, it is desirable to move data as close as possible to the nodes that need them most. In this paper we introduce a protocol for dynamically migrating memory pages in home-based SDSM systems. In these systems each page has a designated home node; yet our protocol allows a node that heavily modifies a page to become its new home. The new protocol targets multiple-writer DSMs, i.e. DSMs that allow multiple nodes to concurrently modify the same page. The process is dynamic and transparent to the applications programmer. Moreover, it does not assume a specific consistency protocol. Experimental results show that our page migration protocol reduces remote page modifications, decreases the average memory access latency, as well as the overhead for the preservation of memory consistency. The benefit for the end-user is a significant improvement in application performance

Summary form only given. In the emerging area of wireless sensor networks, a typical challenge is to retrieve historical information from the sensor nodes. We propose a new technique, called adaptive learning vector quantization (ALVQ), to compress this historical information. Our technique is based on the following two observations: (1) in sensor networks, the historical information exhibits similar patterns over time; and (2) different measurements are intrinsically correlated. Our algorithm works as follows: first, the codebook is obtained through a LVQ (learning vector quantization), which adjusts the codebook to be nearer to the optimal codebook. Second, ALVQ compresses the codebook update data pieces and transfers the compressed information to the base station. Using 2-level piece-wise regression, ALVQ can compress the updates with high precision while saving more bandwidth for data transmission in order to increase the quality of the approximation. In our experiments we used weather data to compare the performance of the ALVQ algorithm with the recently proposed SBR (self based regression) technique. Our experimental results demonstrate that the LVQ learning process significantly improves the quality of the codebook, thus increasing the regression precision. In addition the use of two-level regression for transmitting the codebook updates further minimizes the required bandwidth. Overall the ALVQ technique can achieve the same precision with SBR while using 75% of the bandwidth.

Over the past few years, peer-to-peer (P2P) systems have become very popular for constructing overlay networks of many nodes (peers) that allow users geographically distributed to share data and resources. One non-trivial question is how to distribute the data in a fair and fully decentralized manner among the peers. This is important because it can improve resource usage, minimize network latencies and reduce the volume of unnecessary traffic incurred in large-scale P2P systems. In this paper we present a technique for fair resource allocation in unstructured peer-to-peer systems. Our technique uses the fairness index of a distribution as a measure of fairness and shows how to optimize the fairness of the distribution using only local decisions. Load balancing is achieved by replicating documents across multiple nodes in the system. Our experimental results demonstrate that our technique is scalable, has low overhead and achieves good load balance even under skewed demand.

In this work we propose and evaluate a framework for efficient and real-time dissemination of dynamic data in distributed simulation virtual environments in a scalable fashion. A peer-to-peer overlay is used to create self-organizing groups of participants. Filters that combine application-level knowledge are utilized to control the message propagations and minimize the end-to-end delays. Our approach enables nodes to trade-off processing overhead for consistency precision. Our simulation results illustrate that our techniques meet the consistency requirements of the participants, while minimizing the data transmissions and the message delays.

The pervasiveness of computers in our current society (transportation, e-commerce, home appliances, medical monitoring, process control) expands our freedom for flexible ad-hoc communication and dynamic collaboration between individuals through a wide variety of devices. With the pervasive deployment of computers, the Peer-to-Peer (P2P) model is increasingly receiving attention for direct and symmetric interaction and to perform critical functions in a decentralized manner. Some of the benefits of a P2P environment include its ability for self-organization, scalability by avoiding dependency on centralized servers, resource aggregation and adaptation to different loads, resiliency to node failures and lower cost of ownership and cost sharing. The goal of this panel is to explore the synergy of these two technologies, identify the challenges along with their shortcomings and explore promising approaches.

In this paper we propose adaptive content-driven routing and data dissemination algorithms for intelligently routing search queries in a peer-to-peer network that supports mobile users. In our mechanism nodes build content synopses of their data and adaptively disseminate them to the most appropriate nodes. Based on the content synopses, a routing mechanism is being built to forward the queries to those nodes that have a high probability of providing the desired results. Our simulation results show that our approach is highly scalable and significantly improves resources usage by saving both bandwidth and processing power.

Wireless sensor network applications typically integrate, within the same network, a variety of sensing devices including those for imaging, sound and temperature. In these settings, multiple flows of packets with different requirements in terms of transmission rates, bandwidth and jitter demands may be initiated towards the sink. Uncontrolled introduction of traffic from sources can cause network overload in areas of the network where the paths of the different flows interfere with each other. Such interference effects may result in congestion which leads to high packet loss and excessive delays. In this paper, we present CoBRA, a framework which incorporates distributed, cluster-based mechanisms to address the problem of congestion by enforcing rate control, for supporting multiple classes of traffic in sensor networks. Towards this goal, CoBRA periodically estimates the collective traffic load and, based on the current conditions, allocates and adjusts rates to sources on per-cluster bases. While doing so, CoBRA takes into consideration interference effects and rate requirements of concurrent flows. We have applied two different rate allocation policies using our framework and, through extensive simulation results we demonstrate its feasibility, effectiveness and performance advantages over traditional approaches

Abstract—Low power, high performance sensor designs are of particular importance nowadays considering the plethora of emerging applications in a wide range of fields. Applications such as audio capture, FFT (Fast Fourier Transform), image sensing, motion detection, feature extraction and cepstrum calculations generate raw data in much larger quantity than more mundane applications as temperature and humidity sensing. In-situ processing of data is an effective way to reduce the amount of information needed to be transmitted over the wireless links. The Co-S platform which we develop addresses this very crucial aspect of sensor network design. The Co-S integrated with a System on Chip (SoC) based host platform and a gigabyte scale energy efficient data storage system, simultaneously satisfies the constraints of low power consumption and a small form factor. As opposed to the Sense-and-Send approach which simply entails transmission of raw sensory data from the nodes, the proposed Sense-and-Store paradigm, builds upon the availability of the low power flash memories for storage of sensed data along with key query results (max, min, average, extracted harmonics) for transmission through the network. This approach not only reduces energy consumption (typically two orders of magnitude), of the sensing node in question, but also intuitively reduces network traffic load vis-à-vis complete deployment scenario. Index Terms–Coprocessors, Performance, Flash Storage I.

In this paper, we have presented a new data compression technique, designed for historical information compression in sensor networks. Our method employs the LVQ learning process to construct the codebook and the codebook's updates are compressed to save bandwidth for sensor data transmission. In addition, we have addressed the dynamic bandwidth allocation problem in sensor networks. Our DBA algorithm can dynamically adjust the communication bandwidth of different sensors in order to balance data compression qualities at different sensors.

Dynamic page migration, when employed in distributed shared memory (DSM) systems offers several advantages: (i) reduces the latency of memory accesses, (ii) improves resource utilization by considering the computational and communicational needs of the applications and adapting to the changing resource availability, and (iii) achieves the above with lower overhead than traditional approaches that rely on thread migration. We propose a simple and efficient page migration mechanism that dynamically allocates shared memory pages to home nodes. Each page has a designated home node and nodes that heavily modify the pages can become their new homes. In our protocol, to avoid redundant page transfers, we perform migration only when the number of modifications of a page becomes larger than a threshold. The migration information is piggybacked on the existing synchronization messages to minimize the communication overhead. The migration decision is taken locally, at the home of each page. We have implemented our mechanism in the JIAJIA software DSM. Performance evaluation using real application benchmarks shows that our mechanism significantly reduces remote page modifications, improves memory access latencies, and achieves better performance than its competitors. We observe that the cost of executing the algorithm and of migrating the pages is amortized by the benefits gained.

In this paper, we propose a technique for scheduling soft real-time multimedia applications in overlay networks. Our scheduling technique consists of a novel distributed and dynamic resource utilization based urgency scheduling algorithm, which exploits the urgency of the tasks and uses monitoring and feedback mechanisms to determine an efficient schedule for the tasks in the system. The algorithm is entirely distributed, uses only local knowledge and scales well with the size of the system. Extensive empirical results validate the performance of our mechanism as a function of the number of tasks, the frequency of feedback propagation and the load on the peers.

Peer-to-peer networks have gained much attention due to their attractive features of self-organization, scalability and decentralized control. The key challenge in these networks is how to efficiently locate and retrieve the correct data. In this paper, we propose propagation and routing algorithms for a fully decentralized, self-organizing network. Our goal is to maximize the probability of finding the data, minimize peer access latencies and balance the workload among many peers. Central to our approach is the Kundali data structure that represents the set of data maintained by the peers and drives the smart routing of the search requests (queries). We have implemented our algorithms in the context of a fully decentralized Internet caching service in our internal network. Our mechanism is inexpensive, highly scalable, and resilient to node failures and with low administration cost. Experimental results validate or algorithms and show that they have good performance results.

One important problem in peer-to-peer (P2P) networks is searching and retrieving the correct information. However, existing searching mechanisms in pure peer-to-peer networks are inefficient due to the decentralized nature of such networks. We propose two mechanisms for information retrieval in pure peer-to-peer networks. The first, the modified Breadth-First Search (BFS) mechanism, is an extension of the current Gnuttela protocol, allows searching with keywords, and is designed to minimize the number of messages that are needed to search the network. The second, the Intelligent Search mechanism, uses the past behavior of the P2P network to further improve the scalability of the search procedure. In this algorithm, each peer autonomously decides which of its peers are most likely to answer a given query. The algorithm is entirely distributed, and therefore scales well with the size of the network. We implemented our mechanisms as middleware platforms. To show the advantages of our mechanisms we present experimental results using the middleware implementation.

Complex distributed object systems require dynamic migration algorithms that allocate and reallocate objects to respond to changes in the load or in the availability of the resources. We present the Cooling and Hot-Spot migration algorithms that reallocate objects when the load on a processor is high or when the latency of a task is high. The algorithms have been implemented as a feedback loop in the Eternal Resource Management System where information obtained from monitoring the behavior of the objects and the usage of the processors' resources is used to dynamically balance the load on the processors and improve the latency of the tasks. The cost of moving an object is justified by amortization over many method invocations, and constrains the rate at which objects are moved. The experimental results show that our algorithms guarantee steady flow of operation for the tasks and gracefully migrate objects from the processors when processor overloads and high task latencies are detected.

Distributed real-time applications require flexible and dynamic scheduling mechanisms to provide timeliness guarantees to application objects. In this paper we present a new scheduling algorithm that exploits the task laxities and the object importance to make effective scheduling decisions. The algorithm uses current timing and resource measurements to determine the feasibility of the tasks and to distribute the objects to the processors. A task's timing parameter (laxity value) is carried, from one processor to another, with the object invocations, yielding a system-wide scheduling strategy that requires only local computations. The algorithm aims to ensure that a low importance object does nor delay the execution of a high importance task.

Distributed method invocations require dynamic scheduling algorithms and efficient resource projections to provide timeliness guarantees to application objects. In this paper, we present a dynamic scheduling algorithm that examines the computation times, real times and resource requirements of the application tasks to determine a feasible schedule for the method invocations. The schedule is driven by the laxities of the tasks and the importance that the tasks have to the system. Tasks span processor boundaries, and request messages carry scheduling parameters (laxity values) from one processor to another, yielding a system-wide scheduling algorithm that requires only local computations. Experimental results validate our scheduling algorithm, and show that it has minimal overhead.

The Eternal system supports networked enterprise applications that must operate continuously 24 hours per day, 7 days per week. Based on the CORBA standard, Eternal provides object replication not only for fault tolerance but also for live software upgrades, as well as resource management facilities. Through the use of interceptors, Eternal renders the object replication transparent to the application, as well as to the ORB and to the operating system. Thus, Eternal works with commercial off-the-shelf CORBA ORBs and standard unmodified operating systems. Eternal handles the difficult issues of object replication, fault tolerance, live upgrades and resource management, thereby allowing the application programmers to focus on the applications.

Complex soft real time distributed object systems require object profiling, scheduling and migration algorithms to respond to transient changes in the load or in the availability of the resources. We have developed a resource management system for a soft real time distributed object system that is based on a three level feedback loop which employs a profiling algorithm that monitors the usage of the resources, a least laxity scheduling algorithm that schedules the tasks, and hot spot and cooling algorithms that allocate and migrate objects to balance the load on the resources. The resource management system consists of a single (but possibly replicated and distributed) resource manager, and profilers and schedulers located on each of the processors in the distributed system.