Carleton University - School of Computer Science Honours Project
Summer 2019
Searching On An Infinite Line : A Deterministic Asynchronous Rendezvous Of Two Agents
Christopher Blackman
SCS Honours Project Image
ABSTRACT
Two mobile agents which have distinct labels are located on an infinite line. Both agents are asynchronous, and each one is controlled by an algorithm dependent on its finite label. Agents do not know orientation, or topology, nor can they communicate with other agents. The competitive ratio is defined by the total worst case distance travelled by the agents divided by the initial distance between the agents; this initial distance is denoted by D. We show that for an infinite line with unknown distance D, the competitive ratio is O( b^O(|L_{min}|) ), such that b>1, and we obtain a constant ratio. Where L_{min} is the minimum label size.