skip to main content

Attention:

The NSF Public Access Repository (NSF-PAR) system and access will be unavailable from 5:00 PM ET until 11:00 PM ET on Friday, June 21 due to maintenance. We apologize for the inconvenience.


Title: Many-to-many matching based task allocation for dispersed computing
Dispersed computing is a new resource-centric computing paradigm, which makes use of idle resources in the network to complete the tasks. Effectively allocating tasks between task nodes and networked computation points (NCPs) is a critical factor for maximizing the performance of dispersed computing. Due to the heterogeneity of nodes and the priority requirements of tasks, it brings great challenges to the task allocation in dispersed computing. In this paper, we propose a task allocation model based on incomplete preference list. The requirements and permissions of task nodes and NCPs are quantitatively measured through the preference list. In the model, the task completion rate, response time, and communication distance are taken as three optimizing parameters. To solve this NP-hard optimization problem, we develop a new many-to-many matching algorithm based on incomplete preference list. The unilateral optimal and stable solution of the model are obtained. Taking into account the needs for location privacy-preserving, we use the planar Laplace mechanism to produce obfuscated locations instead of real locations. The mechanism satisfies ε-differential privacy. Finally, the efficacy of the proposed model is demonstrated through extensive numerical analysis. Particularly, when the number of task nodes and NCPs reaches 1:2, the task completion rate can reach 99.33%.  more » « less
Award ID(s):
2148788
NSF-PAR ID:
10397366
Author(s) / Creator(s):
; ; ; ;
Date Published:
Journal Name:
Computing
ISSN:
0010-485X
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Fog computing, which distributes computing resources to multiple locations between the Internet of Things (IoT) devices and the cloud, is attracting considerable attention from academia and industry. Yet, despite the excitement about the potential of fog computing, few comprehensive studies quantitatively characterizing the properties of fog computing architectures have been conducted. In this paper we examine the statistical properties of fog computing task completion latencies, which are important to understand to develop algorithms that match IoT nodes’ tasks with the best execution points within the fog computing substrate. Towards characterizing task completion latencies, we developed and deployed a set of benchmarks in 6 different locations, which included local nodes of different grades, conventional cloud computing services in two different regions, and Amazon Web Services (AWS) and Microsoft Azure serverless computing options. Using the developed infrastructure, we conducted a series of targeted experiments with a node invoking our benchmarks from different locations and in different conditions. The empirical study elucidated several important properties of task execution latencies, including latency variation across different execution points and execution options, and stability with respect to time. The study also demonstrated important properties of serverless execution options, and showed that statistical structure of computing latencies can be accurately characterized based on a small number (only 10–50) of latency samples. The complete measurement set we have captured as part of this study is publicly available. 
    more » « less
  2. Spatial crowdsourcing (SC) enables task owners (TOs) to outsource spatial-related tasks to a SC-server who engages mobile users in collecting sensing data at some specified locations with their mobile devices. Data aggregation, as a specific SC task, has drawn much attention in mining the potential value of the massive spatial crowdsensing data. However, the release of SC tasks and the execution of data aggregation may pose considerable threats to the privacy of TOs and mobile users, respectively. Besides, it is nontrivial for the SC-server to allocate numerous tasks efficiently and accurately to qualified mobile users, as the SC-server has no knowledge about the entire geographical user distribution. To tackle these issues, in this paper, we introduce a fog-assisted SC architecture, in which many fog nodes deployed in different regions can assist the SC-server to distribute tasks and aggregate data in a privacy-aware manner. Specifically, a privacy-aware task allocation and data aggregation scheme (PTAA) is proposed leveraging bilinear pairing and homomorphic encryption. PTAA supports representative aggregate statistics (e.g.,sum, mean, variance, and minimum) with efficient data update while providing strong privacy protection. Security analysis shows that PTAA can achieve the desirable security goals. Extensive experiments also demonstrate its feasibility and efficiency. 
    more » « less
  3. Summary

    The ubiquitous use of location‐based services (LBS) through smart devices produces massive amounts of location data. An attacker, with an access to such data, can reveal sensitive information about users. In this paper, we study location inference attacks based on the probability distribution of historical location data, travel time information between locations using knowledge of a map, and short and long‐term observation of privacy‐preserving queries. We show that existing privacy‐preserving approaches are vulnerable to such attacks. In this context, we propose a novel location privacy‐preserving approach, called KLAP, based on the three fundamental obfuscation requirements: minimumk‐locations,l‐diversity, and privacyareapreservation. KLAP adopts a personalized privacy preference for sporadic, frequent, and continuous LBS use cases. Specifically, it generates a secure concealing region (CR) to obfuscate the user's location and directs that CR to the service provider. The main contribution of this work is twofold. First, a CR pruning technique is devised to establish a balance between privacy and delay in LBS usage. Second, a new attack model called a long‐term obfuscated location tracking attack, and its countermeasure is proposed and evaluated both theoretically and empirically. We assess KLAP with two real‐world datasets. Experimental results show that it can achieve better privacy, reduced delay, and lower communication costs than existing state‐of‐the‐art methods.

     
    more » « less
  4. Both energy-efficiency and real-time performance are critical requirements in many embedded systems applications such as self-driving car, robotic system, disaster response, and security/safety control. These systems entail a myriad of real-time tasks, where each task itself is a parallel task that can utilize multiple computing units at the same time. Driven by the increasing demand for parallel tasks, multi-core embedded processors are inevitably evolving to many-core. Existing work on real-time parallel tasks mostly focused on real-time scheduling without addressing energy consumption. In this paper, we address hard real-time scheduling of parallel tasks while minimizing their CPU energy consumption on multicore embedded systems. Each task is represented as a directed acyclic graph (DAG) with nodes indicating different threads of execution and edges indicating their dependencies. Our technique is to determine the execution speeds of the nodes of the DAGs to minimize the overall energy consumption while meeting all task deadlines. It incorporates a frequency optimization engine and the dynamic voltage and frequency scaling (DVFS) scheme into the classical real-time scheduling policies (both federated and global) and makes them energy-aware. The contributions of this paper thus include the first energy-aware online federated scheduling and also the first energy-aware global scheduling of DAGs. Evaluation using synthetic workload through simulation shows that our energy-aware real-time scheduling policies can achieve up to 68% energy-saving compared to classical (energy-unaware) policies. We have also performed a proof of concept system evaluation using physical hardware demonstrating the energy efficiency through our proposed approach. 
    more » « less
  5. Crowdsourcing has become an efficient paradigm to utilize human intelligence to perform tasks that are challenging for machines. Many incentive mechanisms for crowdsourcing systems have been proposed. However, most of existing incentive mechanisms assume that there are sufficient participants to perform crowdsourcing tasks. In large-scale crowdsourcing scenarios, this assumption may be not applicable. To address this issue, we diffuse the crowdsourcing tasks in social network to increase the number of participants. To make the task diffusion more applicable to crowdsourcing system, we enhance the classic Independent Cascade model so the influence is strongly connected with both the types and topics of tasks. Based on the tailored task diffusion model, we formulate the Budget Feasible Task Diffusion ( BFTD ) problem for maximizing the value function of platform with constrained budget. We design a parameter estimation algorithm based on Expectation Maximization algorithm to estimate the parameters in proposed task diffusion model. Benefitting from the submodular property of the objective function, we apply the budget-feasible incentive mechanism, which satisfies desirable properties of computational efficiency, individual rationality, budget-feasible, truthfulness, and guaranteed approximation, to stimulate the task diffusers. The simulation results based on two real-world datasets show that our incentive mechanism can improve the number of active users and the task completion rate by 9.8% and 11%, on average. 
    more » « less