  An increasing number of applications rely on complex inference tasks that are
based on machine learning (ML). Currently, there are two options to run such
tasks: either they are served directly by the end device (e.g., smartphones,
IoT equipment, smart vehicles), or offloaded to a remote cloud. Both options
may be unsatisfactory for many applications: local models may have inadequate
accuracy, while the cloud may fail to meet delay constraints. In this paper, we
present the novel idea of inference delivery networks (IDNs), networks of
computing nodes that coordinate to satisfy ML inference requests achieving the
best trade-off between latency and accuracy. IDNs bridge the dichotomy between
device and cloud execution by integrating inference delivery at the various
tiers of the infrastructure continuum (access, edge, regional data center,
cloud). We propose a distributed dynamic policy for ML model allocation in an
IDN by which each node dynamically updates its local set of inference models
based on requests observed during the recent past plus limited information
exchange with its neighboring nodes. Our policy offers strong performance
guarantees in an adversarial setting and shows improvements over greedy
heuristics with similar complexity in realistic scenarios.
