  In this work, 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. In particular, if an
unbounded number of crash faults may occur, we prove that (i) the only
constructible graph language is that of spanning cliques and (ii) a strong
impossibility result holds even if the size of the graphs that the protocol
outputs in populations of size $n$ need only grow with $n$ (the remaining nodes
being waste). When there is a finite upper bound $f$ on the number of faults,
we show that it is impossible to construct any non-hereditary graph language.
On the positive side, by relaxing our requirements we prove that: (i)
permitting linear waste enables to construct on $n/(2f)-f$ nodes, any graph
language that is constructible in the fault-free case, (ii) partial
constructibility (i.e. not having to generate all graphs in the language)
allows the construction of a large class of graph languages. We then extend the
original model with a minimal form of fault notifications. Our main result here
is a fault-tolerant universal constructor: We develop a fault-tolerant protocol
for spanning line and use it to simulate a linear-space Turing Machine $M$.
This allows a fault-tolerant construction of any graph accepted by $M$ in
linear space, with waste $min\{n/2+f(n),\; n\}$, where $f(n)$ is the number of
faults in the execution. We then prove that increasing the permissible waste to
$min\{2n/3+f(n),\; n\}$ allows the construction of graphs accepted by an
$O(n^2)$-space Turing Machine, which is asymptotically the maximum simulation
space that we can hope for in this model. Finally, we show that logarithmic
local memories can be exploited for a no-waste fault-tolerant simulation of any
such protocol.
