A Poly-Log Approximation for Transaction Scheduling in Fog-Cloud Computing and Beyond
Ramesh Adhikari, Costas Busch, Pavan Poudel
交易调度对于在分布式系统中以无冲突的方式有效地分配共享资源至关重要。 我们研究雾-云计算模型中事务的有效调度,其中事务及其相关的共享对象可以在网络中移动。 时间表可能要求对象移动到事务节点,或事务移动到对象节点。 此外,时间表可以确定对象和事务都相遇的中间节点。 我们的目标是将总合并成本降至最低。 我们专注于不断加倍的维度网络,这些网络在实践中经常出现。 我们考虑一个批处理问题,其中一组任意节点有需要调度的事务。 首先,我们考虑所有事务所需的单个共享对象,并呈现一个调度算法,该算法给出了最优调度的O(log n ·log D)近似值,其中n是节点的数量,D是网络的直径。 后来,我们考虑事务访问多个共享对象(每次事务最多为 k 个对象),并提供一个调度算法,给出一个 O(k ·log n ·log D) 近似。 我们还提供了一个完全分布式的调度算法版本,其中节点不需要事务的全球知识。
Transaction scheduling is crucial to efficiently allocate shared resources in a conflict-free manner in distributed systems. We investigate the efficient scheduling of transactions in a network of fog-cloud computing model, where transactions and their associated shared objects can move within the network. The schedule may require objects to move to transaction nodes, or the transactions to move to the object nodes. Moreover, the schedule may determine intermediate nodes where both objects and t...