Vi studerar deterministiskt skvaller i synkrona system med dynamiska kraschfel. Varje processor initieras med ett ingångsvärde som kallas rykte. I vanliga skvaller problem, målet för varje processor är att lära sig alla rykten. När processorer kan krascha, då detta mål behöver revideras, eftersom det är möjligt, vid en tidpunkt i en avrättning, att vissa rykten är kända endast för processorer som redan har kraschat. Vi definierar skvaller som ska slutföras, för ett system med krascher, när varje processor vet antingen ryktet om processorn v eller att v redan har kraschat, för alla processorer v. Vi designar skvalleralgoritmer som är effektiva med avseende på både tid och kommunikation. Låt t < n vara antalet fel, där n är antalet processorer. Om n − t =  till (n/polylog n), då en av våra algoritmer avslutar skvaller i O(log 2 t) tid och med O(n polylog n) meddelanden. Vi utvecklar en algoritm som utför skvaller med O(n 1,77 ) meddelanden och i O(log 2 n) tid, i varje utförande där minst en processor förblir icke-felaktig. Vi visar en avvägning mellan tid och kommunikation i skvaller algoritmer: om antalet meddelanden är som mest O(n polylog n), då måste tiden vara minst  och log n log (n log n)-logg t. Genom tillämpning, visar vi att om n − t = n), då samförstånd kan lösas i O(t) tid och med O(n log 2 t) meddelanden.
Chlebus och Kowalski REF presenterar deterministiska algoritmer (baserade på en expandergraph konstruktion) som säkerställer spridning av rykten inom tid O(log 2 t) använder O(n polylog t) totala meddelanden, där t är antalet fel.
Robust gossiping with an application to consensus
{'venue': 'Journal of Computer and System Science', 'journal': None, 'mag_field_of_study': ['Computer Science']}