Talley Amir and James Aspnes. Privacy in population protocols with probabilistic scheduling. Theoretical Computer Science 1024:114926, January 2025 (SSS 2023 special issue). An earlier version appeared in Stabilization, Safety, and Security of Distributed Systems (SSS 2023), October 2023, pp. 400–413.
The population protocol model offers a theoretical framework for designing and analyzing distributed algorithms among limited-resource mobile agents. While the original population protocol model considers the concept of anonymity, the issue of privacy is not investigated thoroughly. However, there is a need for time- and space-efficient privacy-preserving techniques in the population protocol model if these algorithms are to be implemented in settings handling sensitive data, such as sensor networks, IoT devices, and drones. In this work, we introduce several formal definitions of privacy, ranging from assuring only plausible deniability of the population input vector to having a full information-theoretic guarantee that knowledge beyond an agent’s input and output bear no influence on the probability of a particular input vector. We then apply these definitions to both existing and novel protocols. We show that the Remainder-computing protocol of Delporte-Gallet et al. (which is proven to satisfy output independent privacy under adversarial scheduling) is not information-theoretically private under probabilistic scheduling. In contrast, we provide a new algorithm and demonstrate that it correctly and information-theoretically privately computes Remainder under probabilistic scheduling.
@article{AmirA2005,
title = {Privacy in population protocols with probabilistic scheduling},
journal = {Theoretical Computer Science},
volume = {1024},
pages = {114926},
year = {2025},
issn = {0304-3975},
doi = {https://doi.org/10.1016/j.tcs.2024.114926},
url = {https://www.sciencedirect.com/science/article/pii/S0304397524005437},
author = {Talley Amir and James Aspnes},
keywords = {Mobile ad-hoc networks, Population protocols, Information-theoretic privacy},
abstract = {The population protocol model [2] offers a theoretical framework for designing and analyzing distributed algorithms among limited-resource mobile agents. While the original population protocol model considers the concept of anonymity, the issue of privacy is not investigated thoroughly. However, there is a need for time- and space-efficient privacy-preserving techniques in the population protocol model if these algorithms are to be implemented in settings handling sensitive data, such as sensor networks, IoT devices, and drones. In this work, we introduce several formal definitions of privacy, ranging from assuring only plausible deniability of the population input vector to having a full information-theoretic guarantee that knowledge beyond an agent's input and output bear no influence on the probability of a particular input vector. We then apply these definitions to both existing and novel protocols. We show that the Remainder-computing protocol from [9] (which is proven to satisfy output independent privacy under adversarial scheduling) is not information-theoretically private under probabilistic scheduling. In contrast, we provide a new algorithm and demonstrate that it correctly and information-theoretically privately computes Remainder under probabilistic scheduling.}
}