TY - JOUR
T1 - Flexible scheduling of transactional memory on trees
AU - Busch, Costas
AU - Chlebus, Bogdan S.
AU - Herlihy, Maurice
AU - Popovic, Miroslav
AU - Poudel, Pavan
AU - Sharma, Gokarna
N1 - Publisher Copyright:
© 2023 Elsevier B.V.
PY - 2023/11/2
Y1 - 2023/11/2
N2 - 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 a k factor approximation where k is the maximum number of objects per transaction.
AB - 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 a k factor approximation where k is the maximum number of objects per transaction.
KW - Communication cost
KW - Distributed system
KW - Network
KW - Shared object
KW - Transactional memory
UR - http://www.scopus.com/inward/record.url?scp=85171828832&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85171828832&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2023.114184
DO - 10.1016/j.tcs.2023.114184
M3 - Article
AN - SCOPUS:85171828832
SN - 0304-3975
VL - 978
JO - Theoretical Computer Science
JF - Theoretical Computer Science
M1 - 114184
ER -