2026-07-22T22:39:02Z https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:25183 2026-03-19T12:59:18Z ddc:004 open_access
Computing in a Faulty Congested Clique Censor-Hillel, Keren Soto, Pedro distributed computing graph algorithms computing with faults We study a Faulty Congested Clique model, in which an adversary may fail nodes in the network throughout the computation. We show that any task of O(nlog{n})-bit input per node can be solved in roughly n rounds, where n is the size of the network. This nearly matches the linear upper bound on the complexity of the non-faulty Congested Clique model for such problems, by learning the entire input, and it holds in the faulty model even with a linear number of faults. Our main contribution is that we establish that one can do much better by looking more closely at the computation. Given a deterministic algorithm π’œ for the non-faulty Congested Clique model, we show how to transform it into an algorithm π’œ' for the faulty model, with an overhead that could be as small as some logarithmic-in-n factor, by considering refined complexity measures of π’œ. As an exemplifying application of our approach, we show that the O(n^{1/3})-round complexity of semi-ring matrix multiplication [Censor{-}Hillel, Kaski, Korhonen, Lenzen, Paz, Suomela, PODC 2015] remains the same up to polylog factors in the faulty model, even if the adversary can fail 99% of the nodes (or any other constant fraction). Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik Keren Censor-Hillel and Pedro Soto 2026 Is Part Of LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2025.10 urn:nbn:de:0030-drops-251833 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.10 eng https://creativecommons.org/licenses/by/4.0/legalcode