DROPS

Document

DOI: 10.4230/LIPIcs.DISC.2025.10

Amnesiac Flooding: Easy to Break, Hard to Escape

Authors: Henry Austin, Maximilien Gadouleau, George B. Mertzios, and Amitabh Trehan

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract

Broadcast is a central problem in distributed computing. Recently, Hussak and Trehan [PODC'19/ STACS'20/DC'23] proposed a stateless broadcasting protocol (Amnesiac Flooding), which was surprisingly proven to terminate in asymptotically optimal time (linear in the diameter of the network). However, it remains unclear: (i) Are there other stateless terminating broadcast algorithms with the desirable properties of Amnesiac Flooding, (ii) How robust is Amnesiac Flooding with respect to faults? In this paper we make progress on both of these fronts. Under a reasonable restriction (obliviousness to message content) additional to the fault-free synchronous model, we prove that Amnesiac Flooding is the only strictly stateless deterministic protocol that can achieve terminating broadcast. We achieve this by identifying four natural properties of a terminating broadcast protocol that Amnesiac Flooding uniquely satisfies. In contrast, we prove that even minor relaxations of any of these four criteria allow the construction of other terminating broadcast protocols. On the other hand, we prove that Amnesiac Flooding can become non-terminating or non-broadcasting, even if we allow just one node to drop a single message on a single edge in a single round. As a tool for proving this, we focus on the set of all configurations of transmissions between nodes in the network, and obtain a dichotomy characterizing the configurations, starting from which, Amnesiac Flooding terminates. Additionally, we characterise the structure of sets of Byzantine agents capable of forcing non-termination or non-broadcast of the protocol on arbitrary networks.

Cite as

Henry Austin, Maximilien Gadouleau, George B. Mertzios, and Amitabh Trehan. Amnesiac Flooding: Easy to Break, Hard to Escape. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 10:1-10:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{austin_et_al:LIPIcs.DISC.2025.10,
  author =	{Austin, Henry and Gadouleau, Maximilien and Mertzios, George B. and Trehan, Amitabh},
  title =	{{Amnesiac Flooding: Easy to Break, Hard to Escape}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{10:1--10:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.10},
  URN =		{urn:nbn:de:0030-drops-248273},
  doi =		{10.4230/LIPIcs.DISC.2025.10},
  annote =	{Keywords: Amnesiac flooding, Terminating protocol, Algorithm state, Stateless protocol, Flooding algorithm, Network algorithms, Graph theory, Termination, Communication, Broadcast}
}

Document

Invited Talk

DOI: 10.4230/OASIcs.AUTOMATA.2021.1

Dynamical Properties of Disjunctive Boolean Networks (Invited Talk)

Authors: Maximilien Gadouleau

Published in: OASIcs, Volume 90, 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)

Abstract

A Boolean network is a mapping f :{0,1}ⁿ → {0,1}ⁿ, which can be used to model networks of n interacting entities, each having a local Boolean state that evolves over time according to a deterministic function of the current configuration of states. In this paper, we are interested in disjunctive networks, where each local function is simply the disjunction of a set of variables. As such, this network is somewhat homogeneous, though the number of variables may vary from entity to entity, thus yielding a generalised cellular automaton. The aim of this paper is to review some of the main results, derive some additional fundamental results, and highlight some open problems on the dynamics of disjunctive networks. We first review the different defining characteristics of disjunctive networks and several ways of representing them using graphs, Boolean matrices, or binary relations. We then focus on three dynamical properties of disjunctive networks: their image points, their periodic points, and their fixed points. For each class of points, we review how they can be characterised and study how many they could be. The paper finishes with different avenues for future work on the dynamics of disjunctive networks and how to generalise them.

Cite as

Maximilien Gadouleau. Dynamical Properties of Disjunctive Boolean Networks (Invited Talk). In 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021). Open Access Series in Informatics (OASIcs), Volume 90, pp. 1:1-1:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{gadouleau:OASIcs.AUTOMATA.2021.1,
  author =	{Gadouleau, Maximilien},
  title =	{{Dynamical Properties of Disjunctive Boolean Networks}},
  booktitle =	{27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)},
  pages =	{1:1--1:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-189-4},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{90},
  editor =	{Castillo-Ramirez, Alonso and Guillon, Pierre and Perrot, K\'{e}vin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.AUTOMATA.2021.1},
  URN =		{urn:nbn:de:0030-drops-140105},
  doi =		{10.4230/OASIcs.AUTOMATA.2021.1},
  annote =	{Keywords: Boolean networks, disjunction, conjunction, fixed points, rank}
}

Search Results

Documents authored by Gadouleau, Maximilien

Amnesiac Flooding: Easy to Break, Hard to Escape

Abstract

Cite as

Dynamical Properties of Disjunctive Boolean Networks (Invited Talk)

Abstract

Cite as

Thanks for your feedback!

Could not send message