Knowledge Connectivity vs. Synchrony Requirements for Fault-Tolerant Agreeme...

Google Tech Talks April, 18 2008 ABSTRACT Agreement problems are fundamental building blocks of reliable distributed systems, and the issue of designing reliable solutions that can cope with the high dynamism and self-organization nature of mobile ad-hoc and peer-to-peer networks is a very active field of current research. The core problem behind agreement problems is the consensus problem. Informally, a group of processes achieves consensus in the following sense: each process initially proposes a value and all correct processes must reach a common decision on some value that is equal to one of the proposed values. It is well known that in classical environments, in which entities behave asynchronously and where identities are known, consensus cannot be solved in the presence of even one process crash. It appears that self-organizing systems are even less favorable because the set and identity of participants are not known. In this talk, we are going to present necessary and sufficient conditions under which fault-tolerant consensus become solvable in these environments. Those conditions are related to the synchrony requirements of the environment, as well as the connectivity of the knowledge graph constructed by the nodes in order to communicate with their peers. Joint work with Professor Sébastien Tixeuil, from LIP6, Université Paris 6, France Speaker: Fabíola Greve Fabíola Greve received the PhD degree in computer science in 2002 from Rennes University, INRIA Labs, France for her work on agreement protocols and group communication middleware. She is currently an associate professor in the Department of Computer Science at the Federal University of Bahia, Brazil, where she acts as the leader of the Gaudi distributed computing group. Her research interests are distributed computing and fault tolerance. Her current projects aim at identifying conditions and protocols able to provide fault tolerance in dynamic and self organizing systems, like as Manets and P2P systems.