We introduce a new problem which we call the Pony Express problem whereby n robots with differing speeds are situated over some domain and a message is placed at some commonly known point. Robots can acquire the message either by visiting its initial position or by encountering another robot that has already acquired it. The robots must collaborate to deliver the message to a given destination in the minimum time. In this paper, we study the Pony Express problem on the line where n robots are arbitrarily deployed along a finite segment. We are interested in both offline centralized and online distributed algorithms. In the online case, we assume the robots have limited knowledge of the initial configuration. In particular, the robots do not know the initial positions and speeds of the other robots nor even their own position and speed. They do, however, know the direction on the line in which to find the message and have the ability to compare speeds when they meet.

First, we study the Pony Express problem where the message is initially placed at one endpoint (labeled 0) of a segment and must be delivered to the other endpoint (labeled 1). We provide an O(n log n) running time offline algorithm as well as an optimal (competitive ratio 1) online algorithm. Then we study the Half-Broadcast problem where the message is at the center (at 0) and must be delivered to either one of the endpoints of the segment [−1, +1]. We provide an offline algorithm running in O(n^2 log n) time and we provide an online algorithm that attains a competitive ratio of 3/2, which we show is the best possible. Finally, we study the Broadcast problem where the message is at the center (at 0) and must be delivered to both endpoints of the segment [−1, +1]. Here we give an FPTAS in the offline case and an online algorithm that attains a competitive ratio of 9/5, which we show is tight.

https://link.springer.com/chapter/10.1007/978-3-030-79987-8_15