Distributed Edge Machine Learning Pipeline Scheduling with Reverse Auctions

Scheduling distributed machine learning pipelines in edge environments is a growing area of research as developers work to bring large, high-accuracy models to relatively low-powered devices. Edge environment dynamics, such as device availability and connectivity, make distributed scheduling a more challenging problem than in traditional cloud environments. Existing approaches usually require significant a priori knowledge of the environment and make assumptions about model availability, both of which are impractical in real edge deployments. We address this problem by proposing a simple and efficient reverse auction algorithm, where a device that wants to distribute a large machine learning workload requests bids from available resources in the environment to construct connected pipelines. We implement our reverse auction scheduling on an existing distributed machine learning pipeline framework and perform an empirical evaluation using a real distributed edge computing testbed. We prove that scheduling distributed pipelines without repeating devices is an NP-complete problem, but that finding good latency or throughput pipelines is tractable for fixed device orderings.