Local-on-Average Distributed Tasks
Local-on-Average Distributed Tasks
复制标题
本地平均分布式任务
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Shay Solomon
中科院分区：
文献类型：
--
作者：
M. Parter;D. Peleg;Shay Solomon
如果一个分布式任务的时间复杂度是（几乎）恒定的，则它是局部的，否则它是全局的。不幸的是，本地任务相对较少，大多数分布式任务需要的时间至少是网络规模的对数（通常更高）。在动态设置中，即，当网络经历重复和频繁的拓扑变化（例如顶点和边的插入和删除）时，希望能够围绕网络的修改部分执行局部更新过程，而不是在每次变化之后从头开始运行静态全局算法。本文提出了一个假设，即许多（静态）非本地分布式任务是本地的平均在动态设置，即他们的摊销时间复杂度为O（log* n）。为了建立这个假设的可验证性，我们提出了一个策略，将静态O（polylog（n））时间算法转换为动态O（log* n）摊销时间更新程序。然后，我们证明了我们的策略的有用性，通过将其应用到几个基本问题，其静态时间复杂度是对数，包括森林分解，边方向和着色稀疏图，并表明其摊销的时间复杂度在动态设置确实是O（log* n）。
A distributed task is local if its time complexity is (nearly) constant, otherwise it is global. Unfortunately, local tasks are relatively scarce, and most distributed tasks require time at least logarithmic in the network size (and often higher than that). In a dynamic setting, i.e., when the network undergoes repeated and frequent topological changes, such as vertex and edge insertions and deletions, it is desirable to be able to perform a local update procedure around the modified part of the network, rather than running a static global algorithm from scratch following each change. This paper makes a step towards establishing the hypothesis that many (statically) non-local distributed tasks are local-on-average in the dynamic setting, namely, their amortized time complexity is O(log* n). Towards establishing the plausibility of this hypothesis, we propose a strategy for transforming static O(polylog(n)) time algorithms into dynamic O(log* n) amortized time update procedures. We then demonstrate the usefulness of our strategy by applying it to several fundamental problems whose static time complexity is logarithmic, including forest-decomposition, edge-orientation and coloring sparse graphs, and show that their amortized time complexity in the dynamic setting is indeed O(log* n).