Supervision : Pierre SENS Co-supervision : ARANTES Luciana
Algorithmes d'exclusion mutuelle : tolérance aux fautes et adaptation aux grilles
Cette thèse étudie les algorithmes distribués d'exclusion mutuelle dans le cadre des systèmes répartis à grande échelle. Elle s'intéresse plus particulièrement à la gestion des défaillances, ainsi qu'à la prise en compte des spécificités des topologies de type grille. Dans une première partie, nous proposons un nouvel algorithme d'exclusion mutuelle tolérant aux défaillances, basé sur l'algorithme de Naimi-Tréhel. Ce nouvel algorithme conserve la complexité originale en O(log(n)), limite l'utilisation de la diffusion et minimise le nombre des ré-émissions de requêtes en cas de défaillances. Une étude de performance, réalisées dans un cadre réel, a permis de montrer qu'il est particulièrement bien adapté aux systèmes répartis à grande échelle. Dans une deuxième partie, nous proposons un algorithme générique permettant de composer les algorithmes d'exclusion mutuelle de la littérature, pour prendre en compte la spécificité des grilles de calcul, à savoir : une grande différence de latence et de débit entre les réseaux locaux et le réseau inter-connectant les différentes grappes (clusters). Des expériences menées sur la grille expérimentale GRID'5000 ont, entre autre, permis de dégager des choix de composition en fonction du type d'application. Dans une autre étude de performances, nous étudions l'importance de la répartition des machines dans les différents clusters, sur l'efficacité de la composition.
Defence : 12/08/2008 - 14h - Site Passy-Kennedy - salle 549 Jury members : Roberto BALDONI, Professeur à l'Université Rome I (Rapporteur)
Frédéric DESPREZ, Directeur de recherche à l'INRIA (Rapporteur)
Marin BERTIER, Maître de conférences à l'INSA de Rennes
André SCHIPER, Professeur à l'École Polytechnique Fédérale de Lausane
Sebastien TIXEUIL, Professeur à l'Université Paris VI
Pierre SENS, Professeur à l'Université Paris VI
Luciana ARANTES, Maître de conférences à l'Université Paris VI
4 PhD students (Supervision / Co-supervision)
GHIGOFF Yoann : Conception de proxy applicatif pour le noyau Linux
OUDIN Rémi : Sytare, formally proving transiently powered systems
LANIEL Francis : MemOpLight : Vers une consolidation mémoire pour les conteneurs grâce à un retour applicatif.
GOUICEM Redha : Gestion coordonnée de ressources CPU et mémoire sur architectures multicoeurs.
COURTAUD Cédric : Caractérisation de la sensibilité aux interférences mémoire dans les systèmes temps-réels embarqués sur des plateformes multi-coeurs.
2019
LE FRIOUX Ludovic : Vers une parallélisation efficace de la résolution du problème de satisfaisabilité.
2017
BLIN Antoine : Vers une utilisation efficace des processeurs multi-cœurs dans des systèmes embarqués à criticités multiples.
2016
LORRILLERE Maxime : Caches collaboratifs noyau adaptés aux environnements virtualisés.
2014
LEJEUNE Jonathan : Algorithmique distribuée d'exclusion mutuelle : vers une gestion efficace des ressources.
2013
HU Ruijing : Algorithmes de dissémination épidémiques dans les réseaux à grande échelle : comparaison et adaptation aux topologie.
V. Vallade, L. Le Frioux, S. Baarir, J. Sopena, V. Ganesh, F. Kordon : “Community and LBD-Based Clause Sharing Policy for Parallel SAT Solving”, SAT 2020 - 23rd International Conference on Theory and Applications of Satisfiability Testing, vol. 12178, Lecture Notes in Computer Science, Alghero / Virtual, Italy, pp. 11-27 (2020)
D. Carver, R. Gouicem, J.‑P. Lozi, J. Sopena, B. Lepers, W. Zwaenepoel, N. Palix, J. Lawall, G. Muller : “Fork/Wait and Multicore Frequency Scaling: a Generational Clash”, 10th Workshop on Programming Languages and Operating Systems, Huntsville, Canada, pp. 53-59, (ACM Press) (2019)
F. Laniel, D. Carver, J. Sopena, F. Wajsbürt, J. Lejeune, M. Shapiro : “Highlighting the Container Memory Consolidation Problems in Linux”, NCA 2019 - 18th IEEE International Symposium on Network Computing and Applications, Cambridge, United States, pp. 1-4, (IEEE) (2019)
R. Gouicem, J. Sopena, J. Lawall, G. Muller, B. Lepers, W. Zwaenepoel, J.‑P. Lozi, N. Palix : “Understanding scheduler performance : a feature-based approach”, Compas 2019 - Conférence d’informatique en Parallélisme, Architecture et Système, Anglet, France (2019)
J. Bouron, S. Chevalley, B. Lepers, W. Zwaenepoel, R. Gouicem, J. Lawall, G. Muller, J. Sopena : “The Battle of the Schedulers: FreeBSD ULE vs. Linux CFS”, 2018 USENIX Annual Technical Conference, Boston, MA, United States (2018)
D. Carver, J. Sopena, S. Monnet : “ACDC : Advanced Consolidation for Dynamic Containers”, NCA 2017 - 16th IEEE International Symposium on Network Computing and Applications, Cambridge, MA, United States, pp. 1-8 (2017)
L. Le Frioux, S. Baarir, J. Sopena, F. Kordon : “PaInleSS: a Framework for Parallel SAT Solving.”, The 20th International Conference on Theory and Applications of Satisfiability Testing, vol. 10491, Lecture Notes in Computer Science, Melbourne, Australia, pp. 233-250, (Springer) (2017)
B. Lepers, W. Zwaenepoel, J.‑P. Lozi, N. Palix, R. Gouicem, J. Sopena, J. Lawall, G. Muller : “Towards Proving Optimistic Multicore Schedulers”, HotOS 2017 - 16th Workshop on Hot Topics in Operating Systems, Whistler, British Columbia, Canada, pp. 6 (2017)
M. Lorrillere, J. Poudroux, J. Sopena, S. Monnet : “Gestion dynamique du cache entre machines virtuelles”, Conférence d'Informatique en Parallélisme, Architecture et Système, Compas'2015, Lille, France, pp. 1-10 (2015)
Alejandro Z. Tomsic, P. Sens, J. Coelho Garcia, L. Arantes, J. Sopena : “2W-FD: A Failure Detector Algorithm with QoS”, IPDPS 2015 - The 29th IEEE International Parallel and Distributed Processing Symposium, Hyderabad, India, pp. 885-893, (IEEE) (2015)
M. Callau‑Zori, L. Arantes, J. Sopena, P. Sens : “MERCi-MIsS: Should I Turn off My Servers?”, Distributed Applications and Interoperable Systems, vol. 9038, Lecture Notes in Computer Science, Grenoble, France, pp. 16-29, (Springer International Publishing) (2015)
D. Serrano, S. Bouchenak, Y. Kouki, Th. Ledoux, J. Lejeune, J. Sopena, L. Arantes, P. Sens : “Towards QoS-Oriented SLA Guarantees for Online Cloud Services”, Proceedings of the 13th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGrid 2013), Delft, Netherlands, pp. 50-57 (2013)
L. Gidra, G. Thomas, J. Sopena, M. Shapiro : “A study of the scalability of stop-the-world garbage collectors on multicores”, ASPLOS 13 - Proceedings of the eighteenth international conference on Architectural support for programming languages and operating systems, Houston, United States, pp. 229-240, (ACM) (2013)
M. Lorrillere, J. Sopena, S. Monnet, P. Sens : “Vers un cache réparti adapté au cloud computing”, Conférence d'informatique en Parallélisme, Architecture et Système (ComPAS'2013) - 9e Conférence Française sur les Systèmes d'Exploitation (CFSE'13), Grenoble, France, pp. 1-12 (2013)
Y. Kouki, Th. Ledoux, D. Serrano, S. Bouchenak, J. Lejeune, L. Arantes, J. Sopena, P. Sens : “SLA et qualité de service pour le Cloud Computing”, Conférence d'informatique en Parallélisme, Architecture et Système, ComPAS 2013, Grenoble, France, pp. 1-11 (2013)
R. Hu, J. Sopena, L. Arantes, P. Sens, I. Demeure : “Efficient Dissemination Algorithm for Scale-Free Topologies”, ICPP'13 - 42th International Conference on Parallel Processing, Lyon, France, pp. 310-319, (IEEE Computer Society) (2013)
L. Millet, M. Lorrillere, L. Arantes, S. Gançarski, H. Naacke, J. Sopena : “Facing peak loads in a P2P transaction system”, Proceedings of the First Workshop on P2P and Dependability (P2PDEP'12), P2P-Dep '12, Sibiu, Romania, pp. 1-7, (ACM) (2012)
L. Arantes, J. Lejeune, M. Piffaretti, O. Marin, P. Sens, J. Sopena, Alysson N. Bessani, Vinicius V. Cogo, M. Correia, P. Costa, M. Pasin : “Vers une plate-forme MapReduce tolérant les fautes byzantines”, Revue des Sciences et Technologies de l'Information - Série TSI : Technique et Science Informatiques, vol. 31 (8-10), pp. 1079-1099, (Lavoisier) (2012)
L. Arantes, J. Lejeune, M. Piffaretti, O. Marin, P. Sens, J. Sopena, Alysson N. Bessani, Vinicius V. Cogo, M. Correia, P. Costa, M. Pasin, Fabrício A. B. Silva : “Étude d’une architecture MapReduce tolérant les fautes byzantines.”, Actes des 20éme Rencontres francophones du parallélisme (RENPAR'11), Saint-Malo, France (2011)
Th. Preud'Homme, J. Sopena, G. Thomas, B. Folliot : “BatchQueue: Efficient core-to-core communication for pipeline parallelism”, ASPLOS 2011 - Sixteenth International Conference on Architectural Support for Programming Languages and Operating Systems, Newport Beach, California, United States (2011)
2010
Th. Preud'Homme, J. Sopena, G. Thomas, B. Folliot : “BatchQueue: Fast and Memory-thrifty Core to Core Communication”, 22nd International Symposium on Computer Architecture and High Performance Computing, SBAC-PAD 2010, Petrópolis, Brazil, pp. 215-222, (The Institute of Electrical and Electronics Engineers, Inc) (2010)
Alysson N. Bessani, Vinicius V. Cogo, M. Correia, P. Costa, M. Pasin, Fabrício A. B. Silva, L. Arantes, O. Marin, P. Sens, J. Sopena : “Making Hadoop MapReduce Byzantine Fault-Tolerant”, Proceedings of the The 40th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN'2010) - Fast Abstract, Chicago, United States, (IEEE Computer Society) (2010)
J. Sopena, L. Arantes, F. Legond‑Aubry, P. Sens : “Synchronization protocols for sharing resources in grid environments”, chapter in Fundamentals of Grid Computing (CRC Numerical Analysis and Scientific Computing Series), 1 edition, (Chapman and Hall), (ISBN: 9781439803677) (2009)
S. Baarir, J. Sopena, F. Legond‑Aubry : “On the Formal Verification of a Generic Hierarchical Mutual Exclusion Algorithm”, 28th IFIP International Conference on Formal Techniques for Networked and Distributed Systems (FORTE'08 ), vol. 5048, Lecture Notes in Computer Science, Tokyo, Japan, pp. 99-115, (Springer-Verlag) (2008)
J. Sopena, L. Arantes, F. Legond‑Aubry, P. Sens : “The impact of clustering on token-based mutual exclusion algorithms”, Euro-Par 2008 Workshops - Parallel Processing, vol. 5168, Lecture Notes in Computer Science, Las Palmas de Gran Canaria, Spain, pp. 565-575, (Springer) (2008)