A variant of the arrow distributed directory with low average complexity

摘要

This paper considers an enhancement to the arrow distributed directory protocol,introduced in [8].The arrow protocol implements a directory service,allowing nodes to locate mobile objects in a distributed system,while ensuring mutual exclusion in the presence of concurrent requests.The arrow protocoal makes use of a minimum spanning tree (MST) T_m of the network,selected during system initialization,resulting in a worst-case overhead ratio of (1+stretch (T_m))/2.However,we observe that the arrow protocol is correct communicating over any spanning tree T of G.