2024/02/14 by Stephan Felber, Felber, Stephan, Hugo Rincon Galeana +1
Computer Science · #C.2.4 #Distributed #Distributed systems and fault tolerance #F.2.0 #FOS: Computer and information sciences #G.2.2 #Mobile Agent-Based Network Management #Parallel #Service-Oriented Architecture and Web Services #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2402.09168
openalex publication_date 2024/02/14 · openalex created_date 2024/02/16 · openalex updated_date 2026/07/28
A substantial portion of distributed computing research is dedicated to terminating problems like consensus and similar agreement problems. However, non-terminating problems have been intensively studied in the context of self-stabilizing distributed algorithms, where processes may start from arbitrary initial states and can tolerate arbitrary transient faults. In between lie stabilizing problems, where the processes start from a well-defined initial state, but do not need to decide irrevocably and are allowed to change their decision finitely often until a stable decision is eventually reached. In this paper, we introduce the novel Delayed Lossy-Link (DLL) model, and the Lossy Iterated Immediate Snapshot Model (LIIS), for which we show stabilizing consensus to be impossible. The DLL model is introduced as a variant of the well-known Lossy-Link model, which admits silence periods of arbitrary but finite length. The LIIS model is a variant of the Iterated Immediate Snapshot (IIS), model which admits finite length periods of at most f omission faults per layer. In particular, we show that stabilizing consensus is impossible even when f=1. Our results show that even in a model with very strong connectivity, namely, the Iterated Immediate Snapshot (IIS) model, a single omission fault per layer effectively disables stabilizing consensus. Furthermore, since the DLL model always has a perpetual broadcaster, the mere existence of a perpetual broadcaster, even in a crash-free setting, is not sufficient for solving stabilizing consensus, negatively answering the open question posed by Charron-Bost and Moran.