As the conclusion of our paper, we now assess to which extent the properties of our implementation of the FATAL+ algorithm, which have been expressed and verified within our modeling framework and tested experimentally, meet our design goals. Furthermore, we will discuss a number of potential improvements and future research avenues. Our exposition will follow the optimization criteria listed in Section 2.1.7.•Area consumption: For a suitable implementation, the total number of gates is O(nlogn) per node. This can be seen by observing that the complexity of the threshold gates is dominating the asymptotic number of gates, since the O(n) remaining components of a node have a constant number of gates each; using sorting networks to implement threshold gates, the stated complexity bound follows [48]. Trivially, this number of gates is a factor of O(logn) from optimal. We conjecture that in fact this complexity is asymptotically optimal, unless one is willing to sacrifice other desirable properties of the algorithm (e.g. optimal resilience). Assuming that the gate complexity of the nodes adequately represents the area consumption of our algorithm, we conclude that our solution is satisfactory in that regard.•Communication complexity: Our implementation uses 7 (1-bit) wires per channel, and sequential encoding of the states of the main state machine would reduce this number to 5. All communication are broadcasts. Considering the complexity of the task, there seems to be very limited room for improvement.•Stabilization time: Our algorithm has a stabilization time of O(n) in the worst case. Recent findings [49] show that a polylogarithmic stabilization time can be achieved at a low communication complexity; however, this comes at the expense of suboptimal resilience, a weaker adversarial model, and, most importantly, constants in the complexity bounds that make the resulting algorithm inferior to our solution for any practical range of parameters. Moreover, as formalized in [13] and demonstrated in Section 7, for a wide range of scenarios our algorithm achieves constant stabilization time. Considering the severe fault model, we conclude that despite not being optimal, our algorithm performs satisfactory with respect to this quality measure.•Resilience: It is known that 3f+1 nodes are necessary to tolerate f faults [25,14] unless cryptographic tools are available. Since the complexity incurred by cryptographic tools is prohibitive in our setting, our algorithm features optimal resilience.•Delays: As mentioned, the delay of wires is outside our control. Taking dmin+ and dmax+ into account in the quick cycle machine, we make best use of the available bounds in terms of the final frequency/synchrony trade-off. The delays incurred by the computations performed at nodes are proportional to the depths of the involved circuits. Again, the implementation of the threshold gates is the dominant cost factor here. The sorting network by Ajtai et al. [48] exhibits depth O(logn). Assuming constant fan-in of gates, this is clearly asymptotically optimal if the decision when to increase the logical clock Lv next indeed depends on all n−1 input signals of v from remote nodes. We conclude that, so far as within our control, the design goal of minimizing the incurred delays is met by our algorithm.•Metastability: We discussed several effective measures to prevent metastability in Section 6. Our experiments support our theoretical finding that, after stabilization, metastability may not occur in absence of further faults. However, since metastability is an elusive problem for which it is difficult to transfer insights and observations to other modes of operation of a given system—let alone to different implementation technology—a mathematical treatment of metastability is highly desirable. Our model opens up various possible approaches to this issue. For one, it is feasible to switch to a more accurate description of signals in terms of signals' voltages as continuous functions of time. Another option choosing an intermediate level of complexity would be to add an additional signal state (e.g. ⊥) for “invalid” signals, representing e.g. creeping or oscillating signals. Assigning appropriate probabilities of metastability propagation and decay to modules, this would enable a unified probabilistic analysis of metastability generation, propagation, and decay within a modeling framework using discrete state representations. Such an approach could yield entirely unconditional guarantees on system recovery; in contrast, our current description requires an a priori guarantee that metastability is sufficiently contained during the stabilization process.•Connectivity: The algorithm presented in this work requires to connect all pairs of nodes and is therefore not scalable. Unfortunately, it is known that Ω(n2) links are required for tolerating f∈Ω(n) faults in the worst case [26,27]. We argued for the assumption of worst-case behavior of faulty nodes; however, it appears reasonable that typical systems will not exhibit a worst-case distribution of faults within the system. Indeed, many interesting scenarios justify to assume a much more benign distribution of faults. In the extreme case where faults are distributed uniformly and independently at random with a constant probability, say, 10%, of a node being faulty, node degrees of Δ∈O(clogn) would suffice to guarantee (at a given point in time) that the probability that more than Δ/9 neighbors of any node are faulty, is at most 1−1/nc. Note that this implies that the mean time until this property is violated polynomially grows with system size. Using the FATAL+ protocol in small subsystems (of less than Δ nodes), system-wide synchronization will be much easier to achieve than if one would start from scratch. In this setting, Δ∈O(logn) would replace n in all complexity bounds of the FATAL+ algorithm, resulting in particular in gate complexity O(lognloglogn) per node, computational delay O(loglogn), and stabilization time O(clogn) with probability 1−1/nc. Thus, this approach promises “local” fault-tolerance of Ω(Δ) faults in each neighborhood in combination with excellent scalability in all complexity measures, and realizing this is a major goal of our future work.•Clock size: The constraint (1) entails that either clock size is bounded or large clocks result in larger stabilization time. This restriction can be overcome if we use the clocks of bounded size generated by FATAL+ as input to another layer that runs a synchronous consensus algorithm in order to agree on exponentially larger clocks [41]. Finally, we would like to mention two more prospective extensions of our work. First, building on our modeling framework, it seems feasible to tackle an even more strict verification of the algorithm's properties than “standard” mathematical analysis. The hierarchical structure and formal specifications of modules seem amenable to formal verification methods. Such an approach should benefit from the possibilities to adjust the granularity of the model by the distinction between basic and compound modules as well as the restrictions imposed by the module specifications; more restrictive modules may be simpler to analyze, yet will guarantee the same properties as the stated variants. Second, it should be noted that it is straightforward to derive clocks of even higher frequency from the FATAL+ clocks. This is essentially done by frequency multiplication, at the expense of increasing the clock skew. We refer to Dolev et al. [13] for details.
wires per channel
7
wires
1-bit
bit
node
probability
10%
%