Flexible scheduling of transactional memory on trees
Flexible scheduling of transactional memory on trees
复制标题
DOI：
10.1016/j.tcs.2023.114184
复制
发表时间：
2023-09
期刊：
影响因子：
--
通讯作者：
C. Busch;Bogdan S. Chlebus;Maurice Herlihy;Miroslav Popovic;Pavan Poudel;Gokarna Sharma
中科院分区：
文献类型：
--
作者：
C. Busch;Bogdan S. Chlebus;Maurice Herlihy;Miroslav Popovic;Pavan Poudel;Gokarna Sharma
研究了分布式事务存储系统中事务的执行效率。该系统被建模为具有树状拓扑结构的静态网络。与以前的方法相反，我们允许事务及其请求对象在树中的节点之间同时移动。给定一批事务和共享对象，目标是生成一个执行事务的时间表，以最小化移动树中的事务和对象的成本。我们考虑了这两种技术来访问与事务移动相关的远程对象。在第一种技术中，事务将控制消息发送到收集请求对象的远程节点，而不是移动。在第二种技术中，事务迁移到收集对象以访问它们的远程节点。当所有事务使用单个对象时，我们给出了一种离线算法，该算法为两种技术产生最佳调度。对于每个事务有多个对象的一般情况，在第一种技术中，我们获得了一个具有常因子逼近最优的调度。在第二种技术中，对于事务迁移，我们给出一个因子近似值，其中每个事务的最大对象数。
We study the efficiency of executing transactions in a distributed transactional memory system. The system is modeled as a static network with the topology of a tree. Contrary to previous approaches, we allow the flexibility for both transactions and their requested objects to move simultaneously among the nodes in the tree. Given a batch of transactions and shared objects, the goal is to produce a schedule of executing the transactions that minimizes the cost of moving the transactions and the objects in the tree. We consider both techniques for accessing a remote object with respect to a transaction movement. In the first technique, instead of moving, transactions send control messages to remote nodes where the requested objects are gathered. In the second technique, the transactions migrate to the remote nodes where the objects are gathered to access them. When all the transactions use a single object, we give an offline algorithm that produces optimal schedules for both techniques. For the general case of multiple objects per transaction, in the first technique, we obtain a schedule with a constant-factor approximation of optimal. In the second technique, with transactions migrating, we give akfactor approximation wherekis the maximum number of objects per transaction.