TY - GEN
T1 - Universal model simulation
T2 - 15th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2013
AU - Kuznetsov, Petr
PY - 2013/12/1
Y1 - 2013/12/1
N2 - This paper focuses on simulations as a means of deriving the relative power of distributed computing models. We describe an abstract simulation algorithm that enables reducing the question of solvability of a generic distributed task in one model to an equivalent question in another model. The technique implies simple equivalents to the fundamental reduction by Borowsky and Gafni, known as BG simulation, as well as to Extended BG, a more recent extension of it to colored tasks. We also sketch how the parameters of our technique can be tuned to derive recent equivalence results for models that use, in addition to basic read-write memory, k-set agreement or k-process consensus objects, or make assumptions on active resilience.
AB - This paper focuses on simulations as a means of deriving the relative power of distributed computing models. We describe an abstract simulation algorithm that enables reducing the question of solvability of a generic distributed task in one model to an equivalent question in another model. The technique implies simple equivalents to the fundamental reduction by Borowsky and Gafni, known as BG simulation, as well as to Extended BG, a more recent extension of it to colored tasks. We also sketch how the parameters of our technique can be tuned to derive recent equivalence results for models that use, in addition to basic read-write memory, k-set agreement or k-process consensus objects, or make assumptions on active resilience.
U2 - 10.1007/978-3-319-03089-0_2
DO - 10.1007/978-3-319-03089-0_2
M3 - Conference contribution
AN - SCOPUS:84893911110
SN - 9783319030883
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 17
EP - 31
BT - Stabilization, Safety, and Security of Distributed Systems - 15th International Symposium, SSS 2013, Proceedings
Y2 - 13 November 2013 through 16 November 2013
ER -