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).
|
Text
MST-SSS19.pdf - Author Accepted Manuscript Download (305kB) | Preview |
Abstract
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 |
Dimensions
Dimensions
