University of Illinois Urbana-Champaign

Complexity analysis for DROPLET: Distributed Operator Placement for IoT Applications Spanning Edge and Cloud Resources

Sandur, Atul; Elgamal, Tarek; Agha, Gul; Nahrstedt, Klara

Content Files
complexity-analysis-droplet.pdf

Permalink

https://hdl.handle.net/2142/99062

Description

Title
Complexity analysis for DROPLET: Distributed Operator Placement for IoT Applications Spanning Edge and Cloud Resources
Author(s)
  • Sandur, Atul
  • Elgamal, Tarek
  • Agha, Gul
  • Nahrstedt, Klara
Issue Date
2018
Keyword(s)
complexity, placement, distributed, edge devices, cloud, DAG
Date of Ingest
2018-02-19T01:28:26Z
Abstract
Internet of Things (IoT) applications generate massive amounts of real-time data. Owners of such data strive to make predictions/inference from large streams of complex input such as video feeds, often by deploying applications that involve machine learning and image processing operations. A typical deployment of IoT applications includes edge devices to acquire the input data and provide processing/storage capacity closer to the location where the data is captured. An important challenge for IoT applications is deciding which operations to be executed on an edge device and which operations should be carried out on the cloud, in order to minimize the completion time of all operations. We call this the distributed operator placement problem. In this report, we show that the distributed operator placement problem is NP-complete. We then provide computational complexity analysis of a dynamic programming algorithm called Droplet, which is a heuristic to scalably partition operations in IoT applications across shared edge and cloud resources, while minimizing the completion time of all operations. Our analysis shows that Droplet scales log-linearly in the total number of operations.
Type of Resource
text
Genre of Resource
Technical Report
Language
en
Permalink
http://hdl.handle.net/2142/99062

Owning Collections

Research and Tech Reports - Computer Science PRIMARY