Dispersion, Capacitated Nodes, and the Power of a Trusted Shepherd

Moses Jr., William K.; Redlich, Amanda

Abstract

In this paper, we look at and expand the problems of dispersion and Byzantine dispersion of mobile robots on a graph, introduced by Augustine and Moses Jr. [ICDCN 2018] and by Molla, Mondal, and Moses Jr. [ALGOSENSORS 2020], respectively, to graphs where nodes have variable capacities. We use the idea of a single shepherd, a more powerful robot that will never act in a Byzantine manner, to achieve fast Byzantine dispersion, even when other robots may be strong Byzantine in nature. We also show the benefit of a shepherd for dispersion on capacitated graphs when no Byzantine robots are present.

Citation

Moses Jr., W. K., & Redlich, A. (2024). Dispersion, Capacitated Nodes, and the Power of a Trusted Shepherd. In ICDCN '24: Proceedings of the 25th International Conference on Distributed Computing and Networking (400-405). https://doi.org/10.1145/3631461.3632310

• Conference Name: 25th International Conference on Distributed Computing and Networking
• Conference Location: Chennai, India
• Start Date: Jan 4, 2024
• End Date: Jan 7, 2024
• Acceptance Date: Oct 30, 2023
• Online Publication Date: Jan 22, 2024
• Publication Date: 2024-01
• Deposit Date: Dec 8, 2023
• Publicly Available Date: Jan 22, 2024
• Publisher: Association for Computing Machinery (ACM)
• Pages: 400-405
• Book Title: ICDCN '24: Proceedings of the 25th International Conference on Distributed Computing and Networking
• ISBN: 9798400716737
• DOI: https://doi.org/10.1145/3631461.3632310
• Public URL: https://durham-repository.worktribe.com/output/1985136