Flexible Scheduling of Transactional Memory on Trees

Konstantin Busch, Bogdan S. Chlebus, Maurice Herlihy, Miroslav Popovic, Pavan Poudel, Gokarna Sharma

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationStabilization, Safety, and Security of Distributed Systems - 24th International Symposium, SSS 2022, Proceedings
EditorsStéphane Devismes, Franck Petit, Karine Altisen, Giuseppe Antonio Di Luna, Antonio Fernandez Anta
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages18
ISBN (Print)9783031210167
StatePublished - 2022
Event24th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2022 - Clermont-Ferrand, France
Duration: Nov 15 2022Nov 17 2022

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13751 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference24th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2022


  • Communication cost
  • Distributed system
  • Network
  • Shared object
  • Transactional memory

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Flexible Scheduling of Transactional Memory on Trees'. Together they form a unique fingerprint.

Cite this