Distributed computing; Time series; Distributed graphs; Temporal graphs; Data analytics; Lock-free workers
Résumé :
[en] 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.
Disciplines :
Sciences informatiques
Auteur, co-auteur :
Fouquet, Francois; DataThings
HARTMANN, Thomas ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT)
Mosser, Sébastien; Université Côte d'Azur, I3S
CORDY, Maxime ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT)
Co-auteurs externes :
yes
Langue du document :
Anglais
Titre :
Enabling lock-free concurrent workers over temporal graphs composed of multiple time-series
Date de publication/diffusion :
avril 2018
Nom de la manifestation :
33rd Annual ACM Symposium on Applied Computing (SAC'18)
Organisateur de la manifestation :
Université de Pau et des Pays de l'Adour (UPPA)
Lieu de la manifestation :
Pau, France
Date de la manifestation :
09-04-2018 to 13-04-2018
Manifestation à portée :
International
Titre de l'ouvrage principal :
33rd Annual ACM Symposium on Applied Computing (SAC'18)
Peer reviewed :
Peer reviewed
Focus Area :
Computational Sciences
Organisme subsidiant :
CNRS (INS2I PEPS JCJC program) through the M4S project European Commission (FEDER IDEES/CO-INNOVATION) Creos Luxembourg S.A through the UL/SnT partnership programme
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.
A. Adya. Weak Consistency: A Generalized Theory and Optimistic Implementations for Distributed Transactions. PhD thesis, Cambridge, MA, USA, 1999. AAI0800775.
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.
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.
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.
J. Dean and S. Ghemawat. Mapreduce: Simplified data processing on large clusters. Commun. ACM, 51(1):107-113, Jan. 2008.
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.
C. Fidge. Logical time in distributed computing systems. Computer, 24(8):28-33, 1991.
W. Han, Y. Miao, K. Li, M. Wu, F. Yang, L. Zhou, V. Prabhakaran, W. Chen, and E. Chen. Chronos: A graph 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.
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.
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.
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.
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.
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.
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.
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.
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.
G. Malewicz, M. H. Austern, A. J. Bik, J. C. Dehnert, I. Horn, N. Leiser, and G. Czajkowski. Pregel:Asystem 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.
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.
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.
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.
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.
M. Raynal and M. Singhal. Logical time: Capturing causality in distributed systems. Computer, 29(2):49-56, 1996.
M. Shapiro and N. Preguiça. Designing a commutative replicated data type. ArXiv e-prints, Oct. 2007.
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.
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.
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.
L. G. Valiant. A bridging model for parallel computation. Commun. ACM, 33(8):103-111, Aug. 1990.
