Complexity analysis for DROPLET: Distributed Operator Placement for IoT Applications Spanning Edge and Cloud Resources
complexity, placement, distributed, edge devices, cloud, DAG
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.