Fault tolerant network constructors

Michail, Othon ORCID: 0000-0002-6234-3960, Spirakis, Paul G ORCID: 0000-0001-5396-3749 and Theofilatos, Michail ORCID: 0000-0002-3699-0179
(2023) Fault tolerant network constructors. In: International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS).

[thumbnail of MST-SSS19.pdf] Text
MST-SSS19.pdf - Author Accepted Manuscript

Download (305kB) | Preview


We consider adversarial crash faults of nodes in the network constructors model [Michail and Spirakis, 2016]. We first show that, without further assumptions, the class of graph languages that can be (stably) constructed under crash faults is non-empty but small. On the positive side, linear waste enables the construction, on a fraction of the nodes, of any graph language that is constructible in the fault-free case and partial constructibility allows us to construct a large class of graph languages. We then extend the original model with a minimal form of fault notifications. Our main result under that model is a fault-tolerant universal constructor. Finally, we show that logarithmic local memories can be exploited for a no-waste fault-tolerant simulation of any network constructor.

Item Type: Conference or Workshop Item (Unspecified)
Uncontrolled Keywords: Network construction, Distributed protocol, Self stabilization, Fault tolerant protocol, Dynamic graph formation, Population, Fairness, Self -organization
Depositing User: Symplectic Admin
Date Deposited: 16 Sep 2019 08:40
Last Modified: 07 Jun 2023 13:22
DOI: 10.1016/j.ic.2023.105037
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3054747