Abstract
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 language | English (US) |
---|---|
Pages (from-to) | 471-487 |
Number of pages | 17 |
Journal | Distributed Computing |
Volume | 31 |
Issue number | 6 |
DOIs | |
State | Published - Nov 1 2018 |
Externally published | Yes |
Keywords
- 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