Direction de recherche : Marc SHAPIRO

Protocoles efficaces pour le consensus généralisé et la réplication partielle

Un objet accédé par plusieurs processus est dit partagé. Dans un système réparti, un tel objet est généralement répliqué, c'est-à-dire que l'on place des copies physiques de l'objet logique sur plusieurs machines. La réplication permet d'accroître la disponibilité et les performances ; cette technique joue un rôle primordial dans les systèmes d'information modernes. Toutefois, si l'objet subit des écritures, la réplication pose le problème de la cohérence des répliques. Le thème principal de cette thèse est la gestion de la cohérence en présence d'accès concurrents, de dysfonctionnement du réseau, ou de défaillances matérielles et logicielles. Pour cela, la primitive d'ordonnancement des opérations, dit consensus (résolu entre autres par l'algorithme Paxos), occupe une place centrale. La latence du consensus détermine donc les performances du système dans son ensemble ; son amélioration constitue un sujet de choix de la recherche en algorithmique répartie. Des travaux récents généralisent le consensus en prenant en compte l'existence de classes d'équivalence d'ordonnancement, ce qui permet de diminuer la latence lorsque les opérations sont, soit commutatives, soit pré-ordonnées par le réseau. Ainsi, l'extension de Paxos au consensus généralisé, dénommé Generalized Paxos, n'ordonne pas les opérations dans ces cas-là. Cependant, lorsqu'une collision a lieu, c'est-à-dire que deux répliques reçoivent des opérations non-commutatives dans des ordres différents, Generalized Paxos entre dans une phase de recouvrement, dont la latence est bien supérieure à celle de Paxos. Dans la première partie de la thèse nous présentons le protocole FGGC de consensus généralisé que nous avons conçu pour minimiser le coût du recouvrement. Profitant pleinement de la liberté d'ordonnancement permise par le consensus généralisé, FGGC présente une latence optimale (deux étapes de communication si les processus reçoivent les opérations non-commutatives dans le même ordre, et trois autrement) au cours d'une exécution sans faute. De plus, FGGC est optimal par rapport aux fautes : il tolère $f

Un docteur (2014) à Sorbonne Université

Publications 2006-2021

• 2021
  • I. Toumlilt, P. Sutra, M. Shapiro : “Highly-available and consistent group collaboration at the edge with colony”, Middleware '21: Proceedings of the 22^nd International Middleware Conference, Québec / Virtual, Canada, pp. 336–351, (ACM) (2021)
• 2019
  • M. Shapiro, P. Sutra : “Database Consistency Models”, chapter in Encyclopedia of Big Data Technologies, (Springer), (ISBN: 978-3-319-63962-8) (2019)
• 2014
  • M. Saeida Ardekani, P. Sutra, M. Shapiro : “G-DUR: A Middleware for Assembling, Analyzing, and Improving Transactional Protocols”, Middleware, Bordeaux, France, pp. 12, (IEEE) (2014)
  • M. Shapiro, M. Saeida Ardekani, P. Sutra : “Exploring the spectrum of strongly-consistent transactional protocols”, Workshop on Large-Scale Distributed Systems and Middleware (LADIS), Workshop on Large-Scale Distributed Systems and Middleware (LADIS), Cambridge, United Kingdom (2014)
• 2013
  • M. Saeida Ardekani, P. Sutra, M. Shapiro : “Non-Monotonic Snapshot Isolation: scalable and strong consistency for geo-replicated transactional systems”, SRDS 2013 -IEEE 32^nd International Symposium on Reliable Distributed Systems, Braga, Portugal, pp. 163-172, (IEEE Computer Society) (2013)
  • M. Saeida Ardekani, P. Sutra, M. Shapiro, N. Preguiça : “On the Scalability of Snapshot Isolation”, Euro-Par 2013 - 19^th International Conference Parallel Processing, vol. 8097, Lecture Notes in Computer Science, Aachen, Germany, pp. 369-381, (Springer) (2013)
  • M. Saeida Ardekani, P. Sutra, N. Preguiça, M. Shapiro : “Non-Monotonic Snapshot Isolation”, 45 pages (2013)
• 2012
  • M. Saeida Ardekani, M. Zawirski, P. Sutra, M. Shapiro : “The Space Complexity of Transactional Interactive Reads”, HotCDP '12 - 1^st International Workshop on Hot Topics in Cloud Data Processing, Bern, Switzerland, (ACM) (2012)
• 2011
  • P. Sutra, M. Shapiro : “Fast Genuine Generalized Consensus”, SRDS 2011 - 30^th IEEE Symposium on Reliable Distributed Systems, Madrid, Spain, pp. 255-264, (IEEE Computer Society) (2011)
  • M. Saeida Ardekani, P. Sutra, M. Shapiro : “The Impossibility of Ensuring Snapshot Isolation in Genuine Replicated STMs”, WTTM 2011: third workshop on the theory of transactional memory, Roma, Italy (2011)
  • P. Sutra, M. Shapiro : “Résolution efficace du consensus généralisé dans les systèmes répartis par passage de messages”, ALGOTEL 2011 - 13^es Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications, Cap Estérel, France (2011)
  • Z. Bouzid, P. Sutra, C. Travers : “Anonymous Agreement: The Janus Algorithm”, OPODIS'11 - 15^th International Conference On Principles Of Distributed Systems, vol. 7109, Lecture Notes in Computer Science, Toulouse, France, pp. 175-190, (Springer) (2011)
  • J. Michaux, X. Blanc, P. Sutra, M. Shapiro : “A Semantically Rich Approach for Collaborative Model Edition”, Symp. on Applied Computing (SAC), vol. 26, Taichung, Taiwan, Province of China, pp. 1470-1475, (Assoc. for Computing Machinery) (2011)
• 2010
  • P. Sutra : “Protocoles efficaces pour le consensus généralisé et la réplication partielle”, soutenance de thèse, soutenance 08/11/2010, direction de recherche Shapiro, Marc (2010)
  • N. Schiper, P. Sutra, F. Pedone : “P-Store : Genuine Partial Replication in Wide Area Networks”, International Symposium on Reliable Distributed Systems (SRDS), New Delhi, India, pp. 214-224, (IEEE) (2010)
• 2009
  • N. Schiper, P. Sutra, F. Pedone : “Genuine versus Non-Genuine Atomic Multicast Protocols for Wide Area Networks : an Empirical Study”, The 28^th IEEE Symposium on Reliable Distributed Systems (SRDS 2009), Niagara Falls, NY, Canada, pp. 166-175, (IEEE) (2009)
  • L. Benmouffok, J.‑M. Busca, J. Marquès, M. Shapiro, P. Sutra, G. Tsoukalas : “Telex: A Semantic Platform for Cooperative Application Development”, Conférence Française sur les Systèmes d'Exploitation (CFSE), Toulouse, France (2009)
• 2008
  • P. Sutra, M. Shapiro : “Fault-Tolerant Partial Replication in Large-Scale Database Systems”, europar, Las Palmas de Gran Canaria, Spain, pp. 404-413 (2008)
  • P. Sutra, M. Shapiro : “Fault-Tolerant Partial Replication in Large-Scale Database Systems”, 25 pages (2008)
  • L. Benmouffok, J.‑M. Busca, J. Manuel Marquès, M. Shapiro, P. Sutra, G. Tsoukalas : “Telex: Principled System Support for Write-Sharing in Collaborative Applications”, 31 pages (2008)
• 2007
  • C. Ignat, G. Oster, P. Molli, M. Cart, J. Ferrié, A.‑M. Kermarrec, P. Sutra, M. Shapiro, L. Benmouffok, J.‑M. Busca, R. Guerraoui : “A Comparison of Optimistic Approaches to Collaborative Editing of Wiki Pages”, Proceedings of the The 3^rd International Conference on Collaborative Computing: Networking, Applications and Worksharin - CollaborateCom, White Plains, NY, United States, pp. 474-483, (IEEE Computer Society) (2007)
  • P. Sutra, J. Barreto, M. Shapiro : “Decentralised Commitment for Optimistic Semantic Replication”, International Conference on Cooperative Information Systems (CoopIS), vol. 4803, Lecture Notes in Computer Science, Vilamoura, Algarve, Portugal, pp. 318-335, (Springer) (2007)
  • P. Sutra, M. Shapiro : “Comparing Optimistic Database Replication Techniques”, Bases de Données Avancées (BDA), Marseille, France (2007)
  • C. Ignat, G. Oster, P. Molli, M. Cart, J. Ferrié, A.‑M. Kermarrec, P. Sutra, M. Shapiro, L. Benmouffok, J.‑M. Busca, R. Guerraoui : “A Comparison of Optimistic Approaches to Collaborative Editing of Wiki Pages”, 19 pages (2007)
• 2006
  • P. Sutra, M. Shapiro, J. Barreto : “An asynchronous, decentralised commitment protocol for semantic optimistic replication”, 21 pages (2006)