- Computer Science Laboratory

PANDEY Ayush

Doutorando at Sorbonne University
Team : DELYS
https://ayushpandey8439.github.io/
https://ayushpandey8439.github.io/

Direção de pesquisa : Mesaac MAKPANGOU
Co-supervisão£o : SHAPIRO Marc, SOPENA Julien, DUBOIS Swan

CALock : Topological Multi-Granularity Locking for Hierarchical data

Hierarchies serve as a fundamental structure across various disciplines, modelling hierarchical relationships in computer science, biology, social networks, and logistics. However, dynamic, concurrent updates in real-world systems necessitate synchronisation techniques to maintain data consistency.

This work explores a novel approach, called CALock, to synchronise operations on a hierarchy, based on a novel labelling scheme that facilitates multi-granularity locking. Our approach addresses both concurrent data access and structural modification. CALock exploits the hierarchical topology, via a new labelling scheme, to identify common ancestors of vertices. This enables a thread to efficiently identify an appropriate lock granule. Leveraging variable lock granularity optimizes operations across the hierarchy while ensuring consistency and performance.

We provide a detailed discussion of the CALock labeling and the locking algorithm, prove its properties, and evaluate it experimentally. On static hierarchies, CALock remains competitive with previous labeling schemes. When structural modifications change the hierarchy, CALock has better concurrency and throughput. Indeed, CALock improves throughput by up to 4.5×, and response time by up to 1.5× for workloads that contain structural modifications.


Defesas : 17/03/2025

Membros da banca :

David BROMBERG, Professeur, Université de Rennes [Rapporteur]
Pascal FELBER, Professeur, Université de Neuchâtel [Rapporteur]
Gaël THOMAS, Chercheur senior, INRIA
Sathya PERI, Professeur, IIT Hyderabad
Stefania DUMBRAVA, Maîtresse de conférences, ENSIIE & Télécom SudParis
Mesaac MAKPANGOU, Chargé de Recherche [HDR], INRIA
Julien SOPENA, Maître de Conférences, LIP6/Sorbonne Université
Marc SHAPIRO, Directeur de Recherche Émérite, INRIA & LIP6/Sorbonne Université
Swan DUBOIS, Maître de Conférences, LIP6/Sorbonne Université

Data de partida : 11/04/2025

Publicações 2022-2025