caa a22 4500 445354941 CHVBK 20180317142857.0 cr unu---uuuuu 170323e20111101xx s 000 0 eng 10.1007/s00446-010-0116-2 doi (NATIONALLICENCE)springer-10.1007/s00446-010-0116-2 Randomization can be a healer: consensus with dynamic omission failures [Elektronische Daten] [Henrique Moniz, Nuno Neves, Miguel Correia, Paulo Veríssimo] Wireless ad-hoc networks are being increasingly used in diverse contexts, ranging from casual meetings to disaster recovery operations. A promising approach is to model these networks as distributed systems prone to dynamic communication failures. This captures transitory disconnections in communication due to phenomena like interference and collisions, and permits an efficient use of the wireless broadcasting medium. This model, however, is bound by the impossibility result of Santoro and Widmayer, which states that, even with strong synchrony assumptions, there is no deterministic solution to any non-trivial form of agreement if n − 1 or more messages can be lost per communication round in a system with n processes. In this paper we propose a novel way to circumvent this impossibility result by employing randomization. We present a consensus protocol that ensures safety in the presence of an unrestricted number of omission faults, and guarantees progress in rounds where such faults are bounded by $${f \,{\leq}\,\lceil \frac{n}{2} \rceil (n\,{-}\,k)\,{+}\,k\,{-}\,2}$$, where k is the number of processes required to decide, eventually assuring termination with probability 1. Springer-Verlag, 2010 Moniz Henrique Faculty of Sciences, University of Lisboa, LASIGE, Lisbon, Portugal aut Neves Nuno Faculty of Sciences, University of Lisboa, LASIGE, Lisbon, Portugal aut Correia Miguel Faculty of Sciences, University of Lisboa, LASIGE, Lisbon, Portugal aut Veríssimo Paulo Faculty of Sciences, University of Lisboa, LASIGE, Lisbon, Portugal aut Distributed Computing Springer-Verlag 24/3-4(2011-11-01), 165-175 0178-2770 24:3-4<165 2011 24 446 https://doi.org/10.1007/s00446-010-0116-2 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00446-010-0116-2 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Moniz Henrique Faculty of Sciences, University of Lisboa, LASIGE, Lisbon, Portugal aut NATIONALLICENCE 700 1- Neves Nuno Faculty of Sciences, University of Lisboa, LASIGE, Lisbon, Portugal aut NATIONALLICENCE 700 1- Correia Miguel Faculty of Sciences, University of Lisboa, LASIGE, Lisbon, Portugal aut NATIONALLICENCE 700 1- Veríssimo Paulo Faculty of Sciences, University of Lisboa, LASIGE, Lisbon, Portugal aut NATIONALLICENCE 773 0- Distributed Computing Springer-Verlag 24/3-4(2011-11-01), 165-175 0178-2770 24:3-4<165 2011 24 446 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer