We investigate the minimal number of failures that can partition a system where processes communicate both through shared memory and by message passing. We prove that this number precisely captures the resilience that can be achieved by algorithms that implement a variety of shared objects, like registers and atomic snapshots, and solve common tasks, like randomized consensus, approximate agreement and renaming. This has implications for the m&m-model of [Aguilera et al., 2018] and for the hybrid, cluster-based model of [Damien Imbs and Michel Raynal, 2013; Michel Raynal and Jiannong Cao, 2019].
@InProceedings{attiya_et_al:LIPIcs.OPODIS.2020.16, author = {Attiya, Hagit and Kumari, Sweta and Schiller, Noa}, title = {{Optimal Resilience in Systems That Mix Shared Memory and Message Passing}}, booktitle = {24th International Conference on Principles of Distributed Systems (OPODIS 2020)}, pages = {16:1--16:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-176-4}, ISSN = {1868-8969}, year = {2021}, volume = {184}, editor = {Bramas, Quentin and Oshman, Rotem and Romano, Paolo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.16}, URN = {urn:nbn:de:0030-drops-135019}, doi = {10.4230/LIPIcs.OPODIS.2020.16}, annote = {Keywords: fault resilience, m\&m model, cluster-based model, randomized consensus, approximate agreement, renaming, register implementations, atomic snapshots} }
Feedback for Dagstuhl Publishing