Mañana 9 a las 15:00 en el seminario 103 del departamental 2 de Móstoles hay charla de Corentin.
Title:
Beyond consensus : weak coordination tasks in asynchronous
distributed systems
Abstract :
In an asynchronous distributed system, independent processes run at varying speeds and may even crash; they communicate through unsynchronized primitives, like sending and receiving messages.
To perform shared computation, processes need to coordinate their actions. This is theoretically modeled as solving a coordination task, where processes start with some inputs and have to output values satisfying certain conditions. A fundamental task is consensus, from which it is possible to solve any other coordination task. However, this task is not solvable in asynchronous failures prone environments.
We study sub-consensus tasks, i.e., coordination tasks that are weaker than consensus. In particular, we focus on renaming which requires processes to rename in a tighter name space, k-set-consensus which extends consensus by allowing processes to decide on a small number (k).
We first explore, through algorithmic reductions, the relationships between these sub-tasks. The second part deals with the use of failure detector to solve set agreement. A failure detector is a distributed oracle giving indications about the correctness of processes. We determine the relative computational power provided by various families of failure detectors. The last part looks as failure detector as mechanisms to restrict the possible executions rather than oracle.
We show that failure detectors can be seen as schedulers. For each failure detector fd presented in the dissertation, we define a restriction of the iterated immediate snapshot model of E. Gafni that has exactly the same computational power (in the sense of ability to solve coordination tasks) as the classical model enhanced with fd.
To perform shared computation, processes need to coordinate their actions. This is theoretically modeled as solving a coordination task, where processes start with some inputs and have to output values satisfying certain conditions. A fundamental task is consensus, from which it is possible to solve any other coordination task. However, this task is not solvable in asynchronous failures prone environments.
We study sub-consensus tasks, i.e., coordination tasks that are weaker than consensus. In particular, we focus on renaming which requires processes to rename in a tighter name space, k-set-consensus which extends consensus by allowing processes to decide on a small number (k).
We first explore, through algorithmic reductions, the relationships between these sub-tasks. The second part deals with the use of failure detector to solve set agreement. A failure detector is a distributed oracle giving indications about the correctness of processes. We determine the relative computational power provided by various families of failure detectors. The last part looks as failure detector as mechanisms to restrict the possible executions rather than oracle.
We show that failure detectors can be seen as schedulers. For each failure detector fd presented in the dissertation, we define a restriction of the iterated immediate snapshot model of E. Gafni that has exactly the same computational power (in the sense of ability to solve coordination tasks) as the classical model enhanced with fd.
No hay comentarios:
Publicar un comentario