The Arvy Distributed Directory Protocol

In this paper we consider the problem of designing a distributed directory service. The two classic directory service protocols are Arrow and Ivy. Arrow performs well if the network is a tree, while Ivy performs well on complete graphs. However, there are graphs for which both Arrow and Ivy yield poor performance. In this paper, we propose a new distributed directory protocol, Arvy. Arvy is a natural extension of both Arrow and Ivy, generalizing both, while keeping their simplicity and strengths. Our main contribution is to prove Arvy's correctness, in asynchronous networks with concurrent requests, for arbitrary topologies. Regarding performance, we show that Arvy achieves constant competitive ratio on rings using constant space per node.