Impossibility results for distributed transactional memory

Costas Busch; Maurice Herlihy; Miroslav Popovic; Gokarna Sharma

doi:10.1145/2767386.2767433

Impossibility results for distributed transactional memory

Costas Busch, Maurice Herlihy, Miroslav Popovic, Gokarna Sharma

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

6 Scopus citations

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 nearoptimal or execution time efficient.

Original language	English (US)
Title of host publication	PODC 2015 - Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing
Publisher	Association for Computing Machinery
Pages	207-215
Number of pages	9
ISBN (Electronic)	9781450336178
DOIs	https://doi.org/10.1145/2767386.2767433
State	Published - Jul 21 2015
Externally published	Yes
Event	ACM Symposium on Principles of Distributed Computing, PODC 2015 - Donostia-San Sebastian, Spain Duration: Jul 21 2015 → Jul 23 2015

Publication series

Name	Proceedings of the Annual ACM Symposium on Principles of Distributed Computing
Volume	2015-July

Conference

Conference	ACM Symposium on Principles of Distributed Computing, PODC 2015
Country/Territory	Spain
City	Donostia-San Sebastian
Period	7/21/15 → 7/23/15

Keywords

Communication cost
Distributed systems
Execution time
Impossibility results
Transactional memory

ASJC Scopus subject areas

Software
Hardware and Architecture
Computer Networks and Communications

Access to Document

10.1145/2767386.2767433

Cite this

Busch, C., Herlihy, M., Popovic, M., & Sharma, G. (2015). Impossibility results for distributed transactional memory. In PODC 2015 - Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (pp. 207-215). (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing; Vol. 2015-July). Association for Computing Machinery. https://doi.org/10.1145/2767386.2767433

Impossibility results for distributed transactional memory. / Busch, Costas; Herlihy, Maurice; Popovic, Miroslav et al.
PODC 2015 - Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing. Association for Computing Machinery, 2015. p. 207-215 (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing; Vol. 2015-July).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Busch, C, Herlihy, M, Popovic, M & Sharma, G 2015, Impossibility results for distributed transactional memory. in PODC 2015 - Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing. Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, vol. 2015-July, Association for Computing Machinery, pp. 207-215, ACM Symposium on Principles of Distributed Computing, PODC 2015, Donostia-San Sebastian, Spain, 7/21/15. https://doi.org/10.1145/2767386.2767433

@inproceedings{652f549e47334c2cbf2f6c1fde26c9c8,

title = "Impossibility results for distributed transactional memory",

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 nearoptimal or execution time efficient.",

keywords = "Communication cost, Distributed systems, Execution time, Impossibility results, Transactional memory",

author = "Costas Busch and Maurice Herlihy and Miroslav Popovic and Gokarna Sharma",

year = "2015",

month = jul,

day = "21",

doi = "10.1145/2767386.2767433",

language = "English (US)",

series = "Proceedings of the Annual ACM Symposium on Principles of Distributed Computing",

publisher = "Association for Computing Machinery",

pages = "207--215",

booktitle = "PODC 2015 - Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing",

}

TY - GEN

T1 - Impossibility results for distributed transactional memory

AU - Busch, Costas

AU - Herlihy, Maurice

AU - Popovic, Miroslav

AU - Sharma, Gokarna

PY - 2015/7/21

Y1 - 2015/7/21

N2 - 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 nearoptimal or execution time efficient.

AB - 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 nearoptimal or execution time efficient.

KW - Communication cost

KW - Distributed systems

KW - Execution time

KW - Impossibility results

KW - Transactional memory

UR - http://www.scopus.com/inward/record.url?scp=84957663060&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84957663060&partnerID=8YFLogxK

U2 - 10.1145/2767386.2767433

DO - 10.1145/2767386.2767433

M3 - Conference contribution

AN - SCOPUS:84957663060

T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

SP - 207

EP - 215

BT - PODC 2015 - Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing

PB - Association for Computing Machinery

T2 - ACM Symposium on Principles of Distributed Computing, PODC 2015

Y2 - 21 July 2015 through 23 July 2015

ER -

Impossibility results for distributed transactional memory

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this