Recent years have seen fog and edge computing emerge as new paradigms to provide more responsive software services. While both these concepts have numerous advantages in terms of efficiency and user experience by moving computational tasks closer to where they are needed, effective service scheduling requires a different approach in the geographically widespread fog than it does in the cloud. Additionally, fog and edge networks are volatile, and of such a scale that gathering all the required data for a centralized scheduler results in prohibitively high memory use and network traffic. Since the fog is a geographically distributed computational substrate, a suitable solution is to use a decentralized service scheduler, deployed on all nodes, which can monitor and deploy services in its neighbourhood without having to know the entire service topology. This article presents a fully decentralized service scheduler, labeled “SoSwirly”, for fog and edge networks containing hundreds of thousands of devices. It scales service instances as required by the edge, based on available resources and flexibly defined distance metrics. A mathematical model of fog networks is presented, along with a theoretical analysis and an empirical evaluation which indicate that under the right conditions, SoSwirly is highly scalable. It is also explained how to achieve these conditions by carefully selecting configuration parameters. Concretely, only 15 MiB of memory is required on each node, and network traffic in the evaluations is less than 4 Kbps on edge nodes, while 4–6% more service instances are created than by a centralized algorithm.