Open Systems Laboratory at Illinois

Complexity analysis for droplet: distributed operator placement for iot applications spanning edge and cloud resources

By Atul Sandur, Tarek Elgamal, Gul Agha, and Klara Nahrstedt. In Illinois Digital Environment for Access to Learning and Scholarship, 1–6. 2018.

Publisher Link:


Internet of Things (IoT) applications generate massive amounts of real-time streaming data. IoT data owners strive to make predictions/inferences from these large streams of data often through applying machine learning, and image processing operations. A typical deployment of such applications includes edge devices to provide processing/storage operations closer to the location where the streaming data is captured. An important challenge for IoT applications is deciding which operations to execute on an edge device and which operations should be carried out in the cloud. In this paper, we propose a scalable dynamic programming algorithm called DROPLET, to partition operations in IoT applications across shared edge and cloud resources, while minimizing completion time of the end-to-end operations. We evaluate DROPLET using three real-world applications. Our results show that DROPLET finds a partitioning of operations having overall completion time within 4% of the optimum for these applications. It also scales to thousands of operations and outperforms closest heuristics in the literature, by being 10 times faster in running time while finding partitioning of operations with total completion time that is 20% better for the large applications that we simulated. We analyze DROPLET to show that it scales with total number of operations in log-linear time.


    author = "Sandur, Atul and Elgamal, Tarek and Agha, Gul and
              Nahrstedt, Klara",
    title = "Complexity analysis for DROPLET: Distributed Operator
             Placement for IoT Applications Spanning Edge and Cloud Resources",
    booktitle = "Illinois Digital Environment for Access to
                 Learning and Scholarship",
    doi = "",
    pages = "1--6",
    timestamp = "Tue, 25 Sep 2018 01:00:00 +0200",
    url = "",
    year = "2018",