  We introduce a new problem which we call the Pony Express problem. n robots
with differing speeds are situated over some domain. 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. The objective is to deliver the message in minimum time. In this
paper we study the Pony Express problem on the line where n robots are
arbitrarily deployed along a finite segment. The robots have different speeds
and can move in both directions. 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 of a segment and must be delivered to the other
endpoint. We provide an O(n log n) running time offline algorithm as well as an
optimal online algorithm. Then we study the Half-Broadcast problem where the
message is at the center 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 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.
