Fault tolerant network constructors

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.

Authors

• Othon Michail
• Paul G. Spirakis
• Michail Theofilatos

Keywords

• Network construction
• Distributed protocol
• Self stabilization
• Fault tolerant protocol
• Dynamic graph formation
• Population
• Fairness
• Self-organization