Recent Advances in
R/W Computability with Speculations

Tutorial
Eli Gafni
Friday, July 28, 2017

3 hours with two 10 minutes breaks

 Tools

1. The Extended BG Simulation.
2. Generalized Universality and the resultant ER (Eli-Rachid) simulation.
3. GACT: Generalized Asynchronous Computability Theorem.
4. Constructive Convergence algorithm for Affine complexes.
5. Objects as Tasks.
6. Solving tasks by the cumulative set consensus power of available objects.
7. The demise of the Byzantine.

 Vision

1. Tasks are the “function” of Distributed Computing (DC)
2. Church-Thesis for DC: Any reasonable (causal) framework, MP, Objects, etc., properly extended (e.g. composite objects) gives rise to the same set of time stationary models.
3. The models above correspond to Affine complexes and those are decidable. Hence deterministic objects (and composite) correspond to affine tasks and are robust and decidable.
4. The Wait-Free model is Universal: Given a task T and a model M, there exist a task T(M) solvable wait-free iff T is solvable in M.