Michel Raynal

Last updated

Michel Raynal [1] (born 1949) is a French informatics scientist, professor at IRISA, University of Rennes, France. He is known for his contributions in the fields of algorithms, computability, and fault-tolerance in the context of concurrent and distributed systems. Michel Raynal is also Distinguished Chair professor at the Hong Kong Polytechnic University [2] and editor of the “Synthesis Lectures on Distributed Computing Theory” published by Morgan & Claypool. [3] He is a senior member of Institut Universitaire de France and a member of Academia Europaea.

Contents

Michel Raynal co-authored numerous research papers [4] [5] on concurrent and distributed computing, and has written 12 books. His last three books [6] [7] [8] constitute an introduction to fault-free and fault-tolerant concurrent and distributed computing. In his publications Michel Raynal strives to promote simplicity as a “first-class citizen” in the scientific approach. [9] Michel Raynal (and his co-authors) won several best paper awards in prestigious conferences such as IEEE ICDCS 1999, 2000 and 2001, SSS 2009 and 2011, Europar 2010, DISC 2010, and ACM PODC 2014.

When Michel Raynal became Emeritus professor (2017), INRIA, IRISA and the University of Rennes organized a Workshop [10] in his honor featuring various speakers, including Turing Award recipient (Leslie Lamport) and Dijkstra Prize recipients (Leslie Lamport, Maurice Herlihy, Yoram Moses), and professor at Collège de France (Rachid Guerraoui).

Education and career

Michel Raynal obtained bachelor degrees (French “Baccalauréat”) both in literature and science. He received his PhD from University of Rennes in 1975, and his “Doctorat d’état” in 1981. During the period 1981-1984 he was a professor in a telecommunications engineer school (ENST de Bretagne) where he created and managed the informatics department. In 1984 he moved to the university of Rennes, and in 1985 he founded a research group entirely devoted to Distributed Algorithms (at that time, one of the first groups on this research topic in the world).[ citation needed ]

Michel Raynal has been an associate member of the editorial board of international journals, including the Journal of Parallel and Distributed Computing (JPDC), IEEE Transactions on Computers (TC), and IEEE Transactions of parallel and Distributed Systems (TPDS), among others.

Research areas and scientific interests

Michel Raynal’s research contributions concern mainly concurrent and distributed computing, and more specifically: causality, distributed synchronization, fault-tolerance, distributed agreement (consensus) and distributed computability. His first book (on mutual exclusion algorithms in both shared memory and message-passing systems) [11] is recognized as one of the first books entirely devoted to distributed algorithms.

On the synchronization side, with Jean-Michel Hélary and Achour Mostéfaoui, Michel Raynal designed a very simple generic message-passing mutual exclusion algorithm from which can be derived plenty of token and tree-based mutex algorithms. [12]

On the causality side, with co-workers he produced a very simple algorithm for causal message delivery, [13] and an optimal vector-clock-based distributed checkpointing algorithms, [14] which established the theoretical foundations of distributed checkpointing, [15] and the so-called communication-based snapshot. [16] He also introduced (with Hélary and Mostéfaoui) the notion of virtual precedence. [17] Together with V. Garg, he introduced the concept of “normality” which extends the well-known linearizability consistency condition to the case where objects have polyadic operations. [18]

On the agreement side, Michel Raynal (mainly with A. Mostéfaoui) produced several algorithms for asynchronous message-passing systems which solve consensus in the presence of crash failures [19] [20] [21] or process Byzantine failures. [22] This last algorithm is an incredibly simple randomized algorithm that is optimal with respect to both time and message complexities. With Mostéfaoui and Rajsbaum, Michel Raynal also introduced a new approach to solve consensus called “condition-based”. [23] This approach brought to light a very strong connection between error-correcting codes and distributed agreement problems. [24] Michel Raynal also designed distributed algorithms for other agreement problems (such as k-set agreement and renaming).

Recently, Armando Castaneda, Sergio Rajsbaum, and Michel Raynal introduced the notion of “interval linearizability” which is the first notion that allows us to unify in a single framework the notions of “concurrent objects” and “distributed tasks”. [25]

On the computability side, Stainer, Taubenfeld, and Raynal addressed universal constructions that allow x out of k distributed state machines to progress in the presence of asynchrony and any number of process crashes. [26] Recently, from an initial idea proposed by Taubenfeld, Michel Raynal became interested in algorithms suited to anonymous memories. [27]

Awards and honours

Related Research Articles

A distributed system is a system whose components are located on different networked computers, which communicate and coordinate their actions by passing messages to one another. Distributed computing is a field of computer science that studies distributed systems.

<span class="mw-page-title-main">Mutual exclusion</span> In computing, restricting data to be accessible by one thread at a time

In computer science, mutual exclusion is a property of concurrency control, which is instituted for the purpose of preventing race conditions. It is the requirement that one thread of execution never enters a critical section while a concurrent thread of execution is already accessing said critical section, which refers to an interval of time during which a thread of execution accesses a shared resource or shared memory.

<span class="mw-page-title-main">Deadlock</span> State in which members are blocking each other

In concurrent computing, deadlock is any situation in which no member of some group of entities can proceed because each waits for another member, including itself, to take action, such as sending a message or, more commonly, releasing a lock. Deadlocks are a common problem in multiprocessing systems, parallel computing, and distributed systems, because in these contexts systems often use software or hardware locks to arbitrate shared resources and implement process synchronization.

<span class="mw-page-title-main">Leslie Lamport</span> American computer scientist and mathematician

Leslie B. Lamport is an American computer scientist and mathematician. Lamport is best known for his seminal work in distributed systems, and as the initial developer of the document preparation system LaTeX and the author of its first manual.

<span class="mw-page-title-main">Concurrency (computer science)</span> Ability to execute a task in a non-serial manner

In computer science, concurrency is the ability of different parts or units of a program, algorithm, or problem to be executed out-of-order or in partial order, without affecting the outcome. This allows for parallel execution of the concurrent units, which can significantly improve overall speed of the execution in multi-processor and multi-core systems. In more technical terms, concurrency refers to the decomposability of a program, algorithm, or problem into order-independent or partially-ordered components or units of computation.

A Byzantine fault is a condition of a computer system, particularly distributed computing systems, where components may fail and there is imperfect information on whether a component has failed. The term takes its name from an allegory, the "Byzantine generals problem", developed to describe a situation in which, in order to avoid catastrophic failure of the system, the system's actors must agree on a concerted strategy, but some of these actors are unreliable.

In computing, a parallel programming model is an abstraction of parallel computer architecture, with which it is convenient to express algorithms and their composition in programs. The value of a programming model can be judged on its generality: how well a range of different problems can be expressed for a variety of different architectures, and its performance: how efficiently the compiled programs can execute. The implementation of a parallel programming model can take the form of a library invoked from a sequential language, as an extension to an existing language, or as an entirely new language.

Nancy Ann Lynch is a computer scientist affiliated with the Massachusetts Institute of Technology. She is the NEC Professor of Software Science and Engineering in the EECS department and heads the "Theory of Distributed Systems" research group at MIT's Computer Science and Artificial Intelligence Laboratory.

Concurrent computing is a form of computing in which several computations are executed concurrently—during overlapping time periods—instead of sequentially—with one completing before the next starts.

Causal consistency is one of the major memory consistency models. In concurrent programming, where concurrent processes are accessing a shared memory, a consistency model restricts which accesses are legal. This is useful for defining correct data structures in distributed shared memory or distributed transactions.

A fundamental problem in distributed computing and multi-agent systems is to achieve overall system reliability in the presence of a number of faulty processes. This often requires coordinating processes to reach consensus, or agree on some data value that is needed during computation. Example applications of consensus include agreeing on what transactions to commit to a database in which order, state machine replication, and atomic broadcasts. Real-world applications often requiring consensus include cloud computing, clock synchronization, PageRank, opinion formation, smart power grids, state estimation, control of UAVs, load balancing, blockchain, and others.

Paxos is a family of protocols for solving consensus in a network of unreliable or fallible processors. Consensus is the process of agreeing on one result among a group of participants. This problem becomes difficult when the participants or their communications may experience failures.

In fault-tolerant distributed computing, an atomic broadcast or total order broadcast is a broadcast where all correct processes in a system of multiple processes receive the same set of messages in the same order; that is, the same sequence of messages. The broadcast is termed "atomic" because it either eventually completes correctly at all participants, or all participants abort without side effects. Atomic broadcasts are an important distributed computing primitive.

The Brooks–Iyengar algorithm or FuseCPA Algorithm or Brooks–Iyengar hybrid algorithm is a distributed algorithm that improves both the precision and accuracy of the interval measurements taken by a distributed sensor network, even in the presence of faulty sensors. The sensor network does this by exchanging the measured value and accuracy value at every node with every other node, and computes the accuracy range and a measured value for the whole network from all of the values collected. Even if some of the data from some of the sensors is faulty, the sensor network will not malfunction. The algorithm is fault-tolerant and distributed. It could also be used as a sensor fusion method. The precision and accuracy bound of this algorithm have been proved in 2016.

Baruch Awerbuch is an Israeli-American computer scientist and a professor of computer science at Johns Hopkins University. He is known for his research on distributed computing.

Daniel (Danny) Dolev is an Israeli computer scientist known for his research in cryptography and distributed computing. He holds the Berthold Badler Chair in Computer Science at the Hebrew University of Jerusalem and is a member of the scientific council of the European Research Council.

In distributed computing, a conflict-free replicated data type (CRDT) is a data structure that is replicated across multiple computers in a network, with the following features:

  1. The application can update any replica independently, concurrently and without coordinating with other replicas.
  2. An algorithm automatically resolves any inconsistencies that might occur.
  3. Although replicas may have different state at any particular point in time, they are guaranteed to eventually converge.
<span class="mw-page-title-main">Jayadev Misra</span> American computer scientist (born 1947)

Jayadev Misra is an Indian-born computer scientist who has spent most of his professional career in the United States. He is the Schlumberger Centennial Chair Emeritus in computer science and a University Distinguished Teaching Professor Emeritus at the University of Texas at Austin. Professionally he is known for his contributions to the formal aspects of concurrent programming and for jointly spearheading, with Sir Tony Hoare, the project on Verified Software Initiative (VSI).

Rachid Guerraoui is a Moroccan-Swiss computer scientist and a professor at the School of Computer and Communication Sciences at École Polytechnique Fédérale de Lausanne (EPFL), known for his contributions in the fields of concurrent and distributed computing. He is an ACM Fellow and the Chair in Informatics and Computational Science for the year 2018–2019 at Collège de France for distributed computing.

<span class="mw-page-title-main">Sergio Rajsbaum</span> Mexican computer scientist

Sergio Rajsbaum is a Mexican computer scientist, working in the field of Theoretical Computer Science, specifically concurrent and distributed computing.

References

  1. ↑ Michel Raynal's personal page on IRISA's website
  2. ↑ "Home".
  3. ↑ "Synthesis Lectures on Distributed Computing Theory".
  4. ↑ Michel Raynal's bibliography on DBLP
  5. ↑ Michel Raynal's bibliography on Google Scholar
  6. ↑ Raynal, Michel (2012). Concurrent Programming: Algorithms, Principles, and Foundations. Springer. doi:10.1007/978-3-642-32027-9. ISBN   978-3-642-32027-9. S2CID   10526009.
  7. ↑ Raynal, Michel (2013). Distributed algorithms for message-passing systems. Berlin, Heidelberg: Springer. doi:10.1007/978-3-642-38123-2. ISBN   978-3-642-38123-2. S2CID   31644113.
  8. ↑ Raynal, Michel (2018). Fault-tolerant message-passing distributed systems: an algorithmic approach. Springer. doi:10.1007/978-3-319-94141-7. ISBN   978-3-319-94141-7. S2CID   52175582.
  9. ↑ Le Bonheur, Julien (2018-07-16). "Michel Raynal distingué pour sa contribution exceptionnelle à l'algorithmique répartie" (in French). Université de Rennes 1. Retrieved 13 January 2020.
  10. ↑ "International Workshop on Distributed Computing in the honor of Michel Raynal". Inria. Retrieved 21 December 2019.
  11. ↑ Raynal, Michel (1986) [1984]. Algorithms for mutual exclusion. Cambridge: MIT Press. ISBN   0-262-18119-3.
  12. ↑ Hélary, Jean-Michel; Mostéfaoui, Achour; Raynal, Michel (November 1994). "A general scheme for token- and tree-based distributed mutual exclusion algorithms" (PDF). IEEE Transactions on Parallel and Distributed Systems. 5 (11): 1185–1196. doi:10.1109/71.329670. ISSN   2161-9883.
  13. ↑ Raynal, Michel; Schiper, André; Toueg, Sam (September 1991). "The causal ordering abstraction and a simple way to implement it" (PDF). Information Processing Letters. 39 (6): 343–350. doi:10.1016/0020-0190(91)90008-6.
  14. ↑ Baldoni, Roberto; Hélary, Jean-Michel; Raynal, Michel (March 2001). "Rollback-Dependency Trackability: A Minimal Characterization and Its Protocol". Information and Computation. 165 (2): 144–173. doi: 10.1006/inco.2000.2906 .
  15. ↑ Hélary, J.-M.; Mostefaoui, A.; Netzer, R.H.B.; Raynal, M. (1 January 2000). "Communication-based prevention of useless checkpoints in distributed computations". Distributed Computing. 13 (1): 29–43. doi:10.1007/s004460050003. S2CID   6554750.
  16. ↑ Helary, J.; Mostefaoui, A.; Raynal, M. (1999). "Communication-induced determination of consistent snapshots". IEEE Transactions on Parallel and Distributed Systems. 10 (9): 865–877. doi:10.1109/71.798312. S2CID   13939609.
  17. ↑ Hélary, J.M.; Mostefaoui, A.; Raynal, M. (March 2002). "Interval Consistency of Asynchronous Distributed Computations". Journal of Computer and System Sciences. 64 (2): 329–349. doi: 10.1006/jcss.2001.1819 .
  18. ↑ GARG, VIJAY K.; RAYNAL, MICHEL (21 November 2011). "Normality: A CONSISTENCY CONDITION FOR CONCURRENT OBJECTS". Parallel Processing Letters. 09 (1): 123–134. doi:10.1142/S0129626499000141. S2CID   16427772.
  19. ↑ MOSTEFAOUI, A.; RAYNAL, M. (21 November 2011). "Leader-Based Consensus". Parallel Processing Letters. 11 (1): 95–107. doi:10.1142/S0129626401000452.
  20. ↑ Guerraoui, R.; Raynal, M. (16 October 2006). "The Alpha of Indulgent Consensus" (PDF). The Computer Journal. 50 (1): 53–67. doi:10.1093/comjnl/bxl046.
  21. ↑ Mostefaoui, Achour; Rajsbaum, Sergio; Raynal, Michel; Travers, Corentin (January 2008). "The Combined Power of Conditions and Information on Failures to Solve Asynchronous Set Agreement". SIAM Journal on Computing. 38 (4): 1574–1601. doi:10.1137/050645580. S2CID   12886589.
  22. ↑ Mostéfaoui, Achour; Moumen, Hamouma; Raynal, Michel (11 September 2015). "Signature-Free Asynchronous Binary Byzantine Consensus with t < n/3, O(n2) Messages, and O(1) Expected Time" (PDF). Journal of the ACM. 62 (4): 1–21. doi:10.1145/2785953. S2CID   2212421.
  23. ↑ Mostefaoui, Achour; Rajsbaum, Sergio; Raynal, Michel (1 November 2003). "Conditions on input vectors for consensus solvability in asynchronous distributed systems". Journal of the ACM. 50 (6): 922–954. doi:10.1145/950620.950624.
  24. ↑ Friedman, Roy; Mostefaoui, Achour; Rajsbaum, Sergio; Raynal, Michel (July 2007). "Asynchronous Agreement and Its Relation with Error-Correcting Codes". IEEE Transactions on Computers. 56 (7): 865–875. doi:10.1109/TC.2007.1043. S2CID   9418243.
  25. ↑ Castañeda, Armando; Rajsbaum, Sergio; Raynal, Michel (19 November 2018). "Unifying Concurrent Objects and Distributed Tasks". Journal of the ACM. 65 (6): 1–42. doi:10.1145/3266457. S2CID   53877441.
  26. ↑ Raynal, Michel; Stainer, Julien; Taubenfeld, Gadi (19 August 2015). "Distributed Universality". Algorithmica. 76 (2): 502–535. doi:10.1007/s00453-015-0053-3. S2CID   10912125.
  27. ↑ Raynal, Michel; Taubenfeld, Gadi (2019). "Mutual exclusion in fully anonymous shared memory systems".{{cite journal}}: Cite journal requires |journal= (help)
  28. ↑ Michel Raynal's page Archived 2015-01-11 at the Wayback Machine on the website of the Institut Universitaire de France
  29. ↑ "SIROCCO 2015 website". Archived from the original on 2015-11-27. Retrieved 2015-03-10.
  30. ↑ Michel Raynal's page on the website of Academia Europaea
  31. ↑ "Michel Raynal distingué pour sa contribution exceptionnelle à l'algorithme répartie". Université de Rennes 1. July 2018.
  32. ↑ Le Bonheur, Julien (16 July 2018). "Michel Raynal distingué pour sa contribution exceptionnelle à l'algorithmique répartie" (in French). Université de Rennes 1. Retrieved 13 January 2020.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.