Low Complexity Variants of the Arrow Distributed Directory
Low Complexity Variants of the Arrow Distributed Directory
复制标题
Arrow 分布式目录的低复杂性变体
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
Eilon Reshef
中科院分区：
文献类型：
--
作者：
D. Peleg;Eilon Reshef
本文考虑对8中引入的ARROW分布式目录协议的增强。ARROW协议实现了目录服务，允许节点在分布式系统中定位移动对象，同时确保在存在并发请求的情况下存在互斥。ARROW协议利用在系统初始化时选择的网络的最小生成树Tm，导致最坏情况下的开销比为(1+STREAGE(TM))/2。然而，我们观察到ARROW协议在G的任何生成树T上的通信是正确的。我们证明了最坏情况下的开销比由最小扩展生成树最小化，并且问题不能在比(1+5)/2更好的因子内逼近，除非P=NP。相反，如果一个人对网络的平均情况行为感兴趣，其他树可能更合适。我们证明了在请求的分布是固定的且预先知道的情况下，使用最小通信代价生成树(MCT)来最小化期望的通信。结果表明，所得到的MCT问题是一种受限情况，可以找到一棵树T，在该树T上ARROW协议的通信开销至多是最优协议的期望通信开销的1.5倍。我们还证明了，即使请求的分布不是固定的，或者协议事先不知道，那么如果对手是健忘的，那么可以使用度量空间2，3的概率近似来确保总体上期望的开销比O(Lognlogn)，以及在恒维欧氏图的情况下期望的比率O(Logn)。
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 treeTm of the network, selected during system initialization, resulting in a worst-case overhead ration of (1+ stretch(Tm))/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(lognloglogn) in general and an expected ratio of O(logn) in the case of constant dimension Euclidean graphs.