Time-communication impossibility results for distributed transactional memory
Time-communication impossibility results for distributed transactional memory
复制标题
分布式事务内存的时间通信不可能性结果
DOI：
10.1007/s00446-017-0318-y
复制
发表时间：
2017
影响因子：
1.3
通讯作者：
Gokarna Sharma
中科院分区：
文献类型：
--
作者：
C. Busch;Maurice Herlihy;M. Popovic;Gokarna Sharma
研究了分布式事务存储的数据流模型中的调度问题。事务共享的对象通过遵循网络路径从一个网络节点移动到另一个网络节点。我们考察了对象在网络中的传输如何影响所有事务的完成时间和总通信成本。我们证明了存在这样的问题实例，即不存在能够同时最小化完工时间和通信成本的调度算法。这些实例揭示了一种权衡，最小化执行时间意味着较高的通信成本，反之亦然。从积极的方面来说，我们提供了独立于通信成本接近最优或执行时间有效的调度算法。
We consider scheduling problems in the data flow model of distributed transactional memory. Objects shared by transactions move from one network node to another by following network paths. We examine how the objects’ transfer in the network affects the completion time of all transactions and the total communication cost. We show that there are problem instances for which there is no scheduling algorithm that can simultaneously minimize the completion time and communication cost. These instances reveal a trade-off, minimizing execution time implies high communication cost and vice versa. On the positive side, we provide scheduling algorithms which are independently communication cost near-optimal or execution time efficient.