Résumé | Simulations are powerful tools in the study of the computability power of a distributed system. A simulation takes as input an algorithm that solves an instance of a given class of problems in a given model and produces as output another algorithm that executes correctly in another model.
This talk will first present the BG simulation, that shows that in a crash-prone asynchronous shared memory model, the important parameter regarding computability is the number of possible crashes, not the total number of processes. It will then present a more recent simulation that shows that, under certain conditions, Byzantine failure-prone systems can solve the same class of problems as crash-prone ones.
|