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, January). Dispersion, Capacitated Nodes, and the Power of a Trusted Shepherd. Presented at 25th International Conference on Distributed Computing and Networking, Chennai, India

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 25th International Conference on Distributed Computing and Networking
• 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)
• Peer Reviewed: Peer Reviewed
• 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