Time-communication impossibility results for distributed transactional memory

Costas Busch, Maurice Herlihy, Miroslav Popovic, Gokarna Sharma

Research output: Contribution to journalArticlepeer-review

10 Scopus citations


We consider scheduling problems in the data flow model of distributed transactional memory. Objects shared by transactions move from one network node to another by following network paths. We examine how the objects’ transfer in the network affects the completion time of all transactions and the total communication cost. We show that there are problem instances for which there is no scheduling algorithm that can simultaneously minimize the completion time and communication cost. These instances reveal a trade-off, minimizing execution time implies high communication cost and vice versa. On the positive side, we provide scheduling algorithms which are independently communication cost near-optimal or execution time efficient.

Original languageEnglish (US)
Pages (from-to)471-487
Number of pages17
JournalDistributed Computing
Issue number6
StatePublished - Nov 1 2018
Externally publishedYes


  • Communication cost
  • Distributed systems
  • Execution time
  • Impossibility results
  • Network congestion
  • Transactional memory

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Computational Theory and Mathematics


Dive into the research topics of 'Time-communication impossibility results for distributed transactional memory'. Together they form a unique fingerprint.

Cite this