Competitive Analysis of Organization Networks or Multicast Acknowledgment: How Much to Wait?
Competitive Analysis of Organization Networks or Multicast Acknowledgment: How Much to Wait?
复制标题
组织网络或多播确认的竞争分析：需要等待多久？
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
Shailesh Vaya
中科院分区：
文献类型：
--
作者：
C. Brito;E. Koutsoupias;Shailesh Vaya
我们研究，从竞争分析的角度来看，通信成本和延迟成本之间的权衡，或简单的发送或等待的困境层次根树。该问题是一个抽象的通信网络上的消息聚合问题和网络层次结构中的组织问题，我们认为最自然的变种的问题，分布式异步政权，并给出严格的（在一个小的附加常数）上界和下界的竞争比的优化问题。我们还考虑了集中式版本的问题，其中有一个中央实体，它保持更新任何传入的消息到网络中，并可以控制在网络中的消息的内部传递。对于集中式的设置，我们结合联合收割机的自然租买策略与预测技术，以实现第一个常数竞争比算法的任何非平凡类的网络拓扑结构。
We study, from the perspective of competitive analysis, the trade-off between communication cost and delay cost, or simply the send-or-wait dilemma on a hierarchical rooted tree. The problem is an abstraction of the message aggregation problem on communication networks and an organizational problem in network hierarchies.We consider the most natural variant of the problem, the distributed asynchronous regime, and give tight (within a small additive constant) upper and lower bounds on the competitive ratio of the optimization problem. We also consider the centralized version of the problem, in which there is a central entity which remains updated about any incoming messages to the network and which can control the internal delivery of messages in the network. For the centralized setting, we combine a natural rent-to-buy strategy with prediction techniques to achieve the first constant competitive ratio algorithm for any non-trivial class of network topologies.