research-article

Enabling lock-free concurrent workers over temporal graphs composed of multiple time-series

Authors:

Francois Fouquet,

Thomas Hartmann,

Sébastien Mosser,

Maxime CordyAuthors Info & Claims

SAC '18: Proceedings of the 33rd Annual ACM Symposium on Applied Computing

Pages 1054 - 1061

https://doi.org/10.1145/3167132.3167255

Published: 09 April 2018 Publication History

Abstract

Time series are commonly used to store temporal data, e.g., sensor measurements. However, when it comes to complex analytics and learning tasks, these measurements have to be combined with structural context data. Temporal graphs, connecting multiple time-series, have proven to be very suitable to organize such data and ultimately empower analytic algorithms. Computationally intensive tasks often need to be distributed and parallelized among different workers. For tasks that cannot be split into independent parts, several workers have to concurrently read and update these shared temporal graphs. This leads to inconsistency risks, especially in the case of frequent updates. Distributed locks can mitigate these risks but come with a very high-performance cost. In this paper, we present a lock-free approach allowing to concurrently modify temporal graphs. Our approach is based on a composition operator able to do online reconciliation of concurrent modifications of temporal graphs. We evaluate the efficiency and scalability of our approach compared to lock-based approaches.

References

[1]

T. Abdessalem, M. L. Ba, and P. Senellart. A probabilistic xml merging tool. In Proceedings of the 14th International Conference on Extending Database Technology, EDBT/ICDT '11, pages 538--541, New York, NY, USA, 2011. ACM.

Digital Library

[2]

A Adya. Weak Consistency: A Generalized Theory and Optimistic Implementations for Distributed Transactions. PhD thesis, Cambridge, MA, USA, 1999. AAI0800775.

Digital Library

[3]

R. Al-Ekram, A. Adma, and O. Baysal. diffx: An algorithm to detect changes in multi-version xml documents. In Proceedings of the 2005 Conference of the Centre for Advanced Studies on Collaborative Research, CASCON '05, pages 1--11. IBM Press, 2005.

Digital Library

[4]

X. Blanc, M.-P. Gervais, and P. Sriplakich. Model Bus: Towards the Interoperability of Modelling Tools, pages 17--32. Springer Berlin Heidelberg, Berlin, Heidelberg, 2005.

Digital Library

[5]

X. Blanc, P. Sriplakich, and M. Gervais. Modeling services and web services: Application of modelbus. In Proceedings of the International Conference on Software Engineering Research and Practice, SERP 2005, Las Vegas, Nevada, USA, June 27-29, 2005, Volume 2, pages 557--563, 2005.

[6]

J. Dean and S. Ghemawat. Mapreduce: Simplified data processing on large clusters. Commun. ACM, 51(1):107--113, Jan. 2008.

Digital Library

[7]

D. G. Ferro, F. Junqueira, I. Kelly, B. Reed, and M. Yabandeh. Omid: Lock-free transactional support for distributed data stores. In 2014 IEEE 30th International Conference on Data Engineering, pages 676--687, March 2014.

[8]

C. Fidge. Logical time in distributed computing systems. Computer, 24(8):28--33, 1991.

Digital Library

[9]

W. Han, Y. Miao, K. Li, M. Wu, F. Yang, L. Zhou, V. Prabhakaran, W. Chen, and E. Chen. Chronos: Agraph engine for temporal graph analysis. In Proceedings of the Ninth European Conference on Computer Systems, EuroSys '14, pages 1:1--1:14, New York, NY, USA, 2014. ACM.

Digital Library

[10]

T. Hartmann, F. Fouquet, M. Jimenez, R. Rouvoy, and Y. L. Traon. Analyzing complex data in motion at scale with temporal graphs. In The 29th International Conference on Software Engineering and Knowledge Engineering, July 5-7, 2017., pages 596--601, 2017.

[11]

T. Hartmann, A. Moawad, F. Fouquet, G. Nain, J. Klein, Y. Le Traon, and J.-M. Jezequel. Model-Driven Analytics: Connecting Data, Domain Knowledge, and Learning. ArXiv e-prints, Apr. 2017.

[12]

K. Imae and N. Hayashibara. Chainvoxel: A data structure for scalable distributed collaborative editing for 3d models. In 2016 IEEE 14th Intl Conf on Dependable, Autonomic and Secure Computing, 14th Intl Conf on Pervasive Intelligence and Computing, 2nd Intl Conf on Big Data Intelligence and Computing and Cyber Science and Technology Congress(DASC/PiCom/DataCom/CyberSciTech), pages 344--351, Aug 2016.

[13]

A. P. Iyer, L. E. Li, T. Das, and I. Stoica. Time-evolving graph processing at scale. In Proceedings of the Fourth International Workshop on Graph Data Management Experiences and Systems, GRADES '16, pages 5:1--5:6, New York, NY, USA, 2016. ACM.

Digital Library

[14]

E. Levy, H. F. Korth, and A. Silberschatz. An optimistic commit protocol for distributed transaction management. In Proceedings of the 1991 ACM SIGMOD International Conference on Management of Data, SIGMOD '91, pages 88--97, New York, NY, USA, 1991. ACM.

Digital Library

[15]

T. Lindholm. A three-way merge for xml documents. In Proceedings of the 2004 ACM Symposium on Document Engineering, DocEng '04, pages 1--10, New York, NY, USA, 2004. ACM.

Digital Library

[16]

Y. Low, D. Bickson, J. Gonzalez, C. Guestrin, A. Kyrola, and J. M. Hellerstein. Distributed graphlab: A framework for machine learning and data mining in the cloud. Proc. VLDB Endow., 5(8):716--727, Apr. 2012.

Digital Library

[17]

Y. Low, J. Gonzalez, A. Kyrola, D. Bickson, C. Guestrin, and J. M. Hellerstein. GraphLab: A New Framework for Parallel Machine Learning. ArXiv e-prints, June 2010.

[18]

G. Malewicz, M. H. Austern, A. J. Bik, J. C. Dehnert, I. Horn, N. Leiser, and G. Czajkowski. Pregel: A system for large-scale graph processing. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, SIGMOD '10, pages 135--146, New York, NY, USA, 2010. ACM.

Digital Library

[19]

A. Moawad, T. Hartmann, F. Fouquet, G. Nain, J. Klein, and Y. L. Traon. Beyond discrete modeling: A continuous and efficient model for iot. In 18th ACM/IEEE International Conference on Model Driven Engineering Languages and Systems, MoDELS 2015, Ottawa, ON, Canada, September 30 - October 2, 2015, pages 90--99, 2015.

[20]

C. Mohan and B. Lindsay. Efficient commit protocols for the tree of processes model of distributed transactions. In Proceedings of the Second Annual ACM Symposium on Principles of Distributed Computing, PODC '83, pages 76--88, New York, NY, USA, 1983. ACM.

Digital Library

[21]

W. Ng. Repairing Inconsistent Merged XML Data. In V. Marík, W. Retschitzegger, and O. Stepánková, editors, Database and Expert Systems Applications, 14th International Conference, DEXA 2003, Prague, Czech Republic, September 1-5, 2003, Proceedings, volume 2736 of Lecture Notes in Computer Science, pages 244--255. Springer, 2003.

[22]

D. Ongaro and J. Ousterhout. In search of an understandable consensus algorithm. In Proceedings of the 2014 USENIX Conference on USENIX Annual Technical Conference, USENIX ATC'14, pages 305--320, Berkeley, CA, USA, 2014. USENIX Association.

Digital Library

[23]

M. Raynal and M. Singhal. Logical time: Capturing causality in distributed systems. Computer, 29(2):49--56, 1996.

Digital Library

[24]

M. Shapiro and N. Preguiça. Designing a commutative replicated data type. ArXiv e-prints, Oct. 2007.

[25]

M. Shapiro, N. Preguiça, C. Baquero, and M. Zawirski. Conflict-free replicated data types. In Proceedings of the 13th International Conference on Stabilization, Safety, and Security of Distributed Systems, SSS'11, pages 386--400, Berlin, Heidelberg, 2011. Springer-Verlag.

[26]

C. Thao and E. V. Munson. Using versioned tree data structure, change detection and node identity for three-way xml merging. In Proceedings of the 10th ACM Symposium on Document Engineering, DocEng '10, pages 77--86, New York, NY, USA, 2010. ACM.

Digital Library

[27]

A. Thomson, T. Diamond, S.-C. Weng, K. Ren, P. Shao, and D. J. Abadi. Calvin: Fast distributed transactions for partitioned database systems. In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data, SIGMOD '12, pages 1--12, New York, NY, USA, 2012. ACM.

Digital Library

[28]

L. G. Valiant. A bridging model for parallel computation. Commun. ACM, 33(8):103--111, Aug. 1990.

Digital Library

Cited By

Halawa HRipeanu MKalavri VYakovets N(2021)Position paperProceedings of the 4th ACM SIGMOD Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA)10.1145/3461837.3464514(1-12)Online publication date: 20-Jun-2021
https://dl.acm.org/doi/10.1145/3461837.3464514
Hartmann TFouquet FMoawad ARouvoy RLe Traon Y(2019) GreyCatInformation Systems10.1016/j.is.2019.03.00483:C(101-117)Online publication date: 1-Jul-2019
https://dl.acm.org/doi/10.1016/j.is.2019.03.004

Index Terms

Enabling lock-free concurrent workers over temporal graphs composed of multiple time-series
1. Information systems
  1. Data management systems
    1. Database design and models
      1. Graph-based database models
    2. Database management system engines
      1. Stream management

Recommendations

Coloring temporal graphs
Abstract
A temporal graph is a pair ( G , λ ) where G is a simple graph and λ is a function assigning to each edge time labels telling at which snapshots each edge is active. As recently defined by Mertzios, Molter and Zamaraev (2021), a ...
Transactional lock-free execution of lock-based programs
Special Issue: Proceedings of the 10th annual conference on Architectural Support for Programming Languages and Operating Systems

This paper is motivated by the difficulty in writing correct high-performance programs. Writing shared-memory multi-threaded programs imposes a complex trade-off between programming ease and performance, largely due to subtleties in coordinating access ...
Are lock-free concurrent algorithms practically wait-free?
STOC '14: Proceedings of the forty-sixth annual ACM symposium on Theory of computing

Lock-free concurrent algorithms guarantee that some concurrent operation will always make progress in a finite number of steps. Yet programmers prefer to treat concurrent code as if it were wait-free, guaranteeing that all operations always make ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SAC '18: Proceedings of the 33rd Annual ACM Symposium on Applied Computing

April 2018

2327 pages

ISBN:9781450351911

DOI:10.1145/3167132

Conference Chairs:
Hisham M. Haddad
Kennesaw State University
,
Roger L. Wainwright
University of Tulsa
,
Richard Chbeir
University of Pau & Pays Adour, France

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGAPP: ACM Special Interest Group on Applied Computing

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 April 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

European Commission
CNRS

Conference

SAC 2018

Sponsor:

SIGAPP

SAC 2018: Symposium on Applied Computing

April 9 - 13, 2018

Pau, France

Acceptance Rates

Overall Acceptance Rate 1,650 of 6,669 submissions, 25%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
65
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)1

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Halawa HRipeanu MKalavri VYakovets N(2021)Position paperProceedings of the 4th ACM SIGMOD Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA)10.1145/3461837.3464514(1-12)Online publication date: 20-Jun-2021
https://dl.acm.org/doi/10.1145/3461837.3464514
Hartmann TFouquet FMoawad ARouvoy RLe Traon Y(2019) GreyCatInformation Systems10.1016/j.is.2019.03.00483:C(101-117)Online publication date: 1-Jul-2019
https://dl.acm.org/doi/10.1016/j.is.2019.03.004

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents