This talk introduces and explores a new approach to solve the consensus problem in asynchronous systems that we call the “Condition-Based” approach. It consists in identifying sets of input vectors for which it is possible to design a protocol solving consensus despite the occurrence of process crashes.
The first main result is a generic consensus protocol for the shared memory model. It always guarantees agreement, and also termination (at least) when the inputs satisfy the condition with which the protocol has been instantiated, or when there is no crash. Then, two particular realistic conditions are investigated. A second main result is the statement of a general characterization that captures the set of all the conditions that allow to solve consensus, proving that the protocol works in all these cases. An efficient version of the generic protocol is then designed for the message passing model. It is also shown how the protocol safety can be traded for liveness. The theory that underlies the condition-based approach is also investigated.
Speaker Biography
Michel Raynal received his “doctorat d’Etat” in computer science from the University of Rennes, France, in 1981. In 1981 he moved to Brest (France) where he founded the computer science department in a telecommunications engineer school (ENST). In 1984 he moved to the University of Rennes where he has been a professor of computer science. At IRISA (CNRS-INRIA-University joint computing research laboratory located in Rennes), he is the founder and the leader of the research group “Distributed Algorithms and Protocols”. His research interests include distributed algorithms, operating systems, computing systems, protocols and dependability.
Professor Michel Raynal has published more than 70 papers in journals and more than 140 papers in conferences. He has has written seven books devoted to parallelism, distributed algorithms and systems. Michel Raynal has been invited to serve in program committees for more than 50 international conferences. In 1989 and 1995 he served as the program chair of the WDAG/DISC symposium on Distributed Algorithms. In 1999 he served as the general chair of the IEEE Conference on Object-Oriented Real-time Distributed Computing (ISORC'99). He is the program co-chair of IEEE International Conference on Distributed Comuting Systems (ICDCS'02) that will be held in Vienna (Austria), and the conference co-chair of ISORC'02 that will be held in Washington DC (April 02).