short-paper

Brief announcement: on speculative replication of transactional systems

Authors:

Luis RodriguesAuthors Info & Claims

SPAA '10: Proceedings of the twenty-second annual ACM symposium on Parallelism in algorithms and architectures

Pages 69 - 71

https://doi.org/10.1145/1810479.1810492

Published: 13 June 2010 Publication History

Get Access

Abstract

We define the problem of speculative processing in a replicated transactional system layered on top of an optimistic atomic broadcast service. A realistic model is considered in which transactions' read and write sets are not a priori known and transactions' data access patterns may vary depending on the observed snapshot. We formalize a set of correctness and optimality properties ensuring the minimality and completeness of the set of explored serialization orders within the replicated transactional system.

References

[1]

P. A. Bernstein, V. Hadzilacos, and N. Goodman. Concurrency Control and Recovery in Database Systems. Addison-Wesley, 1987.

Digital Library

Google Scholar

[2]

M. Couceiro, P. Romano, N. Carvalho, and L. Rodrigues. D2STM: Dependable Distributed Software Transactional Memory. In Proc. Int. Symp. on Dependable Computing (PRDC). IEEE Computer Society Press, 2009.

Digital Library

Google Scholar

[3]

D. Powell (ed.). Special Issue on Group Communication, volume 39. ACM, 1996.

Digital Library

Google Scholar

[4]

G. Hetyei and E. Reiner. Permutation trees and variation statistics. Eur. J. Comb., 19(7):847--866, 1998.

Digital Library

Google Scholar

[5]

B. Kemme and G. Alonso. A suite of database replication protocols based on group communication primitives. In Proc. Int. Conf. on Distributed Computing Systems (ICDCS), IEEE Computer Society, 1998.

Digital Library

Google Scholar

[6]

B. Kemme, F. Pedone, G. Alonso, and A. Schiper. Processing transactions over optimistic atomic broadcast protocols. In Proc. Int. Conf. on Distributed Computing Systems (ICDCS), IEEE Computer Society, 1999.

Digital Library

Google Scholar

[7]

J. Mocito, A. Respicio, and L. Rodrigues. On statistically estimated optimistic delivery in large-scale total order protocols. In Proc. Int. Symp. on Dependable Computing (PRDC), IEEE Computer Society Press, 2006.

Digital Library

Google Scholar

[8]

R. Palmieri, F. Quaglia, P. Romano, and N. Carvalho. Evaluating database-oriented replication schemes in software transactional memory systems. In Proc. Workshop on Dependable Parallel and Distribued Networked Systems (DPDNS), IEEE Computer Society Press, 2010.

Crossref

Google Scholar

[9]

P. Romano, R. Palmieri, F. Quaglia, N. Carvalho and L. Rodrigues. On Speculative Replication of Transactional Systems, INESC-ID Tec. Rep. 38/2009, 2009.

Google Scholar

[10]

C. H. Papadimitriou. The serializability of concurrent database updates. J. ACM, 26(4): 631--653, 1979.

Digital Library

Google Scholar

[11]

F. Pedone and A. Schiper. Optimistic atomic broadcast: a pragmatic viewpoint. Theor. Comput. Sci., 291(1):79--101, 2003.

Digital Library

Google Scholar

[12]

P. Romano, N. Carvalho, and L. Rodrigues. Towards distributed software transactional memory systems. In Proc. of the Workshop on Large-Scale Distributed Systems and Middleware (LADIS), ACM press, 2008.

Digital Library

Google Scholar

Cited By

View all

Hirve SPalmieri RRavindran B(2017)HiperTMTheoretical Computer Science10.1016/j.tcs.2016.05.023688:C(86-102)Online publication date: 6-Aug-2017
https://dl.acm.org/doi/10.1016/j.tcs.2016.05.023
Zhang BRavindran BPalmieri R(2014)Distributed Transactional Contention Management as the Traveling Salesman ProblemStructural Information and Communication Complexity10.1007/978-3-319-09620-9_6(54-67)Online publication date: 2014
https://doi.org/10.1007/978-3-319-09620-9_6
Kuznetsov PRavi S(2012)WTTM 2011ACM SIGACT News10.1145/2160649.216067243:1(87-92)Online publication date: 7-Mar-2012
https://dl.acm.org/doi/10.1145/2160649.2160672
Show More Cited By

Index Terms

Brief announcement: on speculative replication of transactional systems
1. Software and its engineering
  1. Software organization and properties
    1. Extra-functional properties
      1. Software fault tolerance
    2. Software system structures
      1. Distributed systems organizing principles

Recommendations

Brief announcement: single-version permissive STM
PODC '10: Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing

We present a single-version STM that satisfies a practical notion of permissiveness: it never aborts read-only transactions, and it only aborts an update transaction due to another conflicting update transaction, thereby avoiding many spurious aborts. ...
Brief announcement: on enhancing concurrency in distributed transactional memory
PODC '10: Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing

Distributed transactional memory (TM) models based on globally-consistent contention management policies may abort many transactions that could potentially commit without violating correctness. To reduce unnecessary aborts and increase concurrency, we ...
Brief Announcement: Proust: A Design Space for Highly-Concurrent Transactional Data Structures
PODC '17: Proceedings of the ACM Symposium on Principles of Distributed Computing

Most STM systems are poorly equipped to support libraries of concurrent data structures. One reason is that they typically detect conflicts by tracking transactions' read sets and write sets, an approach that often leads to false conflicts. A second is ...

Comments

Information & Contributors

Information

Published In

SPAA '10: Proceedings of the twenty-second annual ACM symposium on Parallelism in algorithms and architectures

June 2010

378 pages

ISBN:9781450300797

DOI:10.1145/1810479

General Chairs:
Friedhelm Meyer auf der Heide
University of Paderborn, Germany
,
Cynthia Phillips
Sandia National Laboratories, USA

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 June 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Short-paper

Conference

SPAA 10

Sponsor:

SPAA 10: 22nd ACM Symposium on Parallelism in Algorithms and Architectures

June 13 - 15, 2010

Santorini, Thira, Greece

Acceptance Rates

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
147
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Hirve SPalmieri RRavindran B(2017)HiperTMTheoretical Computer Science10.1016/j.tcs.2016.05.023688:C(86-102)Online publication date: 6-Aug-2017
https://dl.acm.org/doi/10.1016/j.tcs.2016.05.023
Zhang BRavindran BPalmieri R(2014)Distributed Transactional Contention Management as the Traveling Salesman ProblemStructural Information and Communication Complexity10.1007/978-3-319-09620-9_6(54-67)Online publication date: 2014
https://doi.org/10.1007/978-3-319-09620-9_6
Kuznetsov PRavi S(2012)WTTM 2011ACM SIGACT News10.1145/2160649.216067243:1(87-92)Online publication date: 7-Mar-2012
https://dl.acm.org/doi/10.1145/2160649.2160672
Palmieri RQuaglia FRomano P(2010)AGGROProceedings of the 2010 Ninth IEEE International Symposium on Network Computing and Applications10.1109/NCA.2010.10(20-27)Online publication date: 15-Jul-2010
https://dl.acm.org/doi/10.1109/NCA.2010.10

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Brief announcement: single-version permissive STM

Brief announcement: on enhancing concurrency in distributed transactional memory

Brief Announcement: Proust: A Design Space for Highly-Concurrent Transactional Data Structures

Comments

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Other Metrics

Article Metrics

Other Metrics

Cited By

Login options

Full Access

PDF

eReader

Abstract

References

Cited By

Index Terms

Recommendations

Brief announcement: single-version permissive STM

Brief announcement: on enhancing concurrency in distributed transactional memory

Brief Announcement: Proust: A Design Space for Highly-Concurrent Transactional Data Structures

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Get Access

Login options

Full Access

View options

PDF

eReader

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations