Low Complexity Variants of the Arrow Distributed Directory

✍ Scribed by David Peleg; Eilon Reshef

• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 134 KB
• Volume: 63
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.2001.1787

✦ Synopsis

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 protocol makes use of a minimum spanning tree T m of the network, selected during system initialization, resulting in a worst-case overhead ration of (1+ stretch(T m ))/2. However, we observe that the arrow protocol is correct communicating over any spanning tree T of G. We show that the worst-case overhead ratio is minimized by the minimum stretch spanning tree and that the problem cannot be approximated within a factor better than (1+`5)/2, unless P=NP. In contrast, other trees may be more suitable if one is interested in the average-case behavior of the network. We show that in the case where the distribution of the requests is fixed and known in advance, the expected communication is minimized using the minimum communication cost spanning tree (MCT). It is shown that the resulting MCT problem is a restricted case for which one can find a tree T over which the communication cost of the arrow protocol is at most 1.5 times the expected communication cost of an optimal protocol. We also show that even if the distribution of the requests is not fixed, or not known to the protocol in advance, then if the adversary is oblivious, one may use probabilistic approximation of metric space [2, 3] to ensure an expected overhead ratio of O(log n log log n) in general and an expected ratio of O(log n) in the case of constant dimension Euclidean graphs.