TY - GEN
T1 - Flexible Scheduling of Transactional Memory on Trees
AU - Busch, Konstantin
AU - Chlebus, Bogdan S.
AU - Herlihy, Maurice
AU - Popovic, Miroslav
AU - Poudel, Pavan
AU - Sharma, Gokarna
N1 - Funding Information:
G. Sharma was supported by National Science Foundation under Grant No. CAREER CNS-2045597.
Funding Information:
Acknowledgements. G. Sharma was supported by National Science Foundation
Publisher Copyright:
© 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.
PY - 2022
Y1 - 2022
N2 - We study the efficiency of executing transactions in a distributed transactional memory system. The system is modeled as a wired 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 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 they execute. 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 wired 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 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 they execute. 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=85142673041&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85142673041&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-21017-4_10
DO - 10.1007/978-3-031-21017-4_10
M3 - Conference contribution
AN - SCOPUS:85142673041
SN - 9783031210167
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 146
EP - 163
BT - Stabilization, Safety, and Security of Distributed Systems - 24th International Symposium, SSS 2022, Proceedings
A2 - Devismes, Stéphane
A2 - Petit, Franck
A2 - Altisen, Karine
A2 - Di Luna, Giuseppe Antonio
A2 - Fernandez Anta, Antonio
PB - Springer Science and Business Media Deutschland GmbH
T2 - 24th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2022
Y2 - 15 November 2022 through 17 November 2022
ER -