Making "fast" atomic operations computationally tractable

Antonio Fernández Anta, Nicolas Nicolaou, Alexandru Popa

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

1 Citation (Scopus)

Abstract

Communication overhead is the most commonly used performance metric for the operation complexity of distributed algorithms in message-passing environments. However, aside with communication, many distributed operations utilize complex computations to reach their desired outcomes. Therefore, a most accurate operation latency measure should account of both computation and communication metrics. In this paper we focus on the efficiency of read and write operations in an atomic read/write shared memory emulation in the message-passing environment. We examine the operation complexity of the best known atomic register algorithm, presented in [2], that allows all read and write operations to complete in a single communication round-trip. Such operations are called fast. At its heart, the algorithm utilizes a predicate to allow processes to compute their outcome. We show that the predicate used in [2] is computationally hard, by devising a computationally equivalent problem and reducing that to Maximum Biclique, a known NP-hard problem. To improve the computational complexity of the algorithm we derive a new predicate that leads to a new algorithm, we call CCFAST, and has the following properties: (i) can be computed in polynomial time, rendering each read operation in CCFAST tractable compared to the read operations in the original algorithm, (ii) the messages used in CCFAST are reduced in size, compared to the original algorithm, by almost a linear factor, (iii) allows all operations in CCFAST to be fast, and (iv) allows CCFAST to preserve atomicity. A linear time algorithm for the computation of the new predicate is presented along with an analysis of the message complexity of the new algorithm. We believe that the new algorithm redefines the term fast capturing both the communication and the computation metrics of each operation.

Original languageEnglish
Title of host publication19th International Conference on Principles of Distributed Systems, OPODIS 2015
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages19.1-19.16
Volume46
ISBN (Electronic)9783939897989
DOIs
Publication statusPublished - Sep 1 2016
Event19th International Conference on Principles of Distributed Systems, OPODIS 2015 - Rennes, France
Duration: Dec 14 2015Dec 17 2015

Other

Other19th International Conference on Principles of Distributed Systems, OPODIS 2015
CountryFrance
CityRennes
Period12/14/1512/17/15

Fingerprint

Communication
Message passing
Computational complexity
Parallel algorithms
Polynomials
Data storage equipment

Keywords

  • Atomicity
  • Computational complexity
  • Read/write objects
  • Shared memory

ASJC Scopus subject areas

  • Software

Cite this

Anta, A. F., Nicolaou, N., & Popa, A. (2016). Making "fast" atomic operations computationally tractable. In 19th International Conference on Principles of Distributed Systems, OPODIS 2015 (Vol. 46, pp. 19.1-19.16). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.OPODIS.2015.19

Making "fast" atomic operations computationally tractable. / Anta, Antonio Fernández; Nicolaou, Nicolas; Popa, Alexandru.

19th International Conference on Principles of Distributed Systems, OPODIS 2015. Vol. 46 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016. p. 19.1-19.16.

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

Anta, AF, Nicolaou, N & Popa, A 2016, Making "fast" atomic operations computationally tractable. in 19th International Conference on Principles of Distributed Systems, OPODIS 2015. vol. 46, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, pp. 19.1-19.16, 19th International Conference on Principles of Distributed Systems, OPODIS 2015, Rennes, France, 12/14/15. https://doi.org/10.4230/LIPIcs.OPODIS.2015.19
Anta AF, Nicolaou N, Popa A. Making "fast" atomic operations computationally tractable. In 19th International Conference on Principles of Distributed Systems, OPODIS 2015. Vol. 46. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2016. p. 19.1-19.16 https://doi.org/10.4230/LIPIcs.OPODIS.2015.19
Anta, Antonio Fernández ; Nicolaou, Nicolas ; Popa, Alexandru. / Making "fast" atomic operations computationally tractable. 19th International Conference on Principles of Distributed Systems, OPODIS 2015. Vol. 46 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2016. pp. 19.1-19.16
@inproceedings{266470a114ae4c3db1fc5ceeb54b7a0e,
title = "Making {"}fast{"} atomic operations computationally tractable",
abstract = "Communication overhead is the most commonly used performance metric for the operation complexity of distributed algorithms in message-passing environments. However, aside with communication, many distributed operations utilize complex computations to reach their desired outcomes. Therefore, a most accurate operation latency measure should account of both computation and communication metrics. In this paper we focus on the efficiency of read and write operations in an atomic read/write shared memory emulation in the message-passing environment. We examine the operation complexity of the best known atomic register algorithm, presented in [2], that allows all read and write operations to complete in a single communication round-trip. Such operations are called fast. At its heart, the algorithm utilizes a predicate to allow processes to compute their outcome. We show that the predicate used in [2] is computationally hard, by devising a computationally equivalent problem and reducing that to Maximum Biclique, a known NP-hard problem. To improve the computational complexity of the algorithm we derive a new predicate that leads to a new algorithm, we call CCFAST, and has the following properties: (i) can be computed in polynomial time, rendering each read operation in CCFAST tractable compared to the read operations in the original algorithm, (ii) the messages used in CCFAST are reduced in size, compared to the original algorithm, by almost a linear factor, (iii) allows all operations in CCFAST to be fast, and (iv) allows CCFAST to preserve atomicity. A linear time algorithm for the computation of the new predicate is presented along with an analysis of the message complexity of the new algorithm. We believe that the new algorithm redefines the term fast capturing both the communication and the computation metrics of each operation.",
keywords = "Atomicity, Computational complexity, Read/write objects, Shared memory",
author = "Anta, {Antonio Fern{\'a}ndez} and Nicolas Nicolaou and Alexandru Popa",
year = "2016",
month = "9",
day = "1",
doi = "10.4230/LIPIcs.OPODIS.2015.19",
language = "English",
volume = "46",
pages = "19.1--19.16",
booktitle = "19th International Conference on Principles of Distributed Systems, OPODIS 2015",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
address = "Germany",

}

TY - GEN

T1 - Making "fast" atomic operations computationally tractable

AU - Anta, Antonio Fernández

AU - Nicolaou, Nicolas

AU - Popa, Alexandru

PY - 2016/9/1

Y1 - 2016/9/1

N2 - Communication overhead is the most commonly used performance metric for the operation complexity of distributed algorithms in message-passing environments. However, aside with communication, many distributed operations utilize complex computations to reach their desired outcomes. Therefore, a most accurate operation latency measure should account of both computation and communication metrics. In this paper we focus on the efficiency of read and write operations in an atomic read/write shared memory emulation in the message-passing environment. We examine the operation complexity of the best known atomic register algorithm, presented in [2], that allows all read and write operations to complete in a single communication round-trip. Such operations are called fast. At its heart, the algorithm utilizes a predicate to allow processes to compute their outcome. We show that the predicate used in [2] is computationally hard, by devising a computationally equivalent problem and reducing that to Maximum Biclique, a known NP-hard problem. To improve the computational complexity of the algorithm we derive a new predicate that leads to a new algorithm, we call CCFAST, and has the following properties: (i) can be computed in polynomial time, rendering each read operation in CCFAST tractable compared to the read operations in the original algorithm, (ii) the messages used in CCFAST are reduced in size, compared to the original algorithm, by almost a linear factor, (iii) allows all operations in CCFAST to be fast, and (iv) allows CCFAST to preserve atomicity. A linear time algorithm for the computation of the new predicate is presented along with an analysis of the message complexity of the new algorithm. We believe that the new algorithm redefines the term fast capturing both the communication and the computation metrics of each operation.

AB - Communication overhead is the most commonly used performance metric for the operation complexity of distributed algorithms in message-passing environments. However, aside with communication, many distributed operations utilize complex computations to reach their desired outcomes. Therefore, a most accurate operation latency measure should account of both computation and communication metrics. In this paper we focus on the efficiency of read and write operations in an atomic read/write shared memory emulation in the message-passing environment. We examine the operation complexity of the best known atomic register algorithm, presented in [2], that allows all read and write operations to complete in a single communication round-trip. Such operations are called fast. At its heart, the algorithm utilizes a predicate to allow processes to compute their outcome. We show that the predicate used in [2] is computationally hard, by devising a computationally equivalent problem and reducing that to Maximum Biclique, a known NP-hard problem. To improve the computational complexity of the algorithm we derive a new predicate that leads to a new algorithm, we call CCFAST, and has the following properties: (i) can be computed in polynomial time, rendering each read operation in CCFAST tractable compared to the read operations in the original algorithm, (ii) the messages used in CCFAST are reduced in size, compared to the original algorithm, by almost a linear factor, (iii) allows all operations in CCFAST to be fast, and (iv) allows CCFAST to preserve atomicity. A linear time algorithm for the computation of the new predicate is presented along with an analysis of the message complexity of the new algorithm. We believe that the new algorithm redefines the term fast capturing both the communication and the computation metrics of each operation.

KW - Atomicity

KW - Computational complexity

KW - Read/write objects

KW - Shared memory

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

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

U2 - 10.4230/LIPIcs.OPODIS.2015.19

DO - 10.4230/LIPIcs.OPODIS.2015.19

M3 - Conference contribution

VL - 46

SP - 19.1-19.16

BT - 19th International Conference on Principles of Distributed Systems, OPODIS 2015

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

ER -