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.

4 PhD students (Supervision / Co-supervision)

• GHIGOFF Yoann : Conception de proxy applicatif pour le noyau Linux
• MAURICE Nathan : Irregular : Developement of efficient parallel algorithms for irregular application on heterogenous embedded systems for computer vision.
• OUDIN Nehalenniæ Lilith : SAT-solving: One clausebase to rule them all
• VALLADE Vincent : Sharing groups for parallel SAT solvers

8 PhD graduated 2013 - 2020

2005-2022 Publications

• 2022
  • N. Maurice, F. Lemaitre, J. Sopena, L. Lacassagne : “LSL3D: a run-based Connected Component Labeling algorithm for 3D volumes”, Binary is the new Black and White workshop @ IEEE ICIAP 2022, Lecce, Italy (2022)
• 2021
  • N. Maurice, J. Sopena, L. Lacassagne : “Un nouvel algorithme efficace de Split & Merge pour systèmes embarqués”, COMPAS 2021 - Conférence francophone d'informatique en Parallélisme, Architecture et Système, Lyon, France (2021)
  • Y. Ghigoff, J. Sopena, K. Lazri, A. Blin, G. Muller : “BMC: Accelerating Memcached using Safe In-kernel Caching and Pre-stack Processing”, NSDI'21 - 18^th USENIX Symposium on Networked Systems Design and Implementation, Virtual event, United States, pp. 487-501, (USENIX Association) (2021)
• 2020
  • F. Laniel, D. Carver, J. Sopena, F. Wajsbürt, J. Lejeune, M. Shapiro : “MemOpLight: Leveraging application feedback to improve container memory consolidation”, NCA 2020 - 19^th IEEE International Symposium on Network Computing and Applications, Cambridge / Virtual, United States, pp. 1-10 (2020)
  • R. Gouicem, D. Carver, J.‑P. Lozi, J. Sopena, B. Lepers, W. Zwaenepoel, N. Palix, J. Lawall, G. Muller : “Fewer Cores, More Hertz: Leveraging High-Frequency Cores in the OS Scheduler for Improved Application Performance”, 2020 USENIX Annual Technical Conference, Boston / Virtual, United States (2020)
  • 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 - 23^rd International Conference on Theory and Applications of Satisfiability Testing, vol. 12178, Lecture Notes in Computer Science, Alghero / Virtual, Italy, pp. 11-27 (2020)
  • G. Fraysse, J. Lejeune, J. Sopena, P. Sens : “A resource usage efficient distributed allocation algorithm for 5G Service Function Chains”, DAIS 2020 - 20^th IFIP WG 6.1 International Conference Distributed Applications and Interoperable Systems, vol. 12135, Lecture Notes in Computer Science, Valetta, Malta, pp. 169-185, (Springer) (2020)
  • V. Vallade, L. Le Frioux, S. Baarir, J. Sopena, F. Kordon : “On the Usefulness of Clause Strengthening in Parallel SAT Solving”, NFM 2020 - 12^th NASA Formal Methods Symposium, Moffett Field / Virtual, United States (2020)
  • B. Lepers, R. Gouicem, D. Carver, J.‑P. Lozi, N. Palix, M.‑V. Aponte, W. Zwaenepoel, J. Sopena, J. Lawall, G. Muller : “Provable Multicore Schedulers with Ipanema: Application to Work Conservation”, Eurosys 2020 - European Conference on Computer Systems, Heraklion / Virtual, Greece (2020)
  • Ah. Amamou, M. Camey, Ch. Cérin, J. Rivalan, J. Sopena : “Resources management for controlling dynamic loads in clouds environments. The Wolphin project experience”, (2020)
• 2019
  • C. Courtaud, J. Sopena, G. Muller, D. Gracia : “Improving Prediction Accuracy of Memory Interferences for Multicore Platforms”, RTSS 2019 - 40^th IEEE Real-Time Systems Symposium, Hong-Kong, China, (IEEE) (2019)
  • 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”, 10^th 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 - 18^th 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)
  • L. Le Frioux, S. Baarir, J. Sopena, F. Kordon : “Modular and Efficient Divide-and-Conquer SAT Solver on Top of the Painless Framework”, TACAS 2019 - 25^th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, vol. 11427, Lecture Notes in Computer Science, Prague, Czechia, pp. 135-151 (2019)
• 2018
  • 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)
  • G. Fraysse, I. Grida Ben Yahia, J. Lejeune, P. Sens, J. Sopena : “Towards multi-SDN services: Dangers of concurrent resource allocation from multiple providers”, 21^st Conference on Innovation in Clouds, Internet and Networks (ICIN 2018), Paris, France (2018)
• 2017
  • D. Carver, J. Sopena, S. Monnet : “ACDC : Advanced Consolidation for Dynamic Containers”, NCA 2017 - 16^th 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 20^th International Conference on Theory and Applications of Satisfiability Testing, vol. 10491, Lecture Notes in Computer Science, Melbourne, Australia, pp. 233-250, (Springer) (2017)
  • R. Gouicem, J. Sopena, J. Lawall, G. Muller, B. Lepers, W. Zwaenepoel, J.‑P. Lozi, N. Palix : “Ipanema : un langage dédié pour le développement d’ordonnanceurs multi-coeur sûrs”, Compas 2017: Conférence d’informatique en Parallélisme, Architecture et Système, Sophia Antipolis, France (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 - 16^th Workshop on Hot Topics in Operating Systems, Whistler, British Columbia, Canada, pp. 6 (2017)
• 2016
  • A. Blin, C. Courtaud, J. Sopena, J. Lawall, G. Muller : “Maximizing Parallelism without Exploding Deadlines in a Mixed Criticality Embedded System”, 28^th EUROMICRO Conference on Real-Time Systems (ECRTS'16), Toulouse, France (2016)
  • A. Blin, C. Courtaud, J. Sopena, J. Lawall, G. Muller : “Understanding the Memory Consumption of the MiBench Embedded Benchmark”, Netys, Marakech, Morocco (2016)
  • A. Blin, C. Courtaud, J. Sopena, J. Lawall, G. Muller : “Maximizing Parallelism without Exploding Deadlines in a Mixed Criticality Embedded System”, (2016)
• 2015
  • J. Lejeune, L. Arantes, J. Sopena, P. Sens : “Reducing synchronization cost in distributed multi-resource allocation problem”, ICPP 2015 - 44^th International Conference on Parallel Processing, Beijing, China, pp. 540-549, (IEEE) (2015)
  • J. Lejeune, L. Arantes, J. Sopena, P. Sens : “A fair starvation-free prioritized mutual exclusion algorithm for distributed systems”, Journal of Parallel and Distributed Computing, vol. 83, pp. 13-29, (Elsevier) (2015)
  • 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)
  • M. Lorrillere, J. Sopena, S. Monnet, P. Sens : “Puma: pooling unused memory in virtual machines for I/O intensive applications”, SYSTOR'15 - 8^th ACM International Systems and Storage Conference, Haifa, Israel, pp. 1:1-1:11, (ACM) (2015)
  • Alejandro Z. Tomsic, P. Sens, J. Coelho Garcia, L. Arantes, J. Sopena : “2W-FD: A Failure Detector Algorithm with QoS”, IPDPS 2015 - The 29^th IEEE International Parallel and Distributed Processing Symposium, Hyderabad, India, pp. 885-893, (IEEE) (2015)
  • L. Gidra, G. Thomas, J. Sopena, M. Shapiro, Nh. Nguyen : “NumaGiC: a Garbage Collector for Big Data on Big NUMA Machines”, Architectural Support for Programming Languages and Operating Systems (ASPLOS), Istanbul, Turkey, pp. 661-673, (ACM) (2015)
  • J. Lejeune, L. Arantes, J. Sopena, P. Sens : “Reducing synchronization cost in distributed multi-resource allocation problem”, (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)
  • M. Lorrillere, J. Sopena, S. Monnet, P. Sens : “Conception et évaluation d’un système de cache réparti adapté aux environnements virtualisés”, Revue des Sciences et Technologies de l'Information - Série TSI : Technique et Science Informatiques, vol. 34 (1-2), pp. 22, (Lavoisier) (2015)
• 2014
  • A. Blin, J. Sopena, G. Muller, Y. Laarouchi : “Contrôle de la bande passante mémoire dans les systèmes à criticité mixte par sous-réservation”, ComPAS 2014 - Conférence d'informatique en Parallélisme, Architecture et Systeme, Neuchâtel, Switzerland (2014)
  • M. Lorrillere, J. Sopena, S. Monnet, P. Sens : “PUMA: Un cache distant pour mutualiser la mémoire inutilisée des machines virtuelles”, ComPAS'2014 : Conférence d'informatique en Parallélisme, Architecture et Système, Neuchâtel, Switzerland, pp. 1-12 (2014)
• 2013
  • L. Arantes, J. Sopena : “Easily rendering token-ring algorithms of distributed and parallel applications fault tolerant”, 25^th International Symposium on Computer Architecture and High Performance Computing (SBAC'13), Porto de Galinhas, Brazil, pp. 206-213, (IEEE) (2013)
  • A. Faure De Pebeyre, F. Tarissan, J. Sopena : “Évaluation du modèle évolutif par arête-markovienne pour reproduire la dynamique des réseaux mobiles”, 4^e Journées Modèles et l’Analyse des Réseaux : Approches Mathématiques et Informatique (MARAMI'13), Saint-Etienne, France, pp. 1-12 (2013)
  • A. Beslic, R. Bendraou, J. Sopena, J.‑Y. Rigolet : “Towards a solution avoiding Vendor Lock-in to enable Migration Between Cloud Platforms”, MDHPCL 2013 - 2^nd International Workshop on Model-Driven Engineering for High Performance and CLoud computing, Miami, Florida, United States, pp. 5-14 (2013)
  • L. Arantes, J. Sopena : “Easily rendering token-ring algorithms of distributed and parallel applications fault tolerant”, 23 pages (2013)
  • 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 13^th 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) - 9^e 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)
  • A. Faure De Pebeyre, F. Tarissan, J. Sopena : “On the relevance of the edge-Markovian evolving graph model for real mobile networks”, Proceedings of the IFIP Wireless Days conference, Valence, Spain, pp. 1-6, (IEEE) (2013)
  • J. Lejeune, L. Arantes, J. Sopena, P. Sens : “A prioritized distributed mutual exclusion algorithm balancing priority inversions and response time”, ICPP'13 - 42^th International Conference on Parallel Processing, Lyon, France, pp. 290-299, (IEEE Computer Society) (2013)
  • R. Hu, J. Sopena, L. Arantes, P. Sens, I. Demeure : “Efficient Dissemination Algorithm for Scale-Free Topologies”, ICPP'13 - 42^th International Conference on Parallel Processing, Lyon, France, pp. 310-319, (IEEE Computer Society) (2013)
  • R. Hu, J. Sopena, L. Arantes, P. Sens, I. Demeure : “Comparaisons équitables des algorithmes de gossip sur les topologies aléatoires à grande-échelle”, ComPAS'2013 - 9^e Conférence Française sur les Systèmes d'Exploitation (CFSE'13), Chapitre français de l'ACM-SIGOPS, GDR ARP, Grenoble, France (2013)
  • J. Lejeune, L. Arantes, J. Sopena, P. Sens : “Un algorithme équitable d’exclusion mutuelle distribuée avec priorité”, 9^e Conférence Française sur les Systèmes d'Exploitation (CFSE'13), Chapitre français de l'ACM-SIGOPS, GDR ARP, Grenoble, France (2013)
• 2012
  • Th. Preud'Homme, J. Sopena, G. Thomas, B. Folliot : “An improvement of OpenMP pipeline parallelism with the BatchQueue algorithm”, 18^th IEEE International Conference on Parallel and Distributed Systems (ICPADS'12), Singapore, Singapore, pp. 348-355, (IEEE Computer Society Press) (2012)
  • R. Hu, J. Sopena, L. Arantes, P. Sens, I. Demeure : “Fair Comparison of Gossip Algorithms over Large-Scale Random Topologies”, Reliable Distributed Systems (SRDS), 2012 IEEE 31^st Symposium on, Irvine, California, United States, pp. 331-340, (IEEE Computer Society Press) (2012)
  • 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)
  • J. Lejeune, L. Arantes, J. Sopena, P. Sens : “Service Level Agreement for Distributed Mutual Exclusion in Cloud Computing”, 12^th IEEE/ACM International Conference on Cluster, Cloud and Grid Computing (CCGRID'12), Ottawa, Canada, pp. 180-187, (IEEE) (2012)
  • 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”, (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)
• 2011
  • L. Gidra, G. Thomas, J. Sopena, M. Shapiro : “Assessing the Scalability of Garbage Collectors on Many Cores”, Operating Systems Review, vol. 45 (3), Best papers from PLOS'11, pp. 15-19, (Association for Computing Machinery) (2011)
  • L. Gidra, G. Thomas, J. Sopena, M. Shapiro : “Assessing the Scalability of Garbage Collectors on Many Cores”, PLOS '11 - 6^th Workshop on Programming Languages and Operating Systems, Cascais, Portugal, pp. 7:1-7:5, (ACM) (2011)
  • Th. Preud'Homme, J. Sopena, G. Thomas, B. Folliot : “BatchQueue : file producteur / consommateur optimisée pour les multi-cœurs”, 8^e Conférence Française sur les Systèmes d'Exploitation (CFSE'11), Saint-Malo, France, pp. 1-12 (2011)
  • 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”, 22^nd 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 40^th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN'2010) - Fast Abstract, Chicago, United States, (IEEE Computer Society) (2010)
• 2009
  • J. Sopena, L. Arantes, F. Legond‑Aubry, P. Sens : “Building Effective Mutual Exclusion Services for Grids”, Journal of Supercomputing, vol. 49 (1), pp. 84-107, (Springer Verlag) (2009)
  • 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)
  • J. Sopena, S. Baarir, F. Legond‑Aubry : “Vérification formelle d’un algorithme générique et hiérarchique d’exclusion mutuelle”, Revue des Sciences et Technologies de l'Information - Série TSI : Technique et Science Informatiques, vol. 28 (9), pp. 1085-1105, (Lavoisier) (2009)
• 2008
  • J. Sopena : “Algorithmes d’exclusion mutuelle : tolérance aux fautes et adaptation aux grilles”, thesis, defence 12/08/2008, supervision Sens, Pierre, rapporteurs : ARANTES Luciana (2008)
  • S. Baarir, J. Sopena, F. Legond‑Aubry : “On the Formal Verification of a Generic Hierarchical Mutual Exclusion Algorithm”, 28^th 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, F. Legond‑Aubry, L. Arantes, P. Sens : “Composition d’algorithmes d’exclusion mutuelle pour les grilles de calcul.”, 6^e Conférence Française sur les Systèmes d'Exploitation (CFSE'08), Chapitre français de l'ACM-SIGOPS, GDR ARP, Fribourg, Switzerland (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)
• 2007
  • J. Sopena, F. Legond‑Aubry, L. Arantes, P. Sens : “A Composition Approach to Mutual Exclusion Algorithms for Grid Applications”, The 36^th International Conference on Parallel Processing (ICPP07), XiAn, China, pp. 65-65, (IEEE Computer Society) (2007)
• 2006
  • J. Sopena, L. Arantes, P. Sens : “Performance evaluation of a fair fault-tolerant mutual exclusion algorithm”, The 25^th IEEE Symposium on Reliable Distributed Systems (SRDS 2006), Leeds, United Kingdom, pp. 225-234, (IEEE Computer Society) (2006)
  • J. Sopena, L. Arantes, P. Sens : “Un algorithme équitable d’exclusion mutuelle tolérant les fautes”, 5éme Conférence Française sur les Systèmes d'Exploitation (CFSE'06), Perpignan, France, pp. 97-107 (2006)
• 2005
  • J. Sopena, L. Arantes, M. Bertier, P. Sens : “A fault-tolerant token-based mutual exclusion algorithm using a dynamic tree”, Euro-Par 2005 - 11^th European Conference on Parallel and Distributed Computing, vol. 3648, Lecture Notes in Computer Science, Lisboa, Portugal, pp. 654-663, (Springer) (2005)