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
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.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
