Alex Koessler

Martin Perner

Thomas Nowak

Josef Widder

Florian Huemer

Manfred Schwarz

Jürgen Maier

Thomas Polzer

Kyrill Winkler

Traude Sommer

Stephan Friedrichs

Attila Kinali

Moti Medina

Johannes Bund

Michael Dirnberger

Bernadette Charron

Stéphane Demri

Stefan Haar

Hubert Comon-Lundh

Laurent Fribourg

Stefan Schwoon

Béatrice Bérard

The design and analysis of low-level computing devices directly implemented in hardware is commonly based on finite state machine models. In this work we review some of the assumptions made in these designs and discuss techniques for the cases where the assumptions fail to hold. The work concentrates on three such aspects: (i) computing under conditions where low-level timing effects cannot be neglected, (ii) when non-binary signals play a central role, and (iii) computing within a changing infrastructure, i.e., dynamic networks. While most of this work is devoted to implementations in silicon, microbiological circuits are discussed in the outlook. I'd like to start this thesis with a thank you to the many who have made this not only happen, but an enjoyable and interesting journey together. It would be impossible to mention all who contributed and all the great experiences along this path and so I apologize upfront for those not mentioned in this really short summary -rest assured you are not forgotten.

I'd like to begin with the members of the habilitation committee, who foremost contributed by their kind willingness, effort, and time to review and assess this thesis and the defense. I am grateful to my reviewers Miloš Krstić, Yoram Moses, and Alex Yakovlev, as well as my defense members Stefan Haar and the president of the jury Maria Potop-Butucaru for their time and energy. I am well aware that this requires considerable effort besides the already heavily loaded days (and nights). Many, many thanks! I would additionally like to thank Stefan Haar, not only for the many helpful and nice discussion and coffees we had during my time at LSV and later LMF, but also for being so kind to be my habilitation patron. I'd also like to thank Benedikt Bollig for his advises, proofreading, and setting up the defense's technical environment and Nicole Bidoit-Tollu for her help.

Following up with my studies and PhD time at TU Wien, I'd first like to mention Andreas Steininger. He immediately sparked my interest in how circuits work and how to design good ones, not only with his catching lectures, but also with his open-minded and searching attitude. I was more than happy to write my bachelor thesis under his and Babak Rahbaran's supervision, which I greatly enjoyed. My wish to become a member of the ECS group, where he was working, was all the more clear, when I got to know Ulrich Schmid in his impressive course on distributed systems. I clearly remember the way he encouraged us to contribute to the current state-of-the-art in a homework

Chapter 1

Introduction

A central aspect of computation is mechanically, in the sense that this process follows rules, transforming binary input words into binary output words, such that input and output are related via a predefined function. The rules of the mechanical transformation naturally depend on the target machinery. Two abstract machineries are typically studied within this context.

(i) The Turing machine, an abstract machine, reads from and writes to an infinite, linear, sequentially accessible tape, and is controlled by a finite state machine. The input is presented to the machine as the tape's initial state and the output contained on the tape when the state machine enters a dedicated final state.

(ii) Circuits that comprise of untimed Boolean gates. The input is represented as respective constant signals, and the output is obtained as the signal values of dedicated gate outputs. These Boolean circuits are restricted to be purely combinational, i.e., gates are stateless, and no cycles are allowed when connecting gates.

While a Turing machine specifies an input-output relation for a potentially infinite set of inputs, a circuit does so only for inputs of the same length. Computation of a function on an infinitely large set of inputs is modeled by a family of circuits; one per input length. Care has to be taken when defining how these circuits are generated and which constraints they have to fulfill as these decisions have effects on the resulting complexity hierarchy.

The problem of determining an output functionally related to an initially presented input, however falls short of capturing reactive problems where inputs are presented along an execution. The design of controllers falls into this category: it round-wise receives inputs and responds with outputs such that the potentially infinite execution is within a predefined set of correct executions.

Machine models considered for this class of problems are typically state machines with finite or infinite number of states. Notable special cases of finite state machines are Moore machines, where outputs only depend on the current state, and Mealy machines, where outputs are determined by the current state and current input. Both play a key role for physical circuit implementations discussed in the following.

Before we start with definitions and problems, the author would like to remark that we work with a broad definition of computation in this text. In particular, we will not distinguish between one-shot input-output problems and providing a continuously executing service, as the line of separation seems to be set rather for historically reasons than by other means. While one may object that with such a definition the specificity of computer science as opposed to computer engineering, control theory, to physics or biology disappears, the author of this text sees this as an opportunity rather than a deficit.

Basic Notation

We write N = {0, 1, . . . }, N + = N \ {0}, and R + 0 = {x ∈ R | x ≥ 0}. Further, for k ∈ N + , [k] = {1, . . . , k}. For the set of Boolean values we write B = {0, 1}.

For a directed graph G = (V, E) with vertices V and edges E, we write In v ⊆ V , with v ∈ V , to denote the set of in-neighbors of v in G, and Out v ⊆ V for v's set of out-neighbors. Instead of vertices, we will sometimes speak of nodes when it is more natural, e.g., when vertices correspond to computing nodes. Likewise, we will sometimes refer to edges as links.

State Machines and Circuits

We will first make the two machine models, namely, state machines and circuits, more precise.

State machine. Consider a deterministic, finite Moore state machine, that operates in discrete rounds. Such a machine M is defined by a tuple (I, O, S, s 0 , δ, o), where I is a finite input alphabet, O a finite output alphabet, S a finite set of states, s 0 ∈ S the initial state, δ : S × I → S the transition function, and o : S → O the output function. An execution of M for a countably infinite input trace ι ∈ I ω is the sequence (ι k , s k , o k ) k≥0 , where s 0 is the initial state, o 0 = o(s 0 ), and for k ≥ 1,

s k = δ(s k-1 , ι k-1 ) o k = o(s k ) .
Execution (prefixes) of M for input traces ι ∈ I * of finite length k ≥ 0 are defined as the (unique) k-prefix of an execution of M for an input trace ι that is obtained by extending ι arbitrarily to an infinite input trace.

With the above definitions, the notion of round-wise computation lies at hand. Given an execution, round k comprises of (i) reading input ι k-1 , (ii) computing the current round's state s k based on input ι k-1 and the previous round's state s k-1 , and

(iii) computing the current round's output o k based on the current state s k .

Circuit. Likewise, a combinational feed-forward circuit, in the following simply referred to as a combinational circuit, is a directed node-labeled graph G = (V, E, g) with a finite set of nodes V partitioned into input nodes I, output nodes O, and internal nodes L, a set of signals E, i.e., edges between nodes, and a gate labeling function g that assigns to each internal or output node v, a Boolean formula with atoms in v's incoming edges. The graph is required to be acyclic, input nodes only have outgoing but no incoming edges, output nodes only incoming and no outgoing edges.

Example 1. Figure 1.1 shows a circuit with input nodes I = {1, 2}, internal nodes L = {3, 4, 5}, and output nodes O = {6, 7}.

Before defining an execution of a circuit, we need to define delay models for circuit components. We continue with some definitions towards this goal.

An event is a tuple (t, x) ∈ E = (R + 0 ∪ {-∞}) × B. We call t the event's time and x its value. If t = -∞, the event is called an initial event. A signal is a finite or countably infinite sequence of events, such that, there is exactly one initial event, event times are increasing, and within any finite interval of time only finitely many events occur. Intuitively, the list of events describes the signal's value changes over time, with an event (t, v) denoting that the signal takes value v at time t. The history of signal s at time t, denoted by s[→ t], is s with all events with times larger than t removed. We denote the set of histories of signal s at time t by Hist s (→ t). A signal's value at a time t ∈ R is the value of the latest event in s[→ t]. Note that for convenience of later definitions we also allow a signal to change to, say 1, when it already has value 1. We will call such an event redundant as the signal's value stays the same upon such an event.

Let s 1 to s k , with k ≥ 1, be signals. A delay function d with inputs s 1 to s k is a function from

R + 0 × t≥0 k i=1
Hist si [→ t] → R . Intuitively,

δ(t; s) = d(t, s 1 [→ t], . . . , s k [→ t]) (1.1)
is the delay at time t ≥ 0 of a channel with inputs s 1 to s k . By slight abuse of notation we write δ(t) for δ(t; s) if s is clear from the context, and extend δ to t = -∞ by setting δ(-∞; s) = 0 for all s.

Most widely adopted are pure delay functions, where δ(t) = c is constant in t with c ∈ R + 0 . Bounded delay functions guarantee that δ(t) ∈ [δ -, δ + ] for non-negative constants δ -and δ + .

A channel with inputs s 1 to s k is a tuple (d, f ) where d is a delay function with inputs s 1 to s k , and f the channel's Boolean function from B k → B. A channel induces an output signal o that is defined by Algorithm 1 on page 4 as follows. Given a channel with input signals s 1 to s k and time t ≥ 0, the induced output signal until time t is the output o t of Algorithm 1 with inputs s 1 , . . . , s k and t. The time t in the notation o t refers to the input event time t. It does not imply stability of the output signal until time t: in particular the induced output until time t does not necessarily have the same events with times less than time t as the induced output until time t ≥ t.

We define the induced output signal o as the limit, with τ → ∞, of the common prefixes of signals o t , where t ≥ τ . Note that a priori the existence of the limit is not guaranteed. Further, if the limit exists, it may not be a signal, as its event times may not approach ∞ while it contains an infinite number of events, or it may contain events at finite negative times. We will, however, see that for a large class of naturally occurring channels, the limit is a valid signal and an arbitrarily long prefix of it can be computed efficiently.

The algorithm. Algorithm 1 carries out the following steps:

• It generates an event sequence o, by looping over all input events, in increasing order of event times, until time t is reached. For each such input event, it adds an output event to o whose value is determined by the Boolean function f and whose time is the time τ of the input event plus the channel's delay δ(τ ).

• In case, o's events are increasing in time, o will be the returned signal (except for the removal of redundant events).

• However, event list o may contain events that are reversed in time, i.e., be of the form o = x • (t, v) • y • (t , v ) • z with t ≤ t, and sequences x, y, and z. Function doCancellations removes any such violating (sub)sequences, while looping over o's events. An example of two events in wrong order, with the result of an event being removed is shown in Figure 1.3.

• Finally, removeRedundant removes redundant events. Note that according to our definition of a signal this is not necessary for correctness. add event v ← value of first event in s for (τ, v) in s do if v = v then ensure that event is not redundant Pending.append (τ, v) . add event v ← v end if end for return Pending end function

• The final finite event list o, by construction, is a signal if the delay function guarantees that o does not contain negative finite event times.

Cancellations. Let e be an event that causes the removal of an event e , i.e., e comes after e in the event sequence o, but e has time less or equal to the time of event e . Such an event e will be removed within doCancellations in Algorithm 1. We then say that e cancels e .

Example 2. To determine the induced output signal o until time 2, we execute Algorithm 1 with inputs s and t = 2.

1. Initially, τ is set to -∞ and o = .

2. Next, the initial event (-∞ + δ(-∞; s), f (0)) = (-∞, 0) is added to o, resulting in o = (-∞, 0) . Time τ is updated to the next input event time 1.

3. Since the condition of the while-loop is fulfilled, δ is set to δ(1; s) = 1 and v to f (s(1)) = 1.

4. This results in o = (-∞, 0), (2, 1) and τ = 2.

5.

Again the loop's condition is fulfilled, resulting in o = (-∞, 0), (2, 1), (3, 0) and τ = ∞.

6. Function doCancellations returns o, since there are no events violating order.

7. Function removeRedundant returns o, since there are no redundant events.

Since, execution of the algorithm for all t ≥ 2 leads to the same output, the output signal induced by the channel is o = (-∞, 0), (2, 1), (3, 0) . First, consider the case shown in Figure 1.5 (left). Here a reordering of events with identical value occurs. A reason for this, e.g., is that the presence of an active second input leads to quicker charging of the Or gate's output, and thus shorter rising transition times.

1. Initially the output has value 0.

2. The rising transition of s 2 at time 1 results in an event (1 + δ , 1) = (4, 1) being added to o.

3.

The following rising transition of s 1 at time 2 results in an event (2 + δ , 1) = (3, 1) being added to o.

4. Thus o = [(-∞, 0), (

5. Function doCancellations returns o = [(-∞, 0), [START_REF] Manohar | Asynchronous signalling processes[END_REF][START_REF] Martin | Compiling communicating processes into delay-insensitive VLSI circuits[END_REF]], canceling the event at time 4.

6. Function removeRedundant returns o, since there are no redundant events.

Second, consider the case shown in Figure 1.5 (right) where a reordering of events with distinct values occurs. A reason for such a scenario may be a short input glitch that is suppressed at the output.

1. Initially the output has value 0.

2. The rising transition of s 2 at time 1 results in an event (1 + δ , 1) = (4, 1) being added to o. Delay model and execution of a circuit. Returning to circuits, we define: A delay model for a circuit is a collection (d v ) v∈V of delay functions. An execution of a circuit is a collection of signals, one per node v ∈ V , that fulfills the following properties.

• The signals assigned to input nodes are arbitrary.

• Let u ∈ L ∪ O be an internal or output node. Further let v 1 , . . . , v k be the incoming edges of u. Let d be the circuit's delay model. Then the signal assigned to u is the output signal induced by the channel with input signals s 1 to s k assigned to v 1 to v k , and delay function d u .

As such, the definition is not constructive and thus does not allow to generate output signals from input signals. We will, however, later on discuss constructive solutions for several practically relevant delay models. (left) An order violation between events with the same value; here 1. The event with the dotted arrow is canceled. (right) An order violation between events with opposing values. Again, the event with the dotted arrow is canceled. The second event is later removed by the algorithm, since it is redundant.

State Machine Implementations

We next discuss a well-known and practically relevant relation between state machines and circuits: state machines are implementable by circuits.

Implementation of synchronous Moore state machines. A register, or flip-flop, is a stateholding circuit element with a data input D, a clock input clk, and a data output Q. We only provide a high-level specification of a register here, as this will suffice for our purposes. Inputs and outputs are single line, and, by slight abuse of notation, we write D for the input (port) D and its signal in an execution; and similarly for the other ports. Given that the clock respects a certain minimum time between transitions, and that D does not change value within the setup time before a rising (active) clock transition at time t and the hold time after t, output Q is set to D(t) at latest after some clock-to-Q delay δ reg > 0.

Example 5. Figure 1.6 shows the behavior of a register sampling 1 and then 0. We are now in the position to combine registers and (combinational) circuits and describe the classic, clocked Moore state machine implementation shown in Figure 1.7. Input, local, and output registers have bit width large enough to hold values in the input alphabet I, state space S, and output alphabet O, respectively. With each active clock transition, input and local registers sample new values, and the (combinational) circuitry computes the next state and output. Under practically relevant delay models, the next local state and output signals will stabilize within bounded time, and are then (after an additional setup time) ready to be sampled again at the arrival of the next active clock transition.

Figure 1.8 shows the phases within a clock cycle. The red, unstable phases are conservative overapproximations of actual unstable periods, since stability depends on the combinational circuitry and register states among others. The maximum register clock-to-Q delay δ reg and the maximum local input output clk Figure 1.7: Clocked Moore state machine implementation. The dashed output register is not considered to be part of the implementation, and represents the input register of a potentially successor state machine or output logic. 1) register output stabilization, (2) propagation of outputs through combinational logic to register inputs, and (3) stable register inputs. combinational circuit's propagation time δ cir determine the duration of these phases. The minimum propagation time through the circuit, here for simplicity, is lower bounded by the trivial bound 0, requiring that the hold time is 0. Generally, designs require minimum propagation times of at least the registers' setup time.

t clk t Q t D X X X X
One easily verifies that any finite Moore state machine is implementable by a circuit in Figure 1.7, with round-wise presented inputs and round-wise generated outputs. While this approach is used extensively, it has its limitations discussed in the following section.

Abstractions Made so Far

Tempting for its simplicity, the classical synchronous state machine implementation has been widely adopted. However, limitations become apparent in certain applications. Three major foci, based on implicitly made assumptions, are: Delay bounds and steady state behavior. Only maximum and minimum circuit timing has been taken into consideration to validate clock cycle and setup/hold constraints. This allows to consider only the steady state of the combinational circuit and ignore transients.

Precise latency of gates, however, may be essential for several reasons. (i) Working with the steady state may be too conservative to obtain the intended performance (input-output latency and throughput). (ii) The steady state behavior abstracts away from internal glitches 1 . Since glitches contribute to the gates' dynamic power components, their presence or absence influences the circuit's overall power consumption.

For applications where this matters, a timing analysis with refined delay models beyond just the maximum latency may become relevant. This results in potentially less conservative bounds on clock cycle lengths and power consumption. Chapter 2 discusses this path in greater detail.

In some cases, a refined analysis and design of the above scheme is still insufficient, or prohibitively costly, to meet the design constraints. Historically, alternatives have been studied within the asynchronous circuit's community with an initial emphasis on designs that operate in presence of arbitrary delays [START_REF] Martin | Compiling communicating processes into delay-insensitive VLSI circuits[END_REF][START_REF] Martin | Synthesis of asynchronous VLSI circuits[END_REF]. A clear, formal model for such circuits and an analysis of their expressiveness was given by Manohar and Moses [START_REF] Manohar | Asynchronous signalling processes[END_REF]. For an overview on asynchronous circuits we refer the reader to [START_REF] Sparsø | Asynchronous circuit design-a tutorial[END_REF][START_REF] Myers | Asynchronous Circuit Design[END_REF]. While a general discussion of such solutions would go beyond the scope of this work, we deviate from the classical state machine implementation at several places throughout this work.

Boolean signals. So far, circuits have been defined to compute with Boolean values B = {0, 1}. In our model, a signal value s is a non-continuous function from time t to its value s(t) ∈ B at time t. Clearly, though, this is a convenient, but simplifying, abstraction of physical signal values. Classically, digital gates in electronic circuits are viewed as transforming input voltages into output voltages. In design styles like the widely-used Complementary Metal Oxide Semiconductor (CMOS) technique, signal values are continuous functions from the time to the voltage between a certain probing point and ground.

While, signals are meant to reside within clearly separated regions of low and high voltage, encoding 0 and 1, respectively, transient phases with in-between voltages are inevitable when switching between low and high. These, typically, short transient switches are normally neglected in an analysis. The simplification, however, becomes problematic if switching times become a dominant part. This may be due to (i) aggressive timing of the circuitry with only short stable phases, (ii) faults such as charge induced by ionizing particles [START_REF] Autran | Soft Errors: from particles to circuits[END_REF], or failing transistors or interconnect [START_REF] Maly | Realistic fault modeling for vlsi testing[END_REF][START_REF] Heinrich | Cmos bridges and resistive transistor faults: Iddq versus delay effects[END_REF], and (iii) metastability2 of state-holding gates [START_REF] Marino | General theory of metastable operation[END_REF][START_REF] Marino | The effect of asynchronous inputs on sequential network reliability[END_REF].

While some of these effects can be covered by more advanced delay models as discussed in Chapter 2 or by non-deterministic over-approximation of switching times, we will discuss a different approach in Chapter 3: to compute with non-binary signal values.

Stable architecture. Finally, we assumed that gates and interconnections between gates behave according to their Boolean gate and channel specifications. This neglects changes, or deviation, of intended component behavior and interconnect. While, arguably, from a modeling perspective there is no difference between modeling correct or faulty behavior, solutions that have to take into account faulty components will be different from the simple state-machine implementation in Section 1.3. Clearly, though, problems are different, too.

Depending on the problem to solve, available components, failure models, and the behavior of the environment, available solutions differ considerably. However, key to many solutions is redundant execution of computations over space and/or time. One of the fundamental problems when replicating components is to maintain the component states synchronized to a certain extent. Examples of such states are component outputs, internal component states, and a common notion of time among components.

We discuss such homogenization techniques in Chapters 4 and 5.

Algorithms as Circuits

Before discussing means of computing in absence of some of the convenient assumptions of delay bounds and steady state behavior, Boolean signals, and stable architectures, the author of this work would like to emphasize on a general view that is taken throughout the work.

For solutions to problems, algorithms are given in terms of circuits rather than pseudo-code. If pseudo-code is given, it is with the intent to comprise of simple computational and communication statements, that are amenable to implementation within circuits. Clearly though, this criterion is informal, with success or failure becoming visible only when systems are indeed mapped to target technologies. Further, the criterion depends on the intended target technology and size of the circuit. Taking the average of two numbers may be too expensive as a solution in small digital circuits, but be valid for larger digital circuits, or easy to obtain by mixing two equal volumes with a certain protein concentration, and taking the resulting protein concentration. We will thus comment on the intended target technology when it is not clear from the context.

Algorithms and circuits are thus treated interchangeably, instead of seeing circuits as implementations of algorithms. For previous work on gate-level algorithms, we refer the reader to distributed algorithms that have been shown to solve fault-tolerant distributed pulse generation. Consider a distributed system of n > 1 nodes, that can communicate with each other via binary signals whose delay is within bounds [δ -, δ + ]. Each node has a dedicated output signal; its clock output. Some of the nodes are correct, i.e., they follow the algorithm, and some are Byzantine faulty, i.e., they produce arbitrary binary output signals and communicate arbitrary binary signals to the other nodes. Communicated signals may be even different for different nodes in case the sending node is faulty.

We say a distributed algorithm, i.e., a family of circuits indexed by the set of nodes, solves fault-tolerant distributed pulse generation in presence of up to f ∈ N Byzantine nodes, if

• each correct node produces a clock signal with a cycle length, i.e., the time between two successive active transitions, within some strictly positive bounds [T -, T + ], and

• the clock skew, i.e., the maximum of the difference of time of the k th active clock transition of two nodes, over all k ≥ 1 and all pairs of correct nodes, is within some strictly positive bounds [σ -, σ + ],

given that at most f nodes are Byzantine in an execution.

The DARTS algorithm [START_REF] Függer | Fault-tolerant distributed clock generation in VLSI Systems-on-Chip[END_REF][START_REF] Függer | Reconciling fault-tolerant distributed computing and systems-on-chip[END_REF] is an example of an algorithm that solves the problem if f < n/3 and if certain constraints on node internal and external communication delays are fulfilled. The FATAL algorithm [START_REF] Dolev | Fault-tolerant algorithms for tick-generation in asynchronous logic: Robust pulse generation[END_REF] is another example of a fault-tolerant distributed pulse generation algorithm targeted at simple hardware components. In addition to being fault-tolerant, it is self-stabilizing: irrespective of the past until a time t, given that there are no more than f < n/3 Byzantine faults3 during some [t, t + T ], then the system solves fault-tolerant distributed pulse generation within [t + T s , T ] with a certain probability p(T s ) that converges to 1 as T s < T approach infinity.

A discussion on gate-level models for such algorithms is given in [START_REF] Dolev | Rigorously modeling self-stabilizing fault-tolerant circuits: An ultrarobust clocking scheme for systems-on-chip[END_REF]. Distributed gate-level algorithms in more general settings are discussed in Dolev et al. [START_REF] Dolev | Fault-tolerant distributed systems in hardware[END_REF].

Organization of this Work

The following three chapters are devoted to computing in machine models with relaxed assumptions. Chapter 2 discusses work on delay models. Chapter 3 is on computing with non-binary, but still digital, signals. Chapter 4 discusses algorithms that provide a homogeneous state despite highly dynamic architectures. Finally, Chapter 5 provides an outlook to currently ongoing research and future directions.

At the beginning of a chapter we provide a blue box that lists, and briefly sketches, the main research papers this chapter is based on. Central results of a chapter are also highlighted in green. At the end of a chapter, own work that is related to the chapter is provided in a green box.

Chapter 2

Timing

This chapter discusses results from the following research articles. We show deficiencies in previous, widely used delay models for digital circuits. In particular the propagation of glitches through circuits is not captured correctly: problems solvable in Netwonian physics are not solvable in such models and vice versa. The involution delay model is a deterministic delay model: a function from the history of signals to a delay. In this work we weaken this assumption, adding bounded non-determinism to the delay and show that the model is equivalent to the deterministic model with respect to solvability of the short pulse filtration problem variants.

Glitch Propagation

Consider a chain of combinational gates, say buffers, and a glitch propagating through the chain.

An example scenario is depicted in Figure 2.1. Following the convention of delay models and circuit executions from Chapter 1, transitions that occur in reverse order (here, falling before rising in a low signal), cancel each other and the signal value remains unchanged. In the example, the pulse shrinks in length when propagated from a to b and cancellation occurs when propagating the pulse from b to c. Such behavior is typically observed if gates or interconnect form capacitors of non-negligible capacitance that needs to be charged or discharged when the gate drives a different output value. Charging or discharging is not only responsible for the delay until sufficient voltage is available across the capacitor, but this delay also depends on charge already present in the capacitor.

Buf1

Figure 2.2 on page 13 shows a Spice simulation of a chain of 7 buffers, g10 to g16, with an input pulse applied at the first buffer input. The chain was synthesized for the 15 nm FinFET NanGate open cell library [START_REF] Martins | Open cell library in 15nm freepdk technology[END_REF], layed out and routed, and its parasitics extracted for simulation (all within the Cadence suite).

While the pulse in Figure 2.2a propagates through all buffer stages, Figure 2.2b shows a pulse that shrinks in length until it is fully canceled by the pre-last stage.

Pulses, and their propagation through a circuit will play an important role when discussing channel models. Formally, in our binary circuit model, a pulse of length ∆ > 0 at time T is a signal p with

p(t) = 1 if T ≤ t < T + ∆ 0 otherwise . ( 2.1)
A signal contains a pulse of length ∆ > 0 at time T if its event list contains the two consecutive events (T, 1) and (T + ∆, 0).

Bounded Single-history Delay Models

To facilitate a comparison between delay models we follow an approach proposed in Függer et al. [START_REF] Függer | Unfaithful glitch propagation in existing binary circuit models[END_REF][START_REF] Függer | Unfaithful glitch propagation in existing binary circuit models[END_REF], unifying several delay models. For that purpose we define bounded single-history channels. While "single-history" refers to the fact that its delay depends on the current and previous transition only, the term "bounded" will be discussed in Section 2.8.1, when we introduce unbounded single-history channels.

Definition 6 ([16]

). A bounded single-history channel is a tuple (F, f, δ), where F ∈ B specifies whether the channel is non-forgetful (F = 0) or forgetful (F = 1), f is the channel's Boolean function, and δ : R → R determines the channel's delay function d as specified in the following. The channel's function δ must fulfill:

• δ is nondecreasing. • δ(∞) = lim T →∞ δ(T ) is finite and positive.

The two variants of bounded single-history delay channels, non-forgetful and forgetful, differ in whether the time of a canceled output event has an effect on the delay for the next output event (non-forgetful) or not (forgetful). The value d(t, s[→ t]) of their delay function is given by the following inductive definition. For n ≥ 1,

• Let τ i , with i ∈ [n] and -∞ < τ 1 < τ 2 < • • • < τ n ≤ t, be the times where f (s(•)) changes value. • Let t i = τ i + d(τ i , s[→ τ i ]) for i ∈ [n -1]. Further, set t 0 = -∞.
• Let T n = τ n -t , where t is determined as follows:

-If the channel is non-forgetful, then t = t n-1 .

-If the channel is forgetful, then t = t n , with n ≤ n -1 maximal, given that the output event at time t n was not canceled by output events at times t 1 , . . . , t n-1 . The delay of a bounded single-history channel, depends only on the time since the last (nonforgetful channel) or last non-canceled (forgetful channel) output event; thus the name singlehistory. The channel is further called bounded, because of the following property: Lemma 7. The delay of a bounded single-history channel with delay function δ, is bounded. In particular it is within

• Set d(t, s[→ t]) = d(τ n , s[→ τ n ]) = δ(T n ). t i t o t 1 t 2 t 3 δ(T 4 ) τ 4 T 4 (a) Non-forgetful bounded single-history channel. t i t o t 1 t 2 t 3 δ(T 4 )
[δ(-δ(∞)), δ(∞)].
Proof. From the definition of T , it is easily verified that the parameter T for a bounded singlehistory channel is always larger than -δ(∞). In fact such a T occurs as the infimum of parameter T for the delay of the second transition in pulses of duration ε > 0, with the first transition being delayed by δ(∞) < ∞. The lemma's statement then follows from the fact that δ is nondecreasing on R.

Recall from Section 1.2 that the induced output signal until a time t does not necessarily exist. In particular the list of output events generated by Algorithm 1 may not necessarily have common prefixes for increasing times t. This may be the case if output event k ≥ 1 can cancel output event 1 ≤ < k for arbitrarily large k -≥ 1. One can, however, show that bounded single-history channels are well-behaved, and their induced output signal indeed exists.

Indeed, we will see in Lemma 17 on page 21 that bounded single-history channels, as their name suggests, have bounded delays within [-δ inf , δ ∞ ]. Combining this property with the fact that for a bounded single-history channel, an event can at most cancel the previous event, but never more, we obtained: Lemma 8 (Lemma 4 and 5 in [START_REF] Függer | Unfaithful glitch propagation in existing binary circuit models[END_REF]). Denote by S n the output event list generated by Algorithm 1 for a prefix of the input event list of length n. Further, denote by S n | t its restriction to events at times at most t.

Then, for the non-forgetful and the forgetful single-history channel, for all t ≥ 0, there exists an N ∈ N such that S n | t is constant for all n ≥ N .

Conventional Delay Models

Two widely adapted delay models are the pure delay model, also referred to as transport or constant delay model, and the inertial delay model. Both are implemented in standard circuit design frameworks. Example 9 discusses their use in the VHDL language.

Example 9. In the following a VHDL listing for a simple buffer gate with delay is given. Depending on the buffer's architecture, it uses a pure delay channel with parameter 5 ps (BUF transport), or an inertial delay channel with parameters 4 ps and 5 ps (BUF inertial) or 5 ps and 5 ps (BUF after). Y <= transport X a f t e r 5 p s ; end B U F t r a n s p o r t ; a r c h i t e c t u r e B U F i n e r t i a l of BUF i s begin Y <= r e j e c t 4 p s i n e r t i a l X a f t e r 5 p s ; end B U F i n e r t i a l ; a r c h i t e c t u r e B U F a f t e r of BUF i s begin Y <= X a f t e r 5 p s ; end B U F a f t e r ;

In terms of our model, a pure delay channel is a single-history channel with delay function

δ(T ) = δ ∞ , (2.2)
where δ ∞ is its delay. 1 The behavior of pure delay channels is identical, no matter whether they are forgetful or non-forgetful: they simply never cancel transitions. The advantage of the slightly more refined inertial delay channels is not immediate for standard synchronous designs. While correctness of classical synchronous state machine implementations indeed only rely on minimum and maximum delay, i.e., ranges for δ ∞ , inertial delays play a role for power estimates and when leaving the single-clock synchronous design path. Indeed, Unger [START_REF] Stephen | Asynchronous sequential switching circuits with unrestricted input changes[END_REF] proposed a design technique for asynchronous sequential switching circuits that relies on the availability of inertial delay channels.

Cast in our model, the delay function of an inertial delay channel is,

δ(T ) = δ ∞ if T ≥ T 0 -T 0 otherwise . (2.3)
with parameters T 0 and long-term delay δ ∞ . Figure 2.5 shows two delay functions for different long-term delays δ ∞ . Observe, the discontinuity at T = T 0 that will play a central in its analysis later on. Bellido-Diaz et al. [START_REF] Mj Bellido-Diaz | Logical modelling of delay degradation effect in static cmos gates[END_REF] proposed a more refined model, the Delay Degradation Model (DDM). The model overcomes shortcomings of the inertial delay model in that it captures gradual degradation of pulse widths by channel, rather than sudden cancellation at a certain threshold. Its delay function is,

δ(T ) = δ ∞ 1 -e -T -T 0 τ .
(2.4) Figure 2.6 shows two delay functions that differ in their long-term delay δ ∞ . By contrast to the inertial delay model, the delay function is continuous over R. The function was derived by analytic arguments of charging effects and its accuracy compared against Spice simulations. Indeed DDM achieves very good accuracy in challenging scenarios with significant degradation effects.

Glitch Propagation in Models

Starting from the three models with their goals to refine on glitch propagation in circuits, the question arises, which of these models indeed captures these phenomena. While we would intuitively rank the three models from pure delay, followed by inertial delay, and DDM for their capability to model real glitching behavior, a formal answer to this question has several advantages: 1. Accuracy of simulations. We clearly aim for more accurate simulation results with more refined models. Accuracy is measured as deviation from physical measurements, or detailed simulation models that are considered sufficiently close to real measurements. In our setting these are typically (post-layout) Spice models with extracted parasitics.

2. Impact of correctness proofs on real circuits. A correctness proof of a circuit within a model that deviates significantly from reality clearly does not imply correctness of the circuit in real-world settings. While all proposed delay models clearly deviate from reality in one or the other way, a more coarse question of whether a model deviates from reality would be to ask if an (important) problem P is solvable in this model if and only if it is solvable in reality. We termed such models faithful with respect to P [START_REF] Függer | Unfaithful glitch propagation in existing binary circuit models[END_REF].

3. Validity of circuit synthesis. The above observation also has implications on automated circuit synthesis. By analogous arguments as for correct proofs, a circuit synthesized within a model that is not faithful with respect to P may lead to circuits that fail in practice for problems that are related to P .

Short Pulse Filtration in Physical Models

Before discussing adequate problems P to prove faithfulness or non-faithfulness with respect to P , let us specify a model that we consider to capture reality. In doing so we follow Marino's work on metastability [START_REF] Marino | General theory of metastable operation[END_REF], who defined a realistic circuit as one whose voltage signals can be described in a time and value continuous system of differential equations with restrictions that, e.g., imply causality. 2 For a detailed description of the model we refer the reader to [START_REF] Marino | General theory of metastable operation[END_REF]. In our case, (normalized) voltage signals are assumed to be within [0, 1]. To map these signals to binary values, we assume the existence of thresholds l 0 , l 1 ∈ (0, 1) with l 0 < l 1 and will speak of the signal being logical b ∈ B if the signal's value is within L b , where L 0 = [0, l 0 ] and

L 1 = [l 1 , 1].
It remains to chose a problem P for which to assess whether the model is faithful with respect to P . In our case, the informal goal is to correctly model propagation of glitches, i.e., short pulses, through circuitry. Note that this question is closely related to correctly modeling metastabilityalthough, the latter is not straightforward to state in a binary-valued model. We will, see, however, that both -glitches and metastability -are indeed closely related.

Several problems lie at hand when it comes to finding typical problems where correct handling of glitches supposedly plays a role in whether a circuit solves this problem, or not. Although care must be taken on the precise specification of such problems, a fundamental component that would help solving such problems, is a single input single output circuit that filters away too short pulses at the output. In its simplest form we require that this device only works for a single positive input pulse. We termed this problem the Short Pulse Filtration (SPF) problem [START_REF] Függer | Unfaithful glitch propagation in existing binary circuit models[END_REF][START_REF] Függer | Unfaithful glitch propagation in existing binary circuit models[END_REF]. It remains to specify what filtering away means in this context -too strict definitions inevitable will lead to unsolvability in real systems. The SPF problem is specified as follows and has two variants: Definition 10 (Unbounded SPF and bounded SPF in the physical model [START_REF] Függer | Unfaithful glitch propagation in existing binary circuit models[END_REF]). Consider a circuit with a single input and a single output in the physical model. It solves unbounded Short-Pulse Filtration (SPF) if:

(i) If the input signal is constantly logical 0, then so is the output signal. (ii) There exists an input signal such that the output signal attains logical 1 at some point in time.

SPF i o

(iii) There exists some fixed ε > 0 such that, if the output signal is not interpreted as logical 1 at two points in time t and t with tt < ε, then it is not logical 1 at any time in between t and t .

It solves bounded SPF if additionally:

(iv) There exists a time T > 0 such that, if the input signal switches to logical 1 by time t, then the output signal value is either logical 0 or logical 1 at time t + T and remains logical 0 respectively logical 1 thereafter.

Conditions (i) and (ii) outrule trivial solutions to the problem that simply set their output to constant 0 or 1. Condition (iii) prevents a solution from producing an output pulse of length less than a predefined ε; thus the problem's name. Condition (iv) further requires the circuit output to stabilize within bounded time.

We will next discuss both SPF variants in Marino's model of physical circuits.

Impossibility of Bounded SPF

In [START_REF] Függer | Unfaithful glitch propagation in existing binary circuit models[END_REF] we showed by reducing the problem of building a bistable storage element that stabilize in bounded time to building a circuit that solves bounded SPF:

Theorem 11 ( [START_REF] Függer | Unfaithful glitch propagation in existing binary circuit models[END_REF]). No physical circuit solves bounded SPF.

For the proof, let us define a single-input bistable element in the physical circuit model as a circuit with a single input and a single output that fulfills properties (i) and (ii) of SPF, and additionally:

(iii') If the output is logical 1 at some time t, it also remains logical 1 at all times larger than t.

Analogous to the bounded SPF problem, a circuit solves the single-input bistable element stabilizing within bounded time, if additionally (iv) of SPF holds.

Indeed, Marino's Theorem 3 in [START_REF] Marino | General theory of metastable operation[END_REF] then directly implies: [START_REF] Függer | Unfaithful glitch propagation in existing binary circuit models[END_REF]). In the physical circuit model, there is no single-input bistable element stabilizing within bounded time.

Corollary 12 ([
To show Theorem 11, it remains to reduce a single-input bistable element stabilizing within bounded time to a bounded SPF circuit. Figure 2.7 shows such a reduction by a circuit that uses a bounded SPF circuit to build a respective single-input bistable element. Its idea is to use a storage loop, formed by the Nor with the Inv feedback, to capture a 0-1-0 pulse, and permanently output 1. The storage loop does not fail, due to too short input pulses, because of property (iii) of the SPF. Finally, boundedness carries over from the bounded SPF to the single-input bistable element.

Possibility of Unbounded SPF

For the weaker unbounded SPF problem, we showed:

Theorem 13 ([16]

). There is a physical circuit that solves unbounded SPF.

L 0 L 1 Time [ns] [V]
Figure 2.9: Spice simulations of a storage loop in presence of short input pulses (blue). The storage loop gets metastable, resulting in its internal signal staying arbitrarily long near the metastability point (bundled green), before it resolves to stable 0 or 1. Once the signal leaves the metastable region (red area), it resolves quickly, however. Regions L 0 and L 1 for voltages that are interpreted as logical 0 and logical 1 by the successive low threshold inverter are marked in the figure. Figure 2.9 provides an intuition why the circuit indeed solves the unbounded SPF problem: The (blue) input signal may lead to a metastable upset of the storage loop, resulting in the (green) signal at the low threshold inverter input. However, the low-threshold inverter interprets a sufficiently large voltage range, including the metastable region of the storage loop, as a logical 1 and thus maps it to 1. Metastable upsets thus lead to arbitrarily late, but not spurious, transitions at the inverter output. One easily verifies that the circuit thus fulfills all properties required for solving unbounded SPF.

Short Pulse Filtration in Binary-valued Models

We are ready to state unbounded SPF and the bounded SPF from Definition 10 in binary-valued circuit models. Further, we introduce a third problem, the eventual SPF problem. Definition 14 (Unbounded SPF, bounded SPF, and eventual SPF in binary-valued models [START_REF] Függer | Unfaithful glitch propagation in existing binary circuit models[END_REF]). Consider a circuit with input i and output o in the binary-valued model. The circuit solves unbounded Short-Pulse Filtration (SPF) if:

(w) For every pulse p, there exists an execution that has p as the input signal. (Well-formedness) (i) In all executions, if the input signal is constant zero, then so is the output signal. (No generation)

(ii) There exist a pulse p such that, in all executions with p as the input signal, the output signal is not the constant zero signal. (Nontriviality)

(iii) There exists an ε > 0 such that, in all executions, the output signal does not contain a pulse of length less than ε. (No short pulses)

The circuit solves bounded SPF if additionally:

(iv) There exists a K > 0 such that, in all executions with a pulse as the input signal whose last event is at time T , the output signal does not change anymore after time T + K. (Bounded stabilization time)

The circuit solves eventual SPF if conditions (w), (i)-(iii), and the following condition hold:

(iv') There exists an ε > 0 and a K > 0 such that, in all executions with a pulse at time T as the input signal, the output signal does not contain a pulse of length less than ε after time T + K.

(Eventually no short pulses)

One easily verifies that the problems are ordered as eventual SPF ≤ unbounded SPF ≤ bounded SPF with respect to their difficulty: bounded SPF implies unbounded SPF, which itself implies eventual SPF.

We say a circuit model is faithful with respect to glitch propagation if within the model bounded SPF is not solvable, and bounded SPF is solvable.

Unfaithful Delay Models

While the non-faithfulness of the discontinuous inertial delay channels may not come as a surprise, a much larger class of channels has difficulties capturing glitch propagation effects adequately: Theorem 15 ( [START_REF] Függer | Unfaithful glitch propagation in existing binary circuit models[END_REF]). No circuit model with bounded single-history channels is faithful with respect to glitch propagation.

The proof is separated into three cases of bounded single-history channels, each of which is sketched in the following sections.

Constant Delay Channels

Constant delay channels are widely used in circuit design. The following theorem shows that they are not faithful, however.

Theorem 16 ([16]). No circuit solves unbounded SPF with only constant delay bounded single history channels.

The proof is based on the observation that a circuit that comprises only of constant delays "samples" the input signals at certain, discrete, times, only. Assume a circuit that solves SPF and let i be its input and o its output. Then for every t ≥ 0, o(t) depends only on a finite set of input values i(t-τ 1 ), i(t-τ 2 ), . . . , i(t-τ k ), with τ 1 , . . . , τ k > 0. Changes of the input signal that happen between these times thus get unnoticed by the current output value. However, at certain times t, the set of input values grows. The proof now relies on choosing a time t where the set is guaranteed to not grow within an environment of length ε > 0, and changing the input signal to produce an arbitrarily short pulse at the output -making use of the previously established indistinguishably argument for inputs.

Non-Constant Forgetful Channels

For a bounded single-history delay function δ, let

δ ∞ = lim t→∞ δ(t)
(2.5)

δ inf = lim t→0 + δ(-δ ∞ + t) . (2.6)
The notation δ inf , for infimum delay, as well as the notation of a bounded single-history channel is due to the following result: Lemma 17 ([16]). All events produced by a bounded single-history channel are delayed by times within

[δ inf , δ ∞ ].
For a bounded single-history channel c, that is either forgetful or non-forgetful, let

γ(c) = inf {∆ > 0 | δ -δ ∞ + δ(∆ -δ ∞ )} .
(2.7)

We then showed that: [START_REF] Függer | Unfaithful glitch propagation in existing binary circuit models[END_REF]). Let c be a non-forgetful or a forgetful bounded single-history channel with initial value 0. The following statements are equivalent: (i) γ(c) > 0, (ii) c is not a constant-delay channel, (iii) There exists an input pulse, such that the output of c is the zero signal.

Lemma 18 ([
One can then show for forgetful bounded single-history channels: [START_REF] Függer | Unfaithful glitch propagation in existing binary circuit models[END_REF]). Let c be a non-constant-delay forgetful bounded single-history channel with initial value 0. Let s be a signal that does not contain pulses of length greater or equal to γ(c) and that is not eventually equal to 1. Then the output of c with input s is the zero signal.

Lemma 19 ([
The above lemma can finally be applied to show that the circuit shown in Figure 2.8 on page 19, except with a standard inverter with the non-constant forgetful bounded single-history channels instead of the low-threshold inverter, can be used to solve bounded SPF. We thus obtain: Theorem 20 ( [START_REF] Függer | Unfaithful glitch propagation in existing binary circuit models[END_REF]). Let c * be a non-constant-delay forgetful bounded single-history channel. Then there exists a circuit solving bounded SPF whose channels are either constant-delay channels or c * .

Non-Constant Non-forgetful Channels

The proof for the non-constant non-forgetful case is by dissecting into three subcases for the delay function δ. The cases differ in how the function behaves at -δ inf .

• There exists a t > -δ inf such that δ(t) < δ ∞ . From the fact that δ(t) goes to δ ∞ with t → ∞, we have that δ is non-constant within the subdomain (-δ inf , ∞).

• Otherwise, for all t > -δ inf , it is δ(t) = δ ∞ . Either, -δ is continuous at -δ inf , i.e., at -δ inf its left limit equals its right limit, or

-δ is non-continuous at -δ inf .
For all three cases, one can construct (three different) circuits that solve SPF. The idea underlying all circuits is to produce pulses that flank the actual input pulse, and that are shifted by a uniformly lower bounded ε > 0 in time by the presence of an input pulse. This shift is then transformed into a steady state change via a storage loop. We refer the reader to [START_REF] Függer | Unfaithful glitch propagation in existing binary circuit models[END_REF] and the extended arxiv version for a description of the circuits and their correctness proofs. We thus obtain: Theorem 21 ( [START_REF] Függer | Unfaithful glitch propagation in existing binary circuit models[END_REF]). Let c * be a non-constant-delay non-forgetful bounded single history channel with initial value 0. Then there exists a circuit solving SPF whose channels are all either constantdelay channels or c * .

A Faithful Delay Model

The following section is based on [START_REF] Függer | A faithful binary circuit model[END_REF][START_REF] Függer | Towards binary circuit models that faithfully capture physical solvability[END_REF], where we show that faithful delay models exist.

Central to the new model is a modification of bounded single-history channels from Section 2.2 to so called unbounded single-history channels. We will give a definition of these channels in Section 2.8.1. In search for faithful subclasses of unbound single-history channels, we start with a simple physical model of the effects responsible for pulse shortenings in Section 2.8.2 and work our way towards delay functions from there.

Unbounded Single-history Channel

Definition 6 on page 12 formalized bounded single-history channels, with δ's domain being R. Like bounded single-history channels, unbounded single-history channels are defined via their delay function δ (respectively two delay functions δ ↓ and δ ↑ ) and an initial value. The parameter T of the delay function is defined analogously to the parameter T for bounded single-history channels. We consider only non-forgetful channels, here, however.

The major difference of unbounded to bounded channels is that the delay function's domain is not R, but a subset. Along the work in [START_REF] Függer | Towards binary circuit models that faithfully capture physical solvability[END_REF], we define: Definition 22. An unbounded single-history channel is defined analogously to a bounded singlehistory channel, except that its two delay functions (up and down) are strictly increasing concave functions of the form

δ ↑ : (-δ ↓ ∞ , ∞) → (-∞, δ ↑ ∞ ) and δ ↓ : (-δ ↑ ∞ , ∞) → (-∞, δ ↓ ∞ ) with finite δ ↑ ∞ = lim T →∞ δ ↑ (T ) and δ ↓ ∞ = lim T →∞ δ ↓ (T ).

Analog Channel Model

Consider a channel with a successive identity gate -the generalization to other Boolean gates is straightforward by modifying the Boolean behavior. The channel itself is driven by a predecessor gate. Assume that V gnd = 0 V and V dd = 1 V . Figure 2.10 on page 23 depicts the schematic of a simple equivalent circuit.

The predecessor gate output is modeled as an amplifier with infinite amplification and a prespecified discretization voltage V th . Its output is a single bit digital signal u i . The amplifier itself is not part of this channel, however, and is only shown to depict the input environment. The binary signal u i is then delayed by constant time T p , obtaining the binary signal u d . With the occurrence of a rising transition of u d , the following analog switching element follows its rising switching waveform f ↑ from its current (voltage) state onwards, until a falling transition occurs, and it reacts by following the falling switching waveform f ↓ from its current voltage onwards, etc. The resulting signal is an analog signal u r . The signal is finally discretized again by an amplifier, resulting in the channel-gate output signal u o . This signal potentially is the input of a downstream gate, or a circuit output. Figure 2.10 (below subfigure) also shows the delays δ ↑ (T 1 ) and δ ↓ (T 2 ) that result for the first and second transition of the input signal u i to the output signal u o .

In [START_REF] Függer | A faithful binary circuit model[END_REF] we have shown how the switching waveforms can be translated into delay functions that result in the same digital behavior. We start from the ansatz,

δ ↑ (T ) = -f -1 ↑ (f ↓ (T )) δ ↓ (T ) = -f -1 ↓ (f ↑ (T )) , (2.8)
where f ↑ is continuous and strictly increasing and f ↓ is continuous and strictly decreasing.

In the above formula, e.g., at a rising transition, δ ↑ (T ) returns the time by which f ↑ has to be shifted so that the analog output signal u r remains continuous with respect to the output signal caused by the previous falling transition. We further need that rising and falling switching waveforms start at analog voltages 0 and 1 respectively, i.e.,

f ↑ (0) = 0 and f ↓ (0) = 1 . + - u i T p u d u r + - V th u o 1V 0V ∞ 1V 0V ∞ u(t) t V th u i u d u o f ↓ f ↑ T 1 δ ↑ (T 1 ) T 2 δ ↓ (T 2 )
Figure 2.10: Physical, analog channel model based on continuous rising f ↑ and falling f ↓ switching waveforms. From [START_REF] Függer | A faithful binary circuit model[END_REF].

Further, they are required to be full-swing, i.e., lim

t→∞ f ↑ (t) = 1 and lim t→∞ f ↓ (t) = 0 .
Incorporating both into our ansatz, yields a revised ansatz:

δ ↑ (T ) = -f -1 ↑ (f ↓ (T + δ ↓ ∞ )) + δ ↑ ∞ δ ↓ (T ) = -f -1 ↓ (f ↑ (T + δ ↑ ∞ )) + δ ↓ ∞ , (2.9)
where

δ ↑ ∞ = lim T →∞ δ ↑ (T ) δ ↓ ∞ = lim T →∞ δ ↓ (T ) .
From Figure 2.10 one readily observes for the above two quantities,

δ ↑ ∞ = T p + f -1 ↑ (V th ) and δ ↓ ∞ = T p + f -1 ↓ (V th )
First order low pass filter. As an example, consider f ↑ and f ↓ to result from a first-order RC low pass filter behavior. Then,

f ↓ (t) = 1 -f ↑ (t) = e -t/τ ,
where τ is the RC time constant. Using (2.9), we obtain the delay function of a so-called expchannel as being

δ ↑ (T ) = τ ln(1 -e -(T +Tp-τ ln(V th ))/τ ) + T p -τ ln(1 -V th ) δ ↓ (T ) = τ ln(1 -e -(T +Tp-τ ln(1-V th ))/τ ) + T p -τ ln(V th ) . ( 2

Involution Channels

In [START_REF] Függer | A faithful binary circuit model[END_REF] we introduced a new channel type, the so called involution channels, that are defined as follows:

Definition 23 ( [START_REF] Függer | A faithful binary circuit model[END_REF]). An involution channel is an unbounded single-history channel with

-δ ↑ -δ ↓ (T ) = T and -δ ↓ -δ ↑ (T ) = T (2.11)
for all applicable T .

The name involution channel is due the fact that, in case δ ↑ = δ ↓ = δ, function -δ is an involution, i.e., is self-inverse.

All delay functions from involution channels are necessarily continuous. For simplicity, we also assumed them to be differentiable -δ being concave thus implies that its derivative δ is continuous and monotonically decreasing. While this is a restriction of the general case, the underlying motivation was that delay functions in physical circuits will most likely be continuous in their behavior.

In the following we will discuss our main result from [START_REF] Függer | A faithful binary circuit model[END_REF] that render involution channels interesting candidates for faithful delay channels: Theorem 24 ( [START_REF] Függer | A faithful binary circuit model[END_REF]). The binary circuit model with involution channels is faithful with respect to glitch propagation.

Central Properties of Involution Channels

As a first observation, note that δ ↑ and δ ↓ are not independent of each other. The timing behavior of involution channels is fully determined by either one of the delay functions, as δ ↑ (T ) = -δ -1 ↓ (-T ) (and similarly for δ ↓ ).

Further, so called strictly causal channels will play a role to show uniqueness of executions. As we will see from Lemma 27, strictly causal channels have a minimum positive delay which enables constructive generation of executions; a central property for the existence of algorithms that simulate circuits with such channels.

Definition 25 (Strict causality [START_REF] Függer | A faithful binary circuit model[END_REF]). An involution channel is strictly causal if δ ↑ (0) > 0.

One observes from (2.11) and the functions being strictly increasing that a channel is strictly causal if and only if δ ↓ (0) > 0, For the special case of an exp-channel, strict causality is solely determined by T p as follows:

Lemma 26 ( [START_REF] Függer | A faithful binary circuit model[END_REF]). An exp-channel is strictly causal if and only if T p > 0.

The next lemma identifies an important parameter δ min of a strictly causal involution channelthe minimum delay of any transition that will not be canceled, as we will show in Lemma 28. By contrast, transitions that will be canceled very well can (and in fact we show that they will) have delays less than δ min . Lemma 27 ([18]). A strictly causal involution channel has a unique δ min defined by

δ min = δ ↑ (-δ min ) = δ ↓ (-δ min ) ,
which is positive. For exp-channels, δ min = T p . For the derivative, we have

δ ↑ (-δ ↓ (T )) = 1/δ ↓ (T ) ⇒ δ ↑ (-δ min ) = 1/δ ↓ (-δ min ) .
From this result, we finally established a central relation of δ min to the minimum channel delay of non-canceled transitions: Lemma 28 ( [START_REF] Függer | A faithful binary circuit model[END_REF]). Let t n and t n+1 be the times of the nth and (n + 1)th input transitions. The following are equivalent:

1. The nth and (n + 1)th pending output transitions cancel.

2. t n+1 ≤ t n + δ n -δ min 3. δ n+1 ≤ δ min

Possibility of Unbounded SPF

To show faithfulness of the involution channels with respect to glitch propagation, we need to show that, within this delay model: (i) there exists a circuit that solves unbounded SPF, and (ii) that there is no circuit that solves bounded SPF. We start by showing the former:

Theorem 29 ([18]

). There is a circuit that solves unbounded SPF.

Its proof is constructive in the sense that it provides the circuit that solves unbounded SPF. It is shown in Figure 2.12. Interestingly, the circuit is in accordance with the circuit used to show that unbounded SPF is solvable in physical circuits.

C i high TH o Figure 2
.12: A circuit solving unbounded SPF, consisting of an Or gate fed-back by channel C, and an exp-channel HT implementing a high-threshold buffer. From [START_REF] Függer | A faithful binary circuit model[END_REF].

For the proof, we proceed to show the following theorem, that characterizes the circuit's Or gate output behavior with respect to the input pulse. It shows that positive input pulses that have length less than ∆ 0 result in output pulse trains that degrade to eventually being constant 0, longer input pulses lead to pulse trains whose pulses grow to eventually being constant 1, and input pulses of length exactly ∆ 0 result in an output that oscillates forever. Theorem 30 ([18]). The fed-back Or gate with a strictly causal involution channel has the following output when the input pulse has length ∆ 0 :

• If ∆ 0 > ∆0 , then the output is eventually constant 1.

• If ∆ 0 < ∆0 , then the output is eventually constant 0.

• If ∆ 0 = ∆0 , then the output after the initial pulse ∆ 0 is a periodic pulse train with uptime ∆1 , period κ and duty cycle3 γ = ∆1 /κ < 1.

Furthermore, the stabilization time in the first two cases is in the order of log a (1/|∆ 0 -∆0 |) with a = 1 + δ ↑ (0).

To show Theorem 29, it remains to show that the signal generated by the feedback-Or gate is properly filtered by the high-threshold Inv. In particular all eventually vanishing pulse trains must be filtered out and produce a constant 0 signal at the output. Towards this goal, we showed that exp-channels have such filtering properties: Lemma 31 ( [START_REF] Függer | A faithful binary circuit model[END_REF]). Let Θ > 0 and Γ ∈ [0, 1). Then, there exists an exp-channel C such that every finite or infinite pulse train with pulse lengths (Θ i ) i≥0 and duty cycles (Γ i ) i≥0 , that fulfills

• Θ i ≤ Θ, for i ≥ 0, and
• Γ i ≤ Γ, for i ≥ 1
is mapped to the zero signal by channel C.

Theorem 30 and Lemma 31 finally show Theorem 29.

Impossibility of Bounded SPF

The idea to show that no circuit solves bounded SPF has similarities to Marion's work on metastability [START_REF] Marino | General theory of metastable operation[END_REF], showing that no bistable circuit is metastability-free. It first defines a metric space in which (i) circuits are shown to be continuous functions from inputs to outputs, and (ii) argues that the problem to be solved requires a non-continuous function. While in Marino's work this problem is the problem of building a bistable it is solving bounded SPF in our case. Metric spaces are fundamentally different though since our signals are binary as opposed to the continuous valued signals in [START_REF] Marino | General theory of metastable operation[END_REF].

Continuity of Channels.

In [START_REF] Függer | A faithful binary circuit model[END_REF] we showed that strictly causal unbounded single-history channels are continuous within a certain metric space. Towards this goal, we define s

C (s 1 ) ≤ f C (s 2 ).
The proof is by induction on the input transitions of s 2 and uses the fact that delay functions are non-increasing in parameter T . Monotonicity of T for two corresponding transitions in s 1 and s 2 is due to the assumption that s 1 ≤ s 2 . Care has to be taken in that s 2 may contain pulses that do not exist in s 1 : if so, we simply create ones (for analysis) in s 1 .

One may next define a measure for signals, and from this, a distance between signals: [START_REF] Függer | A faithful binary circuit model[END_REF]). Let time T ≥ 0. For a signal s denote by µ T (s) the measure of the set {t ∈ [0, T ] | s(t) = 1}. For any two signals s 1 and s 2 , we define their distance up to time T by

Definition 33 ([
d T (s 1 , s 2 ) = µ T (|s 1 -s 2 |).
Given a strictly causal unbounded single-history channel, it remains to show how the distance between output pulses changes if input pulses are transformed. We state one of these bounds below. For a detailed analysis we refer the reader to [START_REF] Függer | A faithful binary circuit model[END_REF]. Lemma 34 ([18]). Let T ≥ 0 be a time, s be a signal that is eventually constant 0 and, C be a strictly causal unbounded single-history channel. Then, adding a 0-1-0 pulse of length ε 1 ≥ 0 at the last transition of s (thus extending the signal) or after it (thus resulting in a new pulse), and calling the new signal s , we have

µ T (f C (s )) ≤ µ T (f C (s)) + 1 + δ ↓ (-δ min ) ε 1 .
From the above lemma, showing that small extensions have small effects on the measure of a signal, and similar lemmas that study measure and the distance changes in presence of input signal changes, we finally obtain: Theorem 35 ( [START_REF] Függer | A faithful binary circuit model[END_REF]). Let C be a strictly causal unbounded single-history channel and let T ≥ 0. Then, the mapping s → f C (s) is continuous with respect to the distance d T .

Impossibility in combinational feed-forward circuits. Combinational feed-forward circuits by definition do not contain storage loops. Any output signal of such a circuit is obtained by a finite application of channel functions and Boolean functions to the input signals. Boolean functions are easily seen to be continuous in the metric space with distance d T , where T ≥ 0. Theorem 35 showed, that channel function, are, too. Since the composition of continuous functions is continuous, and by choosing T arbitrarily large, we can show that a combinational feed-forward circuit cannot solve bounded SPF until time T since solving this problem would require a circuit with a discontinuous input-to-output function. It follows that:

Theorem 36 ( [START_REF] Függer | A faithful binary circuit model[END_REF]). No forward circuit solves bounded SPF.

Impossibility in general circuits. The restriction to purely combinational circuits is strong. However, we showed that the case of general circuits can be reduced to combinational feed-forward circuits. The principal idea is to simulate a general circuit by a combinational circuit. Central to the simulation argument is that the existence of a combinational circuit that produces the same output events as the original general circuit can be shown. However, the simulation relation a priori only holds until a certain event number N ≥ 0. Making use of the strict causality, and thus a strictly positive δ min > 0, one can relate N to a time T ≥ 0 until when the combinational circuit simulates output signals correctly. Choosing T arbitrarily large, we finally obtained: Theorem 37 ( [START_REF] Függer | A faithful binary circuit model[END_REF]). No circuit solves bounded SPF.

Experimental Evaluation

While faithfulness as previously discussed is a primary requirement when it comes to correctness of circuits, it does not yet separate quantitatively good models from those that do not provide reliable quantitative results. Clearly, though, a tradeoff between (time, space, conceptual) complexity and accuracy has to be taken into account for any model that strives for accuracy. While detailed Spice models are typically considered the golden standard in circuit models, they arguably are too coarse for detailed predictions that include non-electrical properties, e.g., behavior under radiation and mechanical stress, and too slow for larger circuit simulations and formal verification. In [START_REF] Najvirt | Experimental validation of a faithful binary circuit model[END_REF], we studied how close involution models come to Spice models and physical implementations in terms of predicting transition times in digital circuits. In a recent work in [START_REF] Öhlinger | The involution tool for accurate digital timing and power analysis[END_REF] we compared the involution model to other delay models and Spice simulations. The simulations are made with a toolsuite that was designed to integrate the involution model into a standard design flow.

As a test circuit for the comparison in [START_REF] Najvirt | Experimental validation of a faithful binary circuit model[END_REF] we used a custom UMC-90 ASIC [START_REF] Hofbauer | Pulse shape measurements by on-chip sense amplifiers of single event transients propagating through a 90 nm bulk CMOS inverter chain[END_REF] that comprises an inverter line, tapped with low-intrusive high-speed on-chip analog amplifiers to observe the signal traveling along the line. By applying fast, successive input transitions to the line's input, we were then able to trace potential degradation effects of the traversing pulses.

Q 1 Q 2 Q 3 Q 4 Q 5 Q 6 Figure 2
.13: Schematics of the ASIC used for experimental setup. It comprises of an inverter chain with analog high-speed sense amplifiers for measurements along the chain. From [START_REF] Najvirt | Experimental validation of a faithful binary circuit model[END_REF].

experimental setup. The inverters comprise of 700 nm × 80 nm (WxL) pMOS and a 360 nm × 80 nm nMOS transistors with threshold voltages of 0.29 V and 0.26 V. Nominal V dd = 1 V.

The probing amplifiers are attached to a high-speed real-time oscilloscope (50 Ω input) to log traces for later offline analysis in custom Matlab scripts. The measured amplifier gain is 0.15, with an overall -3 dB cutoff frequency of approximately 8.5 GHz. Their input load is equivalent to 3 Inv. Independent power supplies and grounds for inverters and amplifiers was used to reduce measurement noise and simplify differential voltage readout. To reduce temperature effects, the PCB with the directly bonded die has been mounted on a Peltier-cooled copper heat sink.

Figure 2.14 shows the readout at the oscilloscope (12 GHz Tektronix TDS 6154B real-time oscilloscope, 4-channel sampling rate of 20 GS/s). The input was generated with a 3.35 GHz Agilent 81134A pulse/pattern generator. The figure also shows corresponding simulated traces from Spice models that have been extracted from the synthesized design and that were calibrated to the analogue behavior of the amplifiers. Observe that the measured and simulated results match well. This became important for high frequency inputs near nominal voltages of V dd = 1 V, since the analog amplifiers were too slow to observe these undistorted by measurements. We thus had to resort to simulations for these scenarios. In the scenario in Figure 2.14, V dd = 0.6 V for this reason.

0 1 2 3 4 -0.1 0 0.1 [ns] [V] Meas. Sim.
1 , Q 3 , Q 5 (bottom, shifted by -V dd ) and Q 2 , Q 4 , Q 6 (top), with V DD = 0.6 V.
The lower output voltage is due to the amplifier gain of 0.15. From [START_REF] Najvirt | Experimental validation of a faithful binary circuit model[END_REF].

By applying an input pulse with varying width, and logging the transition times, one may extract δ(∞) and δ(T ) for varying T ∈ R. Depending on whether the pulse is positive or negative, the falling or rising delay function can be extracted. Figure 2.15 shows the resulting delay function. The positive arm has been measured, and the negative arm obtained by mirroring along y = -x. Observe the smooth transition at this diagonal as predicted from the involution delay model. We also draw a fitted DDM delay function for comparison.

0 0.5 1 -1 -0.5 0 T [ns] δ(T ) [ns] δ ↓ (T ) δ ↑ (T ) δ ↓ (T ) δ ↑ (T ) DDM ↓ Figure 2
.15: Measured δ ↓ (blue) and δ ↑ (red) for UMC-90 inverter chain for V DD = 0.6 V , which support the involution hypothesis. By contrast, there is no perfect fit for the exponential DDM delay function (dashed green). From [START_REF] Najvirt | Experimental validation of a faithful binary circuit model[END_REF].

Finally, Figure 2.16 shows a longer input trace with high-frequency pulses to ensure that charging effects play a role in the propagation delay. Observe that some of the pulses are already filtered away at Inv4, while others are filtered at Inv6. This effect cannot be obtained with classical pure delay models. While the solid blue lines show the traced voltage signal, blue and red arrows indicate signal transitions according to the involution delay model (blue) and the DDM (red). Both the involution delay model and DDM match the measured signal transitions with great accuracy. . From [START_REF] Najvirt | Experimental validation of a faithful binary circuit model[END_REF].

While measurements had to be run at reduced V dd to slow down inverter delays, we used the measurements to also calibrate a Spice model. In the Spice simulations nominal V dd runs could then be generated to validate if the circuit also behaves according ot the involution delay model at nominal operation conditions. Our delay model showed great accuracy at nominal voltage, too.

Finally, the same inverter line was synthesized in the UMC-65 nm process and Spice simulations used to check accuracy of the involution delay model. Our delay model again showed great accuracy. Figure 2.17 shows the inverters' delay functions obtained for different V dd .

-0.5

0 0.5 1 -1 -0.5 0 T [ns] δ(T ) [ns] 0.8 V 1 V 1.2 V DDM Figure 2.17: Simulated δ ↓ for UMC-65 inverter chain for V dd ∈ {0.8, 1, 1.2} V. DDM fitting for V dd = 1.2 V .

Noise

All delay models presented in this chapter are deterministic: given an input trace, there is a unique output trace that is compliant with this input. While non-determinism can be obtained by varying channel parameters from execution to execution, such models rather account for variations in production than for dynamic noise sources like changes in voltage, temperature, wear-out, etc. In fact we will discuss high-frequency voltage changes, so called voltage droops, in greater detail in Chapter 3. Voltage droops result in rapid changes in gate propagation delays and -as such -are not covered by the current model.

A first path to broaden the model to include varying delay functions, is to introduce additional parameters. For example, a gate with delay function δ : R → R may be generalized to a family of delay functions (δ v ) v∈[0,1] with voltage v ∈ [0, 1] as an additional parameter. Care has to be taken to ensure consistent switching between the delay functions for this approach.

Another approach is to allow a limited additive noise term, resulting in a delay function δ + η, for η ∈ [η min , η max ]. It is this path that was followed in [START_REF] Függer | A faithful binary circuit model with adversarial noise[END_REF]. Rather than assuming a certain probabilistic noise model, we let the adversary arbitrarily chose η ∈ [η min , η max ] for each transition. While, we conjectured that the involution delay model does not allow for any additive noise, it turned out that a significant amount of noise could be handled by the model without losing its faithfulness property. This is in particular surprising as additive noise gives the adversary not only the possibility to shrink and increase pulse sizes, but also to cancel pulses that would otherwise not be canceled and de-cancel pulses that would be canceled.

To show that the involution channel with noise is faithful with respect to glitch propagation, one has to show that (i) bounded SPF cannot be solved in this model, and (ii) unbounded SPF can be solved in the model. Direction (i) immediately follows from the result for the involution model: Whatever circuit we design, the adversary may choose η = 0, resulting in executions in the involution delay model. From Theorem 37 on page 27 we, however, have that this set of executions does not fulfill the requirements of bounded SPF.

It remains to show the more involved direction (ii). Without going into details on the proofs we mention that the possibility result of showing that unbounded SPF is solvable within such a channel model relies on the same circuit, shown in Figure 2.12, that also solves unbounded SPF in the involution channel model and in the Newtonian physical model. While not mathematically relevant, this is reassuring as it increases confidence that the possibility results do not rely on peculiarities of the models that could not be used to build real physical circuits.

As expected, faithfulness does not hold for arbitrary noise. For a strictly causal involution channel, we showed in [START_REF] Függer | A faithful binary circuit model with adversarial noise[END_REF] that faithfulness holds if the noise interval η fulfills

η max + η min < δ ↓ (-η max ) -δ min ,
where δ min is the unique value for which δ ↑ (δ min ) = δ min = δ ↓ (δ min ) > 0; see Lemma 27 on page 25.

Further reading. The work by Öhlinger et al. [START_REF] Öhlinger | The involution tool for accurate digital timing and power analysis[END_REF] discusses a tool that integrates the involution delay model into circuits specified in VHDL, and carry out simulations within existing, commercial digital simulation frameworks. The work by Maier et al. [START_REF] Maier | Transistor-level analysis of dynamic delay models[END_REF] discusses properties of involution delay functions as emerging from transistor-level properties as opposed to the simplified first-order RC charging considerations for exp-channels presented in this chapter.

Chapter 3

Non-binary Signals

This chapter discusses results from the following research articles.

• [START_REF] Friedrichs | Metastability-containing circuits[END_REF] Friedrichs, Függer, Lenzen. Metastability-containing circuits. IEEE Transactions on Computers, 67 [START_REF] Heinrich | Cmos bridges and resistive transistor faults: Iddq versus delay effects[END_REF], 2018.

Traditionally, synchronous designs lower the probability of metastable setups by waiting long enough. Since waiting costs time, latency is traded for reliability in this case. We show that this is not a necessity, and that rather than to wait, one can compute with metastable values.

• [29] Függer, Kinali, Lenzen, Polzer. Metastability-aware memory-efficient time-to-digital converter. In IEEE International Symposium on Asynchronous Circuits and Systems (ASYNC), pages 49-56, 2017.

The work applies the principles of metastability-containing circuit design from [START_REF] Friedrichs | Metastability-containing circuits[END_REF] and discusses three digital time-to-digital converters (TDCs). The designs provide means to reuse TDCs for high-frequency measurements, are memory efficient, and are particularly well-suited for downstream metastability-containing logic.

• [30] Tarawneh, Függer, Lenzen. Metastability tolerant computing. In IEEE International Symposium on Asynchronous Circuits and Systems (ASYNC), pages 25-32, 2017. This work applies the principles of metastability-containing circuits to state machines. At the example of a Network-on-Chip (NoC) router, we show that such state machines may lead to higher performance while maintaining reliability constraints.

• [31] Függer, Kinali, Lenzen, Wiederhake. Fast all-digital clock frequency adaptation circuit for voltage droop tolerance. In IEEE International Symposium on Asynchronous Circuits and Systems (ASYNC), pages 68-77, 2018.

Particularly interesting for applications of metastability-containing circuits are those that involve control with very low latencies. An example is the problem of controlling the clock frequency of a synchronous circuit with respect to high-frequency voltage droops. We present a design based on the techniques developed in [START_REF] Friedrichs | Metastability-containing circuits[END_REF] and prove it correct.

• [32] Bund, Függer, Lenzen, Medina. Synchronizer-free digital link controller. IEEE Transactions on Circuits and Systems I: Regular Papers, 67 [START_REF] Marino | The effect of asynchronous inputs on sequential network reliability[END_REF], pages 3562-3573, 2020.

We show how a metastability-containing link controller between a sender and a receiver can be used to tightly control receiver and sender clocks with low controller latencies.

Metastability

The existence of an intermediate, so called metastable, state in bistable elements like latches and flip-flops, already played a role in Chapter 2: in fact, for the circuit depicted in Figure 2.8 on page 19 that solves unbounded SPF, we explicitly used the storage loop's behavior near the metastable point when resolving to one of the stable states 0 or 1. Our solution, however, did not guarantee when this will happen -and indeed, we showed that a bounded version of Short Pulse Filtration is not solvable by any circuit. The proof is by reduction to a fundamental result from Marino [START_REF] Marino | General theory of metastable operation[END_REF] on bistable storage elements: the existence of a metastable state and an input signal that drives the storage element arbitrarily close to the metastable state, where it resides for an unbounded amount of time before it resolves to stable 0 or 1. Externally, at the output of the storage element, a metastable state may manifest as an intermediate voltage level between a clear 1 and 0, a clear signal followed by a late transition when it resolves, glitches, oscillation, etc. [START_REF] Ginosar | Metastability and synchronizers: A tutorial[END_REF][START_REF] Polzer | An experimental study of metastability-induced glitching behavior[END_REF]; depending on the implementation [START_REF] Jens U Horstmann | Metastability behavior of cmos asic flip-flops in theory and test[END_REF].

The phenomenon of metastability has a large impact on the design of circuits. Consider the standard clocked Moore implementation in Figure 3 A realistic design will interact with an input and output environment -on its left, respectively, right, in the figure. Environments may be untimed or clocked with a clock with unknown phase offset. The former, e.g., either because they are implemented without a clock or since they are simply driven by physical phenomena or circuitry that is outside of our control. Reasons for the latter are typically either circuitry that is outside of the designer's control such as IP blocks, or the circuit may have been deliberately partitioned into independent clock domains for performance reasons.

In both cases, input changes may violate setup/hold constraints of the input registers with severe consequences:

1. If the input register becomes metastable, no upper bound on when its output stabilizes exists.

2. By consequence, a priori, there is no bound on when the combinational logic will stabilize.

3. Thus, the next clock transition may arrive when the combinational circuitry has not stabilized yet -with the possibility for a wrong, or even inconsistent, state stored in the local registers.

In the worst case, the local registers may become metastable, leading to similar problems as described here in downstream logic.

Coping with Metastability

Weather a design suffers from metastable upsets, and if so, with which probability, depends on several factors. First, note that metastability, is not a stable state and the slightest distance of the internal state to the metastable point will amplify exponentially over time until the internal state saturates at a stable state [START_REF] John | Synchronization and Arbitration in Digital Systems[END_REF][START_REF] Kinniment | Measuring deep metastability[END_REF][START_REF] Harry | The behaviour of flip-flops used as synchronizers and prediction of their failure rate[END_REF]. While odds to generate an input pulse that drives the bistable element into metastability for long enough to interfere with the next clock transition may be low for a particular circuit, several factors may very well render such upsets a real problem:

1. A large number of independent clock domains. Designs with tens and recently thousands of clock regions on a chip with significant interfacing to the external world and among each other face a proportionally higher upset frequency.

2. High clock frequencies. Since, a priori, an upset may occur at every clock cycle, upset frequencies are proportional to clock frequencies.

3.

Aggressive timing, i.e., small clock margins. This reduces the tolerance to even slightly longer propagation delays through the combinational logic.

4. Low supply voltage. Trends to decrease the supply voltage to meet power constraints, lead to increased metastability decay times [START_REF] Beer | Metastability challenges for 65nm and beyond; simulation and measurements[END_REF].

Given that there provably is no mitigation technique that completely prevents bistable elements from having upsets, techniques to diminish effects have been developed and are in place in many designs.

Synchronizers

The most widely adopted mitigation technique is to use chains of flip-flops as synchronizers [START_REF] John | Synchronization and Arbitration in Digital Systems[END_REF][START_REF] David J Kinniment | Synchronization circuit performance[END_REF][START_REF] Beer | Eleven ways to boost your synchronizer[END_REF]. Each of the flip-flops has preferable metastability decay characteristics compared to a standard data flip-flop [START_REF] Yang | Synchronizer performance in deep submicron technology[END_REF][START_REF] Cox | Synchronizers and data flip-flops are different[END_REF]. Other known mitigation techniques are Schmitt triggers [START_REF] Steininger | The metastable behavior of a schmitttrigger[END_REF]. But also C-elements, being widely used in asynchronous designs, show synchronizing behavior [START_REF] Fuchs | On the threat of metastability in an asynchronous fault-tolerant clock generation scheme[END_REF][START_REF] Polzer | Muller c-element metastability containment[END_REF].

The principal idea of a synchronizer is simple and effective: Each synchronizer stage is clocked by the recipient circuit's clock and provides extra decay time for the signal before it is passed to the recipient circuitry, aligned to its clock domain. Since signal amplification is exponential around the metastability point of a storage loop, and given uniform input transition arrival times at input of the first synchronizer stage, the probability of the first stage to be metastable after one clock period decreases exponentially with the length of the clock period. Care must be taken, though, in the analysis since the flip-flop comprises of a master and slave latch: the uniform arrival times, e.g., only (potentially) hold for the first latch. The interested reader is referred to the work by Jones et al. [START_REF] Jones | Synchronizer behavior and analysis[END_REF]. A refined analysis is particularly important when analyzing synchronizers with multiple stages. As a rule of thumb, the probability that the last input stage becomes metastable is exponentially small in the number of stages due to an exponential decay happening in all stages.

While synchronizers may decrease the probability of metastable upsets at the cost of additional input latency, a deterministic guarantee of the absence of metastability is impossible.

Asynchronous Circuits

An orthogonal approach is to abolish clock domain crossings altogether. If the timing in the clock domain is dictated by the arriving signal rather than the region's clock, upsets of the circuit can be prevented. The circuit then waits until it has received a handshake from a yet to stabilize component, using either of:

• The fact that timing constraints are met and thus no metastable upsets can occur. This approach is similar to designing either closed-systems where the controller signals to the external environment when it is ready for a new input, or requires respective timing constraints on the environment. As such it is often not feasible.

• The fact that certain components may get metastable, but that do not produce a valid handshake until metastability is resolved internally. This approach allows for deterministically correct solutions, however, with potentially unbounded timing. A discussion of such designs in our context is given in Section 3.3.3 -for the moment we just note that this does not violate Marino's impossibility result of the existence of a bounded-time, deterministic metastability detector as the response may occur after an unbounded time or may even never occur. Nonetheless it renders an interesting alternative to clocked designs if fast enough decay times are guaranteed by the target technology.

In both approaches handshaking is a central concept. Typically, handshaking between components in asynchronous circuits is used to wait for all predecessors of a component to complete, before starting computation. Yakovlev et al. [START_REF] Yakovlev | Or causality: modelling and hardware implementation[END_REF] introduced the concept of OR-causality as an extension to the classical AND-causality that many asynchronous circuits rely on. With classical AND-causality, given that its two predecessors compute a and b, the component then carries on to compute f (a, b) for some function f . In certain scenarios, however, waiting for all predecessors is overly conservative -for example if f (a, b) = a ∨ b and a = 1. No matter of b's value, the component will produce f (a, b) = 1. Thus, the circuit may start computation right after receiving input a = 1.

OR-causality, and more generally the concept of ignoring certain inputs, has the potential to also ignore metastable inputs, and not wait arbitrarily long for them to resolve: by this it may tolerate unbounded delays, or even, complete absence of handshakes in data that it is no longer waiting for. However, this is only guaranteed in certain scenarios. A similar example as above, but with a = 0 forces the component to wait for its second input. Further, a circuit with OR-causality does not necessarily handle metastability in a correct way. Denote a metastable bit with M. Then,

f (1, 0) = f (1, 1) = 1 holds, but f (1, M) = 1 may not necessarily hold for an implementation of f (a, b) = a ∨ b with OR-causality.

Speculative Computing

Tarawneh et al. [START_REF] Tarawneh | An rtl method for hiding clock domain crossing latency[END_REF][START_REF] Tarawneh | Eliminating synchronization latency using sequenced latching[END_REF] proposed the concept of speculative computing. Given a single-argument function f : B → B, with a potentially metastable input a, they compute f (0) and f (1), and only later on, when a has stabilized, decide whether to output f (0) or f (1). This in fact allows to hide a part of the overall synchronization delay within the computation delay, since both, computation and synchronization, are carried out in parallel. The approach, also works for multiple arguments, by recursively applying it to the arguments. Further, if only the first argument of a function f (a, b) may become metastable, the scheme can be applied to the partial evaluation b → f (a, b) as well.

Metastability-Containing Circuits

Both, the synchronizer and the asynchronous approach have in common that they wait before computing. In case of the synchronizers for a fixed time T , and in asynchronous circuits until metastability has decayed. Besides the fact that waiting in high-speed circuits defeats its primary goal, the designer is left to make a decision between:

• Being time-safe. Timing guarantees with the downside of potentially metastable values when using synchronizers.

• Being value-safe. Value guarantees with the possibility of unbounded or infinite delays when using asynchronous circuits.

With metastability-containing circuits [START_REF] Friedrichs | Metastability-containing circuits[END_REF] we showed that this tradeoff is not obligatory, however.

Topological View

Marino's proof on the impossibility of bounded-time stabilization [START_REF] Marino | General theory of metastable operation[END_REF] is based on the topological statement that, given a connected input space I and a continuous function s : I → O, the output space O is connected. Let us consider a bistable element, like a synchronizers, with an input port and an output port. 1 To apply the topological statement, the input space is defined as the set of valid input pulses, and the output space is set to O = [0, 1], i.e., the output's signal value at a certain time T > 0 -the time until which we expect the output signal to be stabilized. With standard metrics in place, the input space is connected. The metric on the output space, is simply the Euclidean distance. The major difficulty then is to prove that the function o is indeed continuous under assumptions that capture realistic physical circuits, like causality. Given that there exists an input pulse i 0 for which s(i 0 ) is arbitrarily close to 0 and an input pulse i 1 with s(i 1 ) being arbitrarily close to 1, we may apply the topological argument to obtain that there exist input pulses i M for which s(i M ) is arbitrarily close to, say, 0.5. Figure 3.2 visualizes this argument.

t i t o s(i0) s(i1) T t i t o s(iM) T Figure 3
.2: Topological argument on the impossibility to stabilize within bounded time T > 0.

Synchronizer followed by computation. Figure 3.3 sketches a synchronizer and the subsequent synchronous computation upon the synchronized data from this point of view. The input environment applies input signals that are from a connected space. The input is then synchronized to the new clock domain, e.g., by passing it through a 3 stage synchronizers, which lasts until some time T > 0. In fact this synchronization process can be understood as computing the identity function during, say, T = 3 clock cycles. While the output space is shown to be connected, with a certain probability, the output signal will be within a disconnected subspace -corresponding to the binary-valued representation of the input signal. Assuming that this is the case, the circuit then computes a function f that finally yields the binary-valued output after another, e.g., 4 clock cycles. The end-to-end latency is thus the sum of both delays; here 7 clock cycles. Metastability-containing computation. The idea of metastability-containing computing is to study computation in a larger, connected, space that includes metastable signals. As such it treats metastability as a valid effect that may occur during the computation, rather than its absence as an assumption external to the model. While Boolean computation studies computation of functions from input values in some discrete input space B i , with i ∈ N + , to a discrete output space B j , with j ∈ N + , we consider functions from tuples on B M to tuples on B M , where B M = B ∪ {M}. Here, the third value M encodes a metastable signal. In our work we do not make any assumption on such a signal -in particular, a metastable signal may have an arbitrary intermediate voltage between 0 and 1, may glitch, oscillate, etc.

From a computational point of view, a synchronizer, if restricted to values in B, computes the identity. So why first compute the identity, before the actual computation of a function f is started? Two properties of the identity function may be responsible for this intuitive choice:

• It preserves precision from the input to the output, no matter if the input/output is encoded in binary, unary, or otherwise. We will later formalize this property of a function, and call such functions metastability-containing.

• It is easily implemented in a way that metastability at the inputs introduces only as much metastability at the outputs as theoretically necessary for such a circuit (in presence of standard registers). In particular, it does output a metastable bit whose corresponding input bit was not metastable. Again, we will formalize this property later on for functions and their circuit implementations and call such circuits metastability-containing.

The question arises, if there are other functions and circuit implementations of these functions that have similar advantageous properties and that additionally already perform (part of) the circuit's intended computation. Designs that make use of these techniques will be referred to as metastability-containing computations. Figure 3.4 sketches the idea of metastability-containing computing from a topological perspective. The difference to the synchronizer is that function f is now computed in a metastabilitycontaining way. The advantage is not only that computing time is spared by removing the synchronization process -see Figure 3.4 (left) -but also that the assumption of stabilization in time is remove -see Figure 3.4 (right). The latter, however, is only applicable if the output environment allows for potentially unstable outputs. Examples where this is the case, are downstream metastability-containing circuitry and applications with a continuous output space, e.g., shifting a signal transition in time, controlling a frequency, voltage, etc. The latter is particularly interesting for controller applications; see Section 3.9.

Relation to Previous Work

To the best of the author's knowledge, the work on speculative computing [START_REF] Tarawneh | An rtl method for hiding clock domain crossing latency[END_REF][START_REF] Tarawneh | Eliminating synchronization latency using sequenced latching[END_REF] is the most closely related to our work: it also aims at parallelizing stabilization and computation and thus fundamentally differs from the synchronizer approach. The differences to our work on metastabilitycontaining circuits [START_REF] Friedrichs | Metastability-containing circuits[END_REF] are: (i) Speculative computing runs two parallel tracks -synchronization and computation -while the idea in metastability-containing computing is to tightly interweave both to obtain synchronization during computation. (ii) It does not aim for deterministic endto-end guarantees, since it uses synchronizers that may fail with a certain probability. (iii) The designer must know in advance which bits face the risk of becoming metastable. Speculative computing is then applied to these. By its recursive nature, designs with several metastable candidates quickly become large: k potentially metastable bits result in designs that are larger than by a factor 2 k (duplication and merging). Because of the tight interweaving of computation and synchronization, smaller circuits can be obtained by metastability-containing circuits if the function allows for it. Indeed in this chapter we will encounter several problems for which small circuit solutions exist.

Glitches and hazards are unintended transitions; typically of an output signals. Their systematic study has been pioneered by Huffman [START_REF] Huffman | The design and use of hazard-free switching networks[END_REF] and Unger [START_REF] Steven | Hazards and delays in asynchronous sequential switching circuits[END_REF]. Different types of hazards have been studied, ranging from static hazards where a multi-bit input x switches to y = x, and although f i (x) = f i (y) for output bit i, two spurious transitions -f i (x) to ¬f i (x), and ¬f i (x) to f i (x) are observed at the output. While glitches and hazards are spurious, but well-formed, transitions in signals and thus differ from our metastable signals, the methods used to study metastable signals have commonalities with those to study glitches and hazards. For example, static hazards [START_REF] Huffman | The design and use of hazard-free switching networks[END_REF] have been addressed with covering prime implicants. In fact we will show that this technique, among others, can also be used to design metastability-containing circuits.

While, initially, two such inputs x, y were restricted to differ only in a single bit, work by Eichelberger [START_REF] Eichelberger | Hazard detection in combinational and sequential switching circuits[END_REF] extended this to multiple bits and studied dynamic hazards with spurious transitions in switching outputs. Brzozowski and Yoeli [START_REF] Janusz | On a ternary model of gate networks[END_REF] extended the simulation algorithm, Brzozowski et al. [START_REF] Janusz | Algebras for hazard detection[END_REF] surveyed techniques using higher-valued logics -including Kleene's 3-valued logic -and Mendler et al. [START_REF] Mendler | Constructive boolean circuits and the exactness of timed ternary simulation[END_REF] studied delay requirements needed to achieve consistency with simulated results.

Besides the different assumptions on signal integrity in glitching signals and metastable signals, key differences are:

• Timing. Circuits studied with respect to the occurrence of glitches require delay models.

Typically pure delay channels are assumed. One can thus bound the time until when outputs are glitch-free. This is no longer true for metastable signals, since metastability may last forever.

• Glitches. Metastability-containing circuits are not designed to be free of static, dynamic, or any other glitches. Their outputs may thus contain glitches.

• Multi-cycle. Glitches and hazards are typically studied in combinational logic, only -and thus for one clock cycle. Our circuits operate over multiple clock cycles. In fact we will show that such circuits result in a strictly larger class of functions that can be implemented; see Section 3.7.3.

• Register types. We studied different register types, that behave differently with respect to internal metastability.

Computational Model

Consider a setup of a synchronous finite state machine implementation, similar to the implementation of the Moore machine in Section 1.3 and the circuit in Figure 3.1 on page 34, expect that the input is not newly latched in every clock cycle. The circuit is shown in Figure 3.5 -note the missing clock input at the input register. While a realistic circuit will have circuitry to load data into the input register, for simplicity we abstract from this and assume that the register is initialized and not written anymore during computation. We next discuss differences between the computational model proposed in [START_REF] Friedrichs | Metastability-containing circuits[END_REF] and the classical Boolean circuit model. Round-wise model. We do not explicitly model continuous evolution of signals, but assume that the clock period is chosen such that non-metastable data has stabilized at the occurrence of the next active (rising) clock transition. Time thus progresses in discrete rounds r ∈ N + , where round r comprises of:

1. Read phase: read all input and local registers. We will define register behavior in the following. The read phase models the time right after clock transition r -1 for r > 1, and the initial values for r = 1.

2. Evaluation phase: the read values are propagated through the combinational logic. We will define the gates' behavior in the following. This phase makes up the largest part of round r.

3. Write phase: the values at the output of the combinational logic finally have the possibility to resolve: An output that is stable, i.e., in B, is not changes, and an output that is M, is allowed to take any value in B M . The value is then the new state of the local or output register. This phase corresponds to the arrival of the r th rising clock transition, ending round r.

Instead of considering the detailed timed executions of such circuits, we will work with a discretetime abstraction. A configuration of a circuit is a tuple that contains the states of the input, local, and output registers. An execution of a circuit is a sequence (s r ) r∈N of configurations, with s 0 being the initial configuration, and s r , with r ∈ N + , obtained from s r-1 by application of the read, evaluation, and write phase. Note that a circuit has to define the initial local and output register states. Given a circuit C, the set of output register states reachable via an execution in r ∈ N rounds from input register states ι is denoted by C r (ι).

A specification is a function B m M → P(B n M ) that maps a vector of input values to the set of allowed output values. We say r rounds of circuit C implement a specification s :

B m M → P(B n M ), if for all inputs ι ∈ B m
M , and all executions of circuit C with inputs ι, after r rounds, the vector of circuit outputs o in this execution is in s(ι), i.e.,

∀ι ∈ B m M : C r (ι) ⊆ s(ι) .
We say C implements s, if there exists an r ∈ N such that r rounds of C implement s. Instead of C implementing s, we also speak of C computing s if the focus is on the functional aspect of s.

It remains to specify the behavior of circuit gates and registers.

Gates. Similar to their classical Boolean counterparts, a gate with k > 0 inputs is a function

B k M → B M .
However, care has to be taken in which functions we allow in order to capture real word circuits. For example, a gate that maps M to 1, and all other values to 0 would be a bounded-time metastability detector; a device that does not exist.

For that purpose, we define resolutions and extensions of Boolean gates based on resolutions as follows. Let x ∈ B k M . The set of partial resolutions of x, denoted by Res M (x), is defined as

Res M (x) = y ∈ B k M | ∀i ∈ [k] : x i = y i ∨ x i = M . (3.1)
The set of resolutions, denoted by Res(x), is defined as

Res(x) = Res M (x) ∩ B k . (3.2)
For a Boolean function f :

B k → B, we define its metastable extension f M : B k M → B M as f M (x) =      0 if ∀x ∈ Res M (x) : f (x ) = 0 1 if ∀x ∈ Res M (x) : f (x ) = 1 M otherwise . (3.3)
We only allow gates that that are metastable extensions of Boolean functions. The reason is that standard Boolean CMOS gates like the 2 input Nand and Nor gates, if implemented correctly, readily compute the metastable extension of their Boolean functions. Registers. We consider three register types. Figure 3.6 shows their gate symbols.

• Simple registers. These are the classical used registers without any additional assumption on their behavior on metastable states. They simply output their internal state. We assume that input registers never change their internal state. While this is obviously no restriction for a stable internal state in B, we claim that it is also not a restriction for a metastable internal state: any stabilization would actually diminish the reachable executions; and thus this captures the worst-case.

• Masking registers. There are two types of masking registersmask-0 and mask-1. With b ∈ B, a mask-b register maps an internal metastable state to b at its output. By contrast to simple registers, masking input registers may change their state during the read phase. If they are internally metastable, they may transition to any state in B M . If they were in state M and they transition to b, then b is their new state, and we read b at their output during the read phase. If they were in state M and they transition to ¬b, then ¬b is their new state, and we read M at their output during the read phase.

While simple registers are sufficiently unconstrained to arguably capture most existing register implementations, the behavior of masking registers is non-standard. Indeed, noise-tolerant implementations are a topic of current research. We will refer to an implementation based on metastability filters as discussed by Kinniment [START_REF] John | Synchronization and Arbitration in Digital Systems[END_REF] (Section 3.1), here. Recall the unbounded SPF circuit from Section 2.8.5. It relied on a low-threshold inverter after a storage loop with a high metastability point; see Figure 2.12 on page 25. We may use the same idea and let the flip-flop output drive high-or low-threshold inverters, amplifying an internal metastable signal to 1 or 0.

Such filters are also used in asynchronous designs: for example the Blade design style [START_REF] Hand | Blade-a timing violation resilient asynchronous template[END_REF], based on bundled data communication between modules, makes use of metastability filtering techniques. Aggressive timing of the request/acknowledge signals with respect to the data signals may result in metastable Blade controller states. In this case, metastability filters are used to locally halt computation (by delaying req/ack) until metastability is resolved. This allows for more aggressive timing than in synchronous pipelines, where large clock margins have to account for all cases.

Another interesting recent applications is within a mutex to create a (local) pausible clock that halts until internal metastability is resolved [START_REF] Fojtik | A fine-grained gals soc with pausible adaptive clocking in 16 nm finfet[END_REF].

Metastability-Containing Multiplexers

Let us demonstrate the key questions at the example of a small, but widely-used circuit, a multiplexer. The choice of the multiplexer as a running example is motivated by a second advantageous fact: it will play a central role in several metastable-containing circuits.

Standard Multiplexer

Definition 38 (Multiplexer). A (k-bit) multiplexer (Mux) is a circuit with 2k + 1 inputs and k outputs, that implements f Mux :

B k M × B k M × B M → P(B k M ) with f Mux (a, b, s) =      Res M (a) if s = 0 Res M (b) if s = 1 B k M if s = M .
When we speak of a multiplexer, we refer to the case k = 1, unless noted otherwise. Its behavior, for binary signals is as expected: the select bit s, determines whether to output a or b. In presence of metastable inputs a and b, it only guarantees that a solution of the output takes on a resolution of the selected input. If the select bit is metastable, an arbitrary output may be produced.

Example 39. For the single bit multiplexer, with k = 1, we have

f Mux (1, M, 0) = Res M (1) = {1}, f Mux (1, M, 1) = Res M (M) = B M , and f Mux (1, M, M) = B M .

Stronger Guarantees

In case of Boolean input values, and if a = b, the specification of a multiplexer implies that its output is a. Care must be taken in presence of metastable inputs. The specification of a multiplexer Mux does not constrain the output if s = M. Indeed, the circuit Smux sets its output to M if s = M and a = b = 1.

The question arises, if we can ask for more from a multiplexer-type circuit. Intuitively, a multiplexer that is unsure which input to forward to the output, but whose both inputs are identical and stable, should output the stable, identical, input value. Cast into a specification, we require:

Definition 40 (Metastability-Containing Multiplexer. From [START_REF] Friedrichs | Metastability-containing circuits[END_REF]). A (k-bit) Metastability-Containing Multiplexer (Cmux) is a circuit with 2k +1 inputs and k outputs, that implements f Cmux :

B k M × B k M × B M → P(B k M ) with f Cmux (a, b, s) =      Res M (a) if s = 0 ∨ a = b Res M (b) if s = 1 B k M if s = M ∧ a = b .
Indeed, metastability-containing multiplexer exists. We showed in [START_REF] Friedrichs | Metastability-containing circuits[END_REF] that 1 round of Cmux1, depicted in Figure 3.8 on page 43, implements f Cmux . Thus: Lemma 41 ( [START_REF] Friedrichs | Metastability-containing circuits[END_REF]). Circuit Cmux1 is a Cmux.

We will next discuss a two round implementation. The reader may wonder why we continue to find a slower implementation after solving the problem in a single round. Further, the two round implementation requires additional local registers to store the circuit's state. Our motivation is twofold: First, the two round solution demonstrates how masking registers can be used to solve problems, and second the proposed technique can be generalized and can lead to potentially efficient circuits for more complex problems.

For simplicity, we state the circuit in terms of pseudocode in Algorithm 2 -note that this can be readily translated to a synchronous circuit. The algorithm uses the fact that out of two reads from a masking register, only one can be metastable. where circuit Mmux failed to implement Cmux, we obtain the following behavior: Since we are using a mask-1 register to store s, if s = M, the two sequential reads of s will yield 1, 1 or M, 0 or 1, M. Accordingly, these are also the states of s , s in round 2 -assuming s did not resolve. One finally observes that in all these scenarios at least one And clause is stable 1, setting the output to 1. We thus have that two rounds of the circuit corresponding to Algorithm 2 implement f Cmux . Thus: Corollary 42 ( [START_REF] Friedrichs | Metastability-containing circuits[END_REF]). The circuit corresponding to Algorithm 2 is a Cmux.

An optimized version of this circuit is obtained by inserting a delay between signals s and s instead of explicitly separating them by a clock cycle. By doing so, one obtains the circuit in Figure 3.9. The technique of delaying outputs from masking registers rather than sampling them in separate rounds has wider applications not detailed here.

Properties of Synchronous Circuits under Metastability

We readily obtain several properties of circuits in our circuit model. The properties are not only useful in proving results about computability later on, but also to show that the model captures physical circuits faithfully. Like the SPF problem in Chapter 2 was used to determine the faithfulness of delay models with respect to glitch propagation, we will discuss analogous problems here to determine the faithfulness of our model with respect to propagation of metastability.

We start with a property of purely combinational circuits. For such circuits, stabilizing inputs do not introduce additional metastability at the outputs. Rather, unstable outputs remain unstable, or they stabilize. The following lemma states this in terms of our model:

∈ B m M , ι ∈ Res M (ι) ⇒ f C (ι ) ∈ Res M f C (ι) . (3.4)
The property also demonstrates that our assumption of simple registers remaining metastable throughout an execution is indeed the worst-case. Any resolution of them cannot lead to more metastability at the circuit outputs. The situation is different for masking registers, as we will see later on -this is also why resolution is explicitly modeled in masking registers.

A further basic property is that output registers, written at the end of the first round, resolve independently of each other: Corollary 44 ( [START_REF] Friedrichs | Metastability-containing circuits[END_REF]). For any circuit C with m input and n non-input registers,

C 1 = g 0 × • • • × g n-1 ,
where

g i : B m M → {{0}, {1}, B M }
is the function that corresponds to non-input register i ∈ {0, . . . , n -1} and maps the input to its possible outputs.

The result implied that we can treat non-input register states independently of each other, at least in the first round. We will later see that this generalizes to multiple rounds for simple registers. Again masking registers make an exception -the property does not hold for rounds larger than 1.

Based on Corollary 44, we may lift Lemma 43 from covering just the combinational logic to full single-round computation, and obtain: Corollary 45 ( [START_REF] Friedrichs | Metastability-containing circuits[END_REF]). For a circuit C with m inputs, and for an input

ι ∈ B m M , ι ∈ Res M (ι) ⇒ C 1 (ι ) ⊆ C 1 (ι) .

Faithfulness

While one may wish for circuits that reliably either detect or filter metastability within bounded time, reductions to Marino's work [START_REF] Marino | General theory of metastable operation[END_REF] prove this impossible in physical circuits. Let us state both problems in our model.

Definition 46 (Synchronous metastability-detector and metastability-filter).

A synchronous metastability-detector is a circuit that implements the function f :

B M → P(B M ) with f (x) = {1} if x = M {0} otherwise . (3.5)
A synchronous metastability-filter is a circuit that implements the function f :

B M → P(B M ) with f (x) = {0, 1} if x = M {x} otherwise . (3.6)
For physical circuits the following holds, by arguments analogous to the ones given in Section 2.5 for the bounded Short Pulse Filtration problem: Theorem 47. No physical circuit exists that is a synchronous metastability-detector or a synchronous metastability-filter.

We thus call a circuit model faithful with respect to metastability detection and filtration if within this model, no circuit exists that is a synchronous metastability-detector or a synchronous metastability-filter.

In [START_REF] Friedrichs | Metastability-containing circuits[END_REF] we have shown that in our synchronous circuit model, for any circuit which has to output different results for at least two different inputs there exists an input that produces metastable outputs.

Theorem 48 ([28]). Let r ∈ N + and C be a circuit with C r (ι) ∩ C r (ι ) = ∅ for some ι, ι ∈ B m M . Then C has an r-round execution in which an output register becomes metastable.

The proof relies on the construction of so called pivotal sequences. These are finite sequences of stable Boolean inputs of which the first element is ι, the last element is ι , and two successive elements differ in at most one input bit. Within this sequence a switch in corresponding outputs must occur between two successive inputs differing in only a single bit. We then construct an input from these two Boolean inputs that leads to metastability for its corresponding output.

By instantiating Theorem 48 for two functions, one readily shows that the previous two problems are not solvable in our circuit model:

Corollary 49 ([28]

). There exists no circuit in the synchronous circuit model that is a synchronous metastability-detector or a synchronous metastability-filter.

We thus finally obtain: Theorem 50. The synchronous circuit model is faithful with respect to metastability detection and filtration.

Computability

In [START_REF] Friedrichs | Metastability-containing circuits[END_REF] we showed that simple and masking registers do not only differ in the functions they compute, but that there exists a non-trivial computational hierarchy in presence of masking registers. The writeup discusses theses results in the following. We start with defining several classes of functions related to computability within our model. Definition 51 (Computable function classes, from [START_REF] Friedrichs | Metastability-containing circuits[END_REF]). We define the following classes of functions, with r ∈ N + :

• Fun r S is the class of functions implementable with r rounds of circuits comprising only simple registers.

• Fun r M is the class of functions implementable with r rounds of circuits that may additionally use masking registers.

The Computational Hierarchy

As a first result, one readily obtains that the first classes match.

Corollary 52 ([28]). Fun

1 S = Fun 1 M .
Further, masking registers only play a role if used as input registers. Using them as local or output registers does not provide different behavior. Note, however that this statement is within our worst-case synchronous circuit model. There may very well be, and in fact is, different behavior in a probabilistic analysis. Treatment of these effects, however, is outside the scope of this writeup.

Corollary 53 ([28]

). Simple and masking registers are interchangeable when used as non-input registers.

Finally, we obtain the existence of a hierarchy among the classes. Adding computational rounds never decreases the class of computable function. The proof of this result uses simulation of shorter executions and delaying outputs. Furthermore, allowing masking registers does not decrease the computational power. In terms of the function classes, we thus have: Corollary 54 ( [START_REF] Friedrichs | Metastability-containing circuits[END_REF]). For all r ∈ N + , we have

• Fun r S ⊆ Fun r+1 S , • Fun r M ⊆ Fun r+1
M , and • Fun r S ⊆ Fun r M . Note that the corollary leaves it open whether the complete hierarchy collapses to a single class of computable functions. We will soon see that this is not the case.

Simple Registers

The technique of circuit unrolling is folklore in circuit design for circuits with binary-valued gates: given a multi-round computation over r > 1 rounds, the combinational circuit may be unrolled r -1 times instead of storing intermediate results in local registers. Indeed, circuits with simple registers can be unrolled also in presence of metastability: Theorem 55. Given a circuit C with only simple registers such that r ∈ N + rounds of C implement f , one can construct a circuit C such that one round of C implements f . While from a computational perspective, multi-round circuits seem superfluous, they clearly play a role when circuit size does.

Theorem 55 finally yields the collapse of the hierarchy for simple registers:

Corollary 56. For all r ∈ N + , Fun r S = Fun 1 S .

We may thus omit the index r in Fun r S and denote the class by Fun S .

Characterization. A question of practical relevance is which functions are indeed implementable with only simple registers, i.e., a characterization of Fun S . For that purpose let us define natural functions and subfunctions:

Definition 57 (Natural functions and subfunctions, from [START_REF] Friedrichs | Metastability-containing circuits[END_REF]). The function f : B m M → P(B n M ) is natural if and only if it is bit-wise, closed, and specific, defined as follows:

Bit-wise. The components f 1 , . . . , f n of f are independent:

f (ι) = f 1 (ι) × • • • × f n (ι). (3.7)
Closed. Each component of f is specified as either 0, as 1, or completely unspecified:

∀ι ∈ B m M : f (ι) ∈ {{0}, {1}, B M } n . (3.8)
Specific. When stabilizing a partially metastable input ι, the output of f remains at least as restricted as with input ι:

∀ι ∈ B m M : ι ∈ Res(ι) ⇒ f (ι ) ⊆ f (ι). (3.9)
For functions f, g :

B m M → P(B n M ), g is a subfunction of f , denoted by g ⊆ f , if and only if g(ι) ⊆ f (ι) for all ι ∈ B m
M . With these definitions in place, Fun S is characterized as: Theorem 58 ( [START_REF] Friedrichs | Metastability-containing circuits[END_REF]). Let g : B m M → P(B n M ) be a function. Then g ∈ Fun S if and only if g has a natural subfunction.

The if-direction of the theorem's proof is constructive and uses a strategy also used in designing hazard-free circuits for static hazards [START_REF] Huffman | The design and use of hazard-free switching networks[END_REF]: it covers prime-implicants of g i , with i ∈ [n]. The construction, however, may result in circuits that are exponentially large in m.

Certain functions are particularly well suited as being implemented by circuits: they do not only fall into the class Fun S , but are also minimal within this class, in a sense that will be made precise in the following. Recalling the metastable extension f M : B m M → B M of a Boolean function f : B m → B, we define: Definition 59 (Metastable closure, from [START_REF] Friedrichs | Metastability-containing circuits[END_REF]). For a Boolean function f :

B m → B n , we define its metastable closure [f ] M : B m M → P(B n M ) component-wise for i ∈ [n] by [f ] M (x) i = Res M ((f i ) M (x)) =      {0} if (f i ) M (x) = 0 {1} if (f i ) M (x) = 1 B M if (f i ) M (x) = M . (3.10)
For a function f :

B m M → P(B n M ), we define its metastable closure [f ] M : B m M → P(B n M ) by [f ] M (x) i =      {0} if ∀x ∈ Res M (x ) i = {0} {1} if ∀x ∈ Res M (x ) i = {1} B M otherwise . (3.11)
Example 60. For the Boolean And input-output function f :

B 2 → B with f (a, b) = a ∧ b, the metastable closure [f ] M is f (a, b) =                {a ∧ b} if a = M ∧ b = M {0} if a = M ∧ b = 0 {0} if a = 0 ∧ b = M B M if a = M ∧ b ∈ {M, 1} B M if a ∈ {M, 1} ∧ a = M . (3.12)
By construction, for a function f : B m M → P(B n M ), its metastable closure [f ] M is bit-wise, closed, specific, and hence natural. The same holds true for Boolean functions f . Corollary 61 ([28]). For all Boolean functions f :

B m → B n , it is [f ] M ∈ Fun S . Further, for all functions f : B m M → P(B n M ), it is [f ] M ∈ Fun S .
Metastability-containing circuits. Corollary 61 has direct applications for implementing Boolean functions by a circuit in a way that the circuit provably optimally contains metastability. While Theorem 48 shows that non-constant functions must have inputs that lead to metastable outputs, Corollary 61 provides the answer to how much metastability we need to accept in presence of metastable inputs: For every Boolean function f : B m → B n , there is a circuit with only simple registers that implements [f ] M . Theorem 58 shows that [f ] M is the minimum extension of f implementable with simple registers: any of its proper subfunctions is not implementable. Thus, the circuit is optimally with respect to containing metastability. Motivated by these considerations, we define:

Definition 62 (Metastability-containing circuit). We call a circuit metastability-containing if it implements the metastable closure of a function.

Note that this is a property of a circuit. We will later also use metastability-containing as a property of a function. Like their circuit counterparts, these functions will behave optimally with respect to metastable inputs; more about this in Section 3.8.

Masking Registers

If the computational hierarchy collapses for simple registers, does it also for masking registers? To answer this question, let us define the n-bit metastability-containing replication problem for n ∈ N + . Definition 63 (Metastability-containing replication, from [START_REF] Friedrichs | Metastability-containing circuits[END_REF]). For n ∈ N + , we say a circuit solves the n-bit metastability-containing replication problem if it implements f Mcr,n :

B M → B n M with f Mcr,n (ι) = {ι n } if ι = M i∈[n] Res M (0 i M1 n-i-1 ) otherwise . (3.13)
Essentially, the problems asks a circuit to replicate a single input bit n times. Classically in non-metastable circuits this is trivially solved by driving n outputs directly or indirectly via buffers. The problem, however, becomes interesting and of practical relevance, as we will see, if the input bit is metastable. While in circuits with simple registers it is easily shown that no restrictions can be made on the states of the output registers at all, we obtained: Lemma 64. There exists a circuit C with masking registers, such that n ∈ N + rounds of C implement f Mcr,n , i.e., that solves the n-bit metastability-containing replication problem.

The circuit is deceptively simple: it copies the input bit, stored in a 0-masking register, to register r in round r ∈ N + . Interestingly, this procedure cannot be unrolled -rendering circuits with masking registers fundamentally different from classical circuits. Indeed, we have: Efficient circuits. Theorem 58 on page 47 presented an exponential size construction to implement functions by metastability-containing circuits if the function is in Fun S . In particular this allows to construct circuits that implement [f ] M for a Boolean function f . In [START_REF] Friedrichs | Metastability-containing circuits[END_REF] we also showed a different construction that inherently uses masking registers to achieve only a linear blowup in gate count:

Theorem 67 ([28]). Let f : B m → B n be a Boolean function and G a purely combinational circuit with input-output behavior f G (ι) = f (ι) for all ι ∈ B m . Then there is a circuit C such that 2m + 1 rounds of C implement [f ] M . The circuit uses

• m mask-0 input registers,

• (2m + 1)n simple local registers, and

• n simple output registers.

The additive overhead in complexity with respect to G is O(nm log m) in gate count and O(log m) in depth.

Figure 3.10 on page 49 sketches the circuit's data path that is at the heart of the construction in Theorem 67. The circuit first solves the 2m + 1-bit metastability-containing replication problembut instead of computing the identity ι it replicates f i (ι), for each output bit i. The majority of the replicas is then computed in each round, with the result written to output register i. Note that the output register may be set to M in round 2m + 1; the proof, however, shows that this is only the case if (f M ) i (ι) = B M , i.e., this output bit is unrestricted. Further, note that the majority circuit is non-trivial since it must be metastability-containing. If it were not metastability-containing, a single M may overwhelm a majority of binary values. Indeed, circuits that follow this scheme to solve problems are of use as we will discuss in Section 3.9.

L 1 L 2 L 3 L 4 L 5 I 1 I 2 f i majority O i Figure 3
.10: Construction for efficiently implementing the metastable-closure [f ] M of a Boolean function f presented in [START_REF] Friedrichs | Metastability-containing circuits[END_REF]. The depicted circuit is for two input registers and only shows the circuitry for output register i.

Metastability-containing Functions

Definition 62 on page 47 specified metastability-containing as a property of circuits that, in a sense made clear in the definition, optimally contain metastability. They do not "unnecessarily" propagate metastability to the outputs, unless not otherwise possible; at least for circuits with only simple registers. In that sense, a circuit that is supposed to compute the projection (x, y) → x and does so by a single buffer is metastability-containing, while another one that does so by a combinational logic reflecting the term (y ∨ (¬y)) ∧ x is not: for x = 1 and y = M, it is

(M ∨ (¬M)) ∧ x = M.
In the following we will define metastability-containing as a property of functions on natural numbers with a similar intention. Towards this end, we start with formalizing encodings for natural numbers.

A code is an injective function γ : {0, . . . , n -1} → B k mapping an x ∈ {0, . . . , n -1} to its encoded representation. For y such that y = γ(x) for some x, we define the inverse γ -1 (y) = x. For a set X, we follow the convention of writing γ(X) for the set {γ(x) | x ∈ X} and γ -1 (X) for the set {x | γ(x) ∈ X}. Instead of γ(n), with n ∈ N, we also write (n) γ , i.e., the number n encoded by code γ.

Example 68. For the k-bit thermometer code, also referred to as unary code, γ = un, with un : {0, . . . , k} → B k , encoded numbers are given by un(0) = 0 . . . 0, un(1) = 0 . . . 01, un(2) = 0 . . . 011, etc. Further, for k = 5, we have un -1 (01111) = 4 and un -1 (00101) does not exist. With respect to space efficiency, the unary code is exponentially less efficient than the binary code and BRGC -the latter two codes are in fact bijections, making them optimal.

Formalizing the notion of the amount of metastability in a code word we define:

Definition 71 (Precision, from [START_REF] Friedrichs | Metastability-containing circuits[END_REF]). Code word x ∈ B k M has precision p with respect to the code γ if max yȳ | y, ȳ ∈ γ -1 (Res(x)) ≤ p , i.e., if the largest possible difference between resolutions of x is bounded by p. The precision of x with respect to code γ is undefined if some y ∈ Res(x) is no code word.

Given a code γ, the Boolean increment function f Inc,γ is defined as

f Inc,γ (u, (x) γ ) = {(x) δ } if u = 0 {(x + 1) δ } if u = 1 . (3.14)
The increment function f Inc,γ on not necessarily Boolean values is defined as [f Inc,γ ] M . We finally define:

Definition 72 (Metastability-containing function). Let γ be a code. Let f γ : Π k i=1 {(0) γ , . . . , (D i ) γ } → (N) γ be a function. We say f γ is metastability-containing in component i ∈ [k], if: For all x 1 , . . . , x k ∈ Π k j=1 {0, . . . , D j } with x i < D i , if f γ ((x 1 ) γ , . . . , {(x i ) γ , (x i + 1) γ }, . . . (x k ) γ )
has precision p, then

f γ ((x 1 ) γ , . . . , f Inc,γ (M, (x i ) γ ), . . . (x k ) γ )
has precision p.

From considerations analogous to those in the following Example 73, we have that f Inc,bin is not metastability-containing in its first component, while f Inc,un and f Inc,rg are.

Example 73. For the three increment functions f Inc,bin , f Inc,un , and f Inc,rg , with respective code word lengths k ∈ {4, 9, 5}, we observe:

1. f Inc,bin ((0) un , (7) bin ) = (7) bin = 0111 and f Inc,bin ((1) un , (7) bin ) = (8) bin = 1000.

Thus f Inc,bin (M, (7) bin ) = Res M (MMMM).

Since Res(MMMM) = {(0) un , . . . , [START_REF] Dolev | Fault-tolerant distributed systems in hardware[END_REF] un } the function does not contain metastability -it amplifies it in this case. Since Res(M1111111) = {(7) un , (8) un } the function contains metastability in this case.

3. f Inc,rg ((0) un , (7) rg ) = ( 7) rg = 00100 and f Inc,rg ((1) un , (7) rg ) = (8) rg = 01100.

Thus f Inc,rg (M, (7) rg ) = Res M (0M100).

Since Res(0M100) = {(7) rg , (8) rg } the function contains metastability in this case.

The example suggests that efficiency and metastability-containing are possible; in this example with binary reflected gray codes.

Applications

Techniques from the previous sections have been applied to obtain metastability-containing solutions for several realistic problems. We will discuss some of these in the following, starting with a metastability-containing TDC proposed we proposed in [START_REF] Függer | Metastability-aware memory-efficient time-to-digital converter[END_REF].

Time to Digital Converters

A time to digital converter (TDC) is a circuit that translates time (differences) of events to digital representations. Prominent applications are within logic analyzers, recording high-frequency digital signals, experimental setups in high energy physics, and high precision clock synchronization. While any stop-watch-like device with digital output is a TDC, we focus on high-precision TDCs built in integrated circuits. Motivated by their wide applicability, such TDCs have been extensively studied, see e.g. [START_REF] Kalisz | Review of methods for time interval measurements with picosecond resolution[END_REF] for a recent overview.

Linear TDCs. The most widely adapted design style for high-precision TDCs is a linear design [START_REF] Daigneault | A Novel 10 ps Resolution TDC Architecture Implemented in a 130nm Process FPGA[END_REF][START_REF] Perktold | A fine time-resolution (<3 ps-rms) time-to-digital converter for highly integrated designs[END_REF][START_REF] Rahkonen | The use of stabilized CMOS delay lines in the digitization of short time intervals[END_REF][START_REF] Staszewski | 1.3 V 20 ps timeto-digital converter for frequency synthesis in 90-nm CMOS[END_REF]. Figure 3.11 depicts such a design. A sequence of n ∈ N + evenly spaced delay elements, each with the same latency T d , are arranged in a delay line. The delay line is then tapped after each delay element. A tap drives the input of a corresponding bistable storage element, e.g., a latch. With the rising Start signal transition, a logical 1 propagates along the delay line. At arrival of the rising Stop transition, all latches are disabled simultaneously, and their current state is frozen. The latch states c(0) to c(n -1) then form a digital, thermometer encoded, representation of the inter-arrival times of the starting and stopping transitions: flipped-over as c(n -1), . . . , c(0), the word 000001 represents a short time between starting and stopping, while 011111 represents a long time.

T d Start D Q c(0) E D Q c(1) E D Q c(2) E D Q . . . E D Q c(n -
While we assumed (almost) simultaneous disabling of the latches, variants exist where the Stop signal is also delayed by a delay line. We denote the former as regular delay lines; the latter are referred to as Vernier delay lines.

The achieved time resolution of linear TDCs is roughly the latency T d of a delay element, e.g., an inverter or a buffer. The latter is preferable to ensure identical (all rising) transitions at the delay element inputs; with the advantage of not having to balance latency for falling and rising transitions. Further, the latch states directly contain the thermometer encoded values without need for further inverting. In recent designs [START_REF] Daigneault | A Novel 10 ps Resolution TDC Architecture Implemented in a 130nm Process FPGA[END_REF][START_REF] Perktold | A fine time-resolution (<3 ps-rms) time-to-digital converter for highly integrated designs[END_REF][START_REF] Staszewski | 1.3 V 20 ps timeto-digital converter for frequency synthesis in 90-nm CMOS[END_REF], the achieved time resolution is in the order of 10-80 ps, depending on the used process and delay element implementation. For comparison, with more advanced techniques like interpolation between delay elements, a bin size of 5 ps has been demonstrated, using a 130 nm process [START_REF] Perktold | A fine time-resolution (<3 ps-rms) time-to-digital converter for highly integrated designs[END_REF].

Increasing the dynamic range. In contrast to their favorable simplicity and the achieved time resolution, linear TDCs grow linearly in size with the dynamic range: measuring values within {0, . . . , n -1} • T d requires a linear TDC of length n. To keep circuit size low and to extend the dynamic range, fine-TDC/coarse-TDC approaches have been proposed. Typically the fine-TDC is a delay line, with a resolution in the order of T d , and the coarse-TDC is based on a binary counter with a time resolution larger than T d . Several variants of this approach exist and similar strategies have been invented many times independently. To the best of our knowledge, the earliest example of the fine-TDC/coarse-TDC approach is [START_REF] Nutt | Digital Time Intervalometer[END_REF].

Metastability in TDCs. As Marino's topological argument [START_REF] Marino | General theory of metastable operation[END_REF] shows, any TDC necessarily faces the problem of metastable upsets: the continuous domain of time differences is mapped to the discrete domain of digital readouts.

For a linear TDC as in Figure 3.11, setting and disabling a latch at roughly the same time may occur and lead to a metastable upset of this latch. More precisely: Without loss of generality, assume that the rising transition of Start occurs at time 0. Let T > 0 be a time duration, the TDC's stabilization time. Then, for latch i ∈ {0, . . . , n -1} with output c(i), we define a countable union of disjoint closed intervals from R, the critical window W i , as follows.

Definition 74 (Critical window W i , from [START_REF] Függer | Metastability-aware memory-efficient time-to-digital converter[END_REF]). Assume that the rising Stop transition occurs at time t ∈ R. If t ∈ W i , then the output c(i) of latch i is stable 0 or 1 by time T . By contrast, if t ∈ W i , then there is no guarantee that the output c(i) of latch i is stable 0 or 1 by time T . In a worst-case manner we thus assume that its value is metastable M. Figure 3.12 shows the alignment of the latches' critical windows if they are non-overlapping for the linear TDC in Figure 3.11. Note that this can be achieved by increasing T d ; clearly though at the cost of increased time resolution. Figure 3.13 depicts a similar scenario, however with overlapping critical windows. In terms of guarantees on the readout, the design in Figure 3.12 only returns outputs of the form By contrast multiple metastable bits are possible in the design in Figure 3.13. In a worst-case model, decreasing T d below the critical window size thus results in larger resolution times. Give a metastable readout like 00M1111, one has several options to proceed:

t Start 0 T d W 0 W 1 W 2 . . . W n-1
c(n -1), . . . , c(0) = 0 k (0 | M | 1)1 n-k-1 . t Start 0 T d W 0 W 1 W 2 . . . W n-1
• Resolve metastability in the TDC before carrying on with the computation. This is achieved by giving the TDC, and in our case, the latches, sufficiently large time to stabilize. In terms of critical windows, this means to increase T , such that the probability of t lying within a W i is negligibly small. Clearly thus, this inhibits the reuse of the TDC in the meantime and thus decreases the sampling rate of the TDC.

• Copy the output to a memory and let it resolve there. Implementations, are, e.g., with synchronizer chains [START_REF] Kinniment | Synchronization and Arbitration in Digital Systems[END_REF], or letting it stabilize in a separate memory after copying there.

Again, the technique relies on increasing the time T until usage. This technique, however, allows for high sampling rates.

• Applying techniques from metastability-containing computation [START_REF] Friedrichs | Metastability-Containing Circuits[END_REF], and directly use the readout within a metastability-containing circuit. This includes stabilization during computation and no necessary stabilization -the latter, if the downstream circuit allows for this. Examples for applications that do not require stabilization [START_REF] Friedrichs | Metastability-Containing Circuits[END_REF][START_REF] Bund | Near-Optimal Metastability-Containing Sorting Networks[END_REF][START_REF] Lenzen | Efficient Metastability-Containing Gray Code 2-Sort[END_REF] will be discussed in Section 3.9.

Simple metastability-containing TDC. Interestingly the linear TDC from Figure 3.11 can be directly used in metastability-containing circuits. To see this, note that a readout may contain at most a single M. Given that the values are thermometer encoded, the precision as defined in Definition 71 on page 50 is 1, which is optimal. The resulting time resolution thus is 1

• T d .
The only drawback of this design is its large circuit size for larger dynamic ranges. Such designs would thus require a subsequent compact encoding, like BRGC.

Most designs for larger dynamic designs are counter-based. To deal with metastability, they protect the, typically binary, counter from metastable upsets by synchronizer chains. However, the resulting synchronizer delays of several clock cycles pose a deadtime for the TDC during which it cannot be used. An interesting exception for a counter-based design that follows a different approach to protect its counter(s) was presented by Mota et al. [START_REF] Mota | A flexible multi-channel high-resolution time-to-digital converter ASIC[END_REF]. The authors use two coarse counters, one driven by the rising and one by the falling clock transition. The counters are aligned so that at most one of them may become metastable for a measurement. To determine which of them is definitely not metastable, the thermometer encoded values must be read, and thus must be guaranteed to not be metastable.

High dynamic range metastability-containing TDCs. A standard technique to increase the dynamic range of linear TDCs is to fold them up into a ring and attach a coarse counter at one tap. Examples of such designs, e.g., are [START_REF] Henzler | Time-to-Digital Converters[END_REF] for regular folded delay lines and [START_REF] Dudek | A high-resolution CMOS time-to-digital converter utilizing a Vernier delay line[END_REF] for Vernier folded delay lines. Figure 3.14 on page 54 shows the design of a regular ring TDC with a generic coarse counter at one tap. The coarse counter has an increment input inc, an (low-active) enable input E, and a multi-bit output C. While generally binary counters with synchronizers are used, we have proposed three alternative designs in [START_REF] Függer | Metastability-aware memory-efficient time-to-digital converter[END_REF] that can be used in metastability-containing circuits. Also note that while inc may be triggered by rising, falling or both transitions in general, we will use designs where both transitions lead to an increment.

The three designs differ only in how the counter in Figure 3.14 is implemented and on the output encoding. We briefly sketch the designs with performance parameters time resolution and dynamic range. 1. TDC-bin. In this design, the counter comprises of two binary counters and a single bit indicating which counter value to use. This value is guaranteed to be correct and not metastable, while the other may be arbitrarily off. This design principle has been first described in [START_REF] Mota | A flexible multi-channel high-resolution time-to-digital converter ASIC[END_REF]. We gave a correctness proof in [START_REF] Függer | Metastability-aware memory-efficient time-to-digital converter[END_REF]. It has the following properties:

T d Start D Q c(0) E D Q c(1) E D Q . . . E D Q c(n -2) E inc C E Stop
+ Time resolution: T d + Design: Any binary counter design may be used.

-Memory: Two counter values need to be stored. If the binary counters have B bits, we store 2B + n bits for a measurement, which is slightly suboptimal.

-Post-processing: Inefficient for currently available metastability-containing operations.

2. TDC-gray. In this design, a Gray code counter is used as a coarse counter. It has the following properties:

+ Time resolution: T d -Design: Requires a custom counter and tighter timing constraints.

+ Memory: Optimal encoding. If the counter has B bits, we store B + log n bits for a measurement.

+ Post-processing: suitable for several existing metastability-containing operations 3. TDC-graybit. This design again uses a Gray code counter, and an additional single bit. The bit indicates whether an up-count should have taken place, shifting the tight timing constraints from the counter to a single latch.

+ Time resolution: T d + Design: Requires a custom counter, but less tight timing constraints.

+ Memory: Only a single bit memory overhead of encoding. If the counter has B bits, we store B + log n + 1 bits for a measurement.

-Post-processing: Inefficient for existing metastability-containing operations Before going into greater detail for the three designs, let us state some common properties for the ring TDC. Similar to the linear TDC, we denote the output of latch i ∈ {0, . . . , n -2} in Figure 3.14 with c(i). If not stated otherwise, we will use c(i) also for the value of signal c(i) at time T > 0 after the Stop signal transition. We then have: Lemma 75 ( [START_REF] Függer | Metastability-aware memory-efficient time-to-digital converter[END_REF]). Assume that latches have zero switching time and thus empty critical windows. Also assume that the coarse counter C is a single-bit, binary latch and denote its output by c(n-1). Denote by cnt the sum of the total number of latch output transitions of all stages between the starting and stopping signals, i.e., the total count of the TDC. Then one of the two cases applies:

• The ring oscillator made a number of full rounds and all latch outputs are of the form 0 . . . 0 or 1 . . . 1. Then, cnt mod n = 0 and ∀i, j ∈ {0, . . . , n -1} : c(i) = c(j) .

• The ring's state was captured in between two full rounds and the latch outputs are of the form 0 . . . 01 . . . 1 or 1 . . . 10 . . . 0. Then,

c(cnt mod n) = c(cnt +1 mod n) and ∀i ∈ {0, . . . , n -1} \ {cnt mod n} : c(i) = c(i + 1) .
This allows one to determine cnt mod n from the latch outputs c(i). A more refined analysis with taking into account the fact that a single bit may become metastable, finally yields: Corollary 76 ( [START_REF] Függer | Metastability-aware memory-efficient time-to-digital converter[END_REF]). Assume that the critical windows of the latches are non-overlapping. Then, after potential metastability resolved, cnt mod n can be determined according to Lemma 75 with precision 1.

TDC-bin.

In this design the counter is implementation by two binary counters [START_REF] Mota | A flexible multi-channel high-resolution time-to-digital converter ASIC[END_REF]. Both counters and the latch are initialized to 0. Output b ∈ B of latch L serves as a select bit for the two counters: counter C b is used. The circuit, and the following delay constraints, then ensure that C b is not metastable.

In particular, we require: Denote by W C0 and W C1 the counters' critical windows. Denote by W L the critical window of latch L. For a window W , denote by W i , with i ∈ N + , the i th interval of W , ordered by time, if it exists. Then we require,

W 1 L < W 1 C0 < W 2 L < W 1 C1 < W 3 L < W 2 C0 < . . . .
The resulting alignment is shown in Figure 3.16 on page 56. We achieve this alignment by the following design choices: For simplicity assume that

|W C0 | = |W C1 |. Then • W i L < W i C b
is ensured by making the delay latency T Buf sufficiently large.

• W i C b < W t+1
L is ensured by choosing the ring size n large enough such that counter C b completes an increment before the transition traverses the ring. The proof relies on observing that a stable b implies a stable C b , and a metastable b implies that both C 0 and C 1 are stable. It is then shown that all these counts are set correctly to obtain the lemma's statement.

Start

T d W 1 0 W 1 1 . . . W 1 n-2 W 1 L W 2 0 W 2 1 . . . W 2 n-2 W 2 L W 3 0 W 1 C0 T Buf W 1 C1 T Buf
Lemma We finally obtain for the readout of TDC-bin:

Theorem 78 ([29]
). After metastability of the latches has been resolved,

cnt = (2C b + b)n + x 1-b ,
where x 1-b is the number of latches having value 1 -b. Moreover, it is exactly the leading x 1-b latches that have value 1 -b.

Memory-wise, if the binary counters have B bit, a measurement requires 2B + n bit. This is below optimal: The maximum cnt value (2 B+1 -1)n + (n -1) of such a measurement would only require B + 1 + log n bit in an optimal encoding. TDC-gray. The design TDC-gray, by contrast, uses an optimal B + log n bit per measurement. Its coarse counter is shown in Figure 3.17. At its core there is a single Gray code counter (shown in blue in the figure), and a successive register of the counter's bit width. While in general, the design works with arbitrary Gray codes, we have shown that BRGC counters are particularly favorablewe discuss this later on in the section.

When a rising transition arrives at the inc input, it is first translated into a pulse by the Xor and the buffer. The buffer delay T Buf is chosen sufficiently large such that the rising transition then triggers the latching of the counter output by the register. Only then, and accounting for the register's hold time, the counter is triggered to increment. The resulting critical windows and their alignment are shown in Figure 3.18 on page 57. While the counter increment may take almost a full round-trip time of the TDC cycle, the register's critical window intervals must be roughly of the same size as the critical window interval sizes of the latches along the ring; see Figure 3.18. While the Gray code from the coarse counter is already optimally compressed, the thermometer encoded latch states require further compression. We proposed to compress them into a Gray code, too.

Stop inc

T del inc E C T Buf D Q E R C

Start

T d W 1 0 W 1 1 . . . W 1 n-2 T d + T del T d + T del + T Buf counter W 1 C W 2 0 W 2 1 . . . W 2 n-2 T d + T del T d + T del + T Buf

Lemma 79 ([29]

). Consider an arbitrary log n -bit Gray code. Suppose that we are given an n-bit ring latch state of the form 11..1M00..0 or 11..100..0. If a possible M is resolved to either 0 or 1, the resulting string is a thermometer encoding of either r or r + 1 for some r ∈ [n]; if there is no M, the string is a thermometer encoding of r ∈ [n + 1]; i.e., it has precision of 1.

There is a purely combinational circuit of at most n Xor gates and depth at most log n that transforms all such inputs into the Gray code, in the sense that in case of metastability in the input, (i) at most one output bit is metastable, and (ii) resolving it to either 0 or 1, the encoded number becomes either r or r + 1; i.e., the circuit preserves precision of 1.

Since the circuit maps inputs with precision 1 to outputs with precision 1, we may say that the function that it implements is metastability-containing. Note that technically, our definition of a metastability-containing function does not apply, since input and output encoding are not identical -however, a generalized version does.

The key observation in the proof of Lemma 79 is that a counter increment, triggered by a latch being set to 1, can be viewed as negating a subset of the output bits (implemented by Xor gates). Clearly, though, while in the first round 1s have to be counted, in the second round 0s have to be counted, a priori requiring two such encoding circuits. Luckily, in the case of BRGC the same circuit may be used. For that purpose we refer the reader to Table 3.1: in fact counting leading 1s is equivalent to counting leading 0s and negating all inputs. In BRGC it turns out that this results in a negation of the left-most BRGC bit; see Table 3

0 0 0 0 0 0 0 0 0 0 7 1 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 2 1 1 1 0 0 0 0 0 1 0 3 1 1 1 1 0 0 0 1 1 0 4 1 1 1 1 1 0 0 1 1 1 5 1 1 1 1 1 1 0 1 0 1 6 1 1 1 1 1 1 1 1 0 0 7 0 0 1 1 1 1 1 1 1 0 1 1 0 0 1 1 1 1 1 1 1 1 2 0 0 0 1 1 1 1 1 1 0 3 0 0 0 0 1 1 1 0 1 0 4 0 0 0 0 0 1 1 0 1 1 5 0 0 0 0 0 0 1 0 0 1 6
The two Gray code encoded values are optimal in terms of memory efficiency and maintain precision of 1 in presence of metastable inputs. We thus obtain:

Corollary 80 ([29]

). Using a B-bit Gray code coarse counter and the XOR-tree circuit from Lemma 79, a measurement can be stored as a tuple of two Gray codes, using B + log n bits, without losing precision.

In fact, and again making use of the peculiarities of BRGC encoded values, we may easily combine the two Gray code values into a single BRGC encoded values that encodes the TDC value:

Theorem 81 ( [START_REF] Függer | Metastability-aware memory-efficient time-to-digital converter[END_REF]). If we use a BRGC coarse counter and n is a power of 2, then just the concatenation of (a) the output of the above Xor-tree circuit, without the need to negate any of its output bits, and (b) the output of the BRGC counter yields a BRGC encoding of the TDC measurement value. TDC-graybit. The third coarse counter design is shown in Figure 3.22 and its critical windows in Figure 3.23. The design comprises of a Gray counter C and a latch L. The purpose of the latch is to "shrink" the critical window that the Gray counter may have. While the counter may get metastable in one bit during a large window W C , the state of the latch with the short critical window can be used to determine whether the counter should be even or odd -and correct the counter after stabilization accordingly.

Stop

Start

T d W 1 0 W 1 1 . . . W 1 n-2 W 1 L W 2 0 W 2 1 . . . W 2 n-2 W 2 L W 3 0 W 1 C T del W 2 C T del

Minimum, Maximum, Median, and Sorting

TDCs are widely used modules at the interface to an outer environment. We will next discuss an application of metastability-containing techniques related to computation. Figure 3.24 on page 60 shows a circuit that computes the minimum of two thermometer encoded values. The circuit is efficiently realized by bit-wise And of the inputs. An analogous circuit with bit-wise Or computes the maximum of the two inputs.

Observer that the minimum and the maximum of thermometer encoded values, with the output again being thermometer encoded, is a metastability-containing function. For example, the minimum of an input with precision 0, say x = 0001111, and and input with precision 1, say y = 0000M11, yields min(x, y) = 0000M11; which has precision 1. Further, the circuit in Figure 3.24 is metastability-containing as has been observed in [START_REF] Friedrichs | Metastability-containing circuits[END_REF]. With metastability-containing versions of minimum and maximum, computing the median, midvalue, and sorting in general, are readily computed in a metastability-containing way: minimum and maximum are combined to a 2-sort element, which is then assembled according to techniques from sorting networks [START_REF] Ajtai | An 0(n log n) sorting network[END_REF][START_REF] Kenneth | Sorting networks and their applications[END_REF].

The 2-sort with the minimum circuit shown in Figure 3.24 requires inputs and outputs to be thermometer encoded. However, more efficient encodings like BRGC are preferable for larger values. Indeed, first observe that the minimum and maximum functions are metastability-containing for values that are BRGC encoded as well: precision 1 at the inputs results in precision 1 at the outputs. Second, Corollary 61 on page 47 shows that there also exists a metastability-containing circuit that implements BRGC-encoded maximum and minimum. A priori, such a circuit may be large (exponential in the input size). Efficient implementations have been shown to exist [START_REF] Lenzen | Efficient metastability-containing gray code 2-sort[END_REF][START_REF] Bund | Near-optimal metastability-containing sorting networks[END_REF][START_REF] Bund | Optimal metastability-containing sorting networks[END_REF], however.

Controllable Oscillator

We will next discuss a component that has been used in several of our designs that use metastabilitycontaining circuitry such as the link controller in [START_REF] Bund | Synchronizer-free digital link controller[END_REF]. In contrast to the previously discussed components, the purpose of this component is not to compute a function, but rather to produce an oscillating signal with a controllable frequency. We will also explain what we mean with metastability-containing in this context; although we do not formalize the term for such components.

A controllable oscillator, in our context, is a component with a temperature encoded input i and a single output port o that will be the oscillating output. In its simplest form, the input is a single bit i. For simplicity, we assume this in the following, although the concept is easily generalized to multiple bits.

For ease of analysis, we will sometimes refer to two other underlying output representations that induce the binary output signal: c and C. We denote by C(t) ∈ N the discrete clock count/value at Newtonian time t ∈ R; that is, the number of active transitions made by output o until time t. Further, let c(t) ∈ R be the output's underlying continuous (normalized) phase signal at time t. For simplicity of analysis we assume normalization of the phase by 2π, i.e., the phase of a full clock period is 1 and not 2π. Thus C(t) = c(t) . The instantaneous frequency of c is dc/dt.

Let the frequency bounds s -≤ s + ≤ f -≤ f + be from R + 0 and the latency T osc be from R + 0 . A controllable oscillator then fulfills: (C4) If i is neither constant 0 nor constant 1 during time [t -T osc , t], we say that the oscillator is unlocked at time t.

Note that clocks in slow mode are never faster than clocks in fast mode.

While in absence of metastable inputs, in our case this means ruling out i = M, many designs of controllable oscillators have been proposed, care has to be taken for designs that behave according to the above specification in presence of metastability. Most designs, however violate (C1) in presence of a metastable input bit. We thus call the oscillator metastability-containing if it grantees constraint (C1).

In [START_REF] Bund | Synchronizer-free digital link controller[END_REF], we proposed to use starved-inverter ring oscillators that guarantee such behavior [START_REF] Hajimiri | Jitter and phase noise in ring oscillators[END_REF]. A starved inverter is an inverter whose propagation delay can be controlled by starving its power supply. This can be done via an input bit that, if set, reduces power supply, and if not set, does not do so or to a less extent. Aligning such inverters along a ring results in a ring oscillator whose period is controllable via the starved inverter propagation delays. The transistor level implementation used in [START_REF] Bund | Synchronizer-free digital link controller[END_REF] followed the design presented in [START_REF] Shruti Suman | Analysis and design of current starved ring vco[END_REF], however without the full control logic overhead typically required to drive the starved inverter cells, since our input values are already temperature encoded and can be directly used to control the inverters. Proper decoupling by intermediate buffers is used in order to minimize unwanted effects on the oscillator frequency by the control logic and by the oscillator output's downstream logic. Not all inverters in the ring need to be starved and a single input bit can control one or several starved inverters. This is useful to set the sensitivity of the oscillator to input changes.

Most importantly, why is this design metastability-containing? Observe that (continuousvalued) propagation delays of the inverters are controlled via the (continuous-valued) reduced V dd with the oscillation frequency extremes being s -and f + . Setting the input to M will lead to a V dd between those for logical 0 and 1, and thus will result in an inverter propagation delay between those for inputs 0 and 1. The resulting oscillation frequency thus remains within s -and f + . In particular no glitches will be produced by the oscillator.

Byzantine Fault-tolerant Clock Synchronization

In this section, we discuss a more high-level application of metastability-containment techniques that was presented in [START_REF] Friedrichs | Metastability-containing circuits[END_REF]. The problem of distributed clock synchronization is to make a distributed system of n ∈ N + processes, generate clock ticks simultaneously [START_REF] Lamport | Synchronizing clocks in the presence of faults[END_REF][START_REF] Lynch | Distributed algorithms[END_REF]. Interpreting the clock generation times on a global Newtonian timeline as local output values, the problem is closely related to the problem of repeatedly solving approximate consensus [START_REF] Dolev | Reaching approximate agreement in the presence of faults[END_REF].

Both problems are well studied in distributed computing [START_REF] Lynch | Distributed algorithms[END_REF], with variants differing in assumptions on which nodes can communicate, stability of the underlying network, and process faults.

Faults. Focusing on algorithms implemented in hardware, a first question is for a valid model of faults in such systems.

There is a large body of literature in the circuit community on types of faults and mitigation strategies at different levels of abstractions. For an introduction with a focus on faults in dependable systems, we refer the reader to Kopetz [START_REF] Kopetz | Real-time systems: design principles for distributed embedded applications[END_REF]. An overview on trends is presented by Constantinescu [START_REF] Constantinescu | Trends and challenges in vlsi circuit reliability[END_REF].

Radiation induced single event upsets (SEUs), i.e., bit-flips of storage elements, have received particular attention in circuits intended for critical missions. Radiation hardened synchronous [START_REF] Das | Razorii: In situ error detection and correction for pvt and ser tolerance[END_REF] and asynchronous [START_REF] Kuentzer | Radiation hardened click controllers for soft error resilient asynchronous architectures[END_REF] designs have been proposed. Radiation induced single event transients (SETs), i.e., glitches within the combinational logic, have gained in importance though [START_REF] Ferlet-Cavrois | Single event transients in digital cmos-a review[END_REF][START_REF] Andjelkovic | Characterization and modeling of set generation effects in cmos standard logic cells[END_REF][START_REF] Hofbauer | Pulse shape measurements by on-chip sense amplifiers of single event transients propagating through a 90 nm bulk cmos inverter chain[END_REF] and may result in downstream bit-flips, delay faults, and glitches. Potential results of such faults are inconsistent reception of signals and even metastable upsets. Simple crash models are thus not sufficient for low-level circuits if high coverage is the goal. Byzantine faults, by contrast, capture inconsistent message receptions. We have argued in this chapter that Byzantine faults, however, are still not sufficient to cover metastable upsets with non-binary values.

Model. Let us consider the classical Byzantine fault-tolerant message passing model [START_REF] Lynch | Distributed algorithms[END_REF], here: The communication system by which the n processes communicate is fully-connected and stable, and up to f < n/3 nodes may fail in an arbitrary, i.e., Byzantine, way. Messages latencies between correct nodes are within some [τ -, τ + ]. Every node has access to a local (continuous) clock with rate [1, 1 + ], where > 1. For simplicity we assume that all correct nodes start simultaneously at time 0, although we note that this condition can be relaxed.

Denote by t i (k), with i ∈ [n] and k ∈ N + , the time node i makes its k-th tick. Further let C i (t) be the number of ticks made by node i until including time t. An algorithm solves distributed clock synchronization, if there exist accuracy bounds α -, α + > 0 and d > 0, as well as a skew σ > 0, such that in all executions:

• For all correct nodes i ∈ [n], and all t , t ∈ R + 0 with t > t,

C i (t ) -C i (t) ∈ [(t -t)α --d, (t -t)α + + d] . (3.15)
• For all k ∈ N + , and all correct nodes i, j ∈ [n],

|t i (k) -t j (k)| ≤ σ . (3.16)
The Lynch-Welch distributed clock synchronization algorithm [START_REF] Lundelius | A new fault-tolerant algorithm for clock synchronization[END_REF] was shown to solve distributed clock synchronization. Without going into details, the algorithm repeatedly lets a node (i) make a tick and broadcast it to all other nodes, (ii) estimate its offset to the other clocks based on the received messages and calculate a correction term from it, and (iii) adapt the time when to produce the next tick based on the correction term. Care has to be taken in that ticks of correct nodes are received timely such that the correction factor can be computed before the next tick has to be made. This results in conditions on (lower and upper bounds of) message delays and the drift . Central to the algorithm is how the correction factor is computed from the received clock offset estimates: the f largest and smallest values are discarded (setting estimates corresponding to non-received values to ∞), and the mid-point of the interval I of the remaining clock offsets is computed as

min(I) + max(I) 2 . (3.17)
Variants of this algorithm have been implemented in the Time-Triggered Protocol (TTP) [START_REF] Kopetz | The time-triggered architecture[END_REF] and Flexray [START_REF] Belschner | Flexray communication protocol[END_REF] for clock synchronization in fault-tolerant systems. Both are software-hardware based implementations and achieve a skew in the order of microseconds. To obtain higher operating frequencies and a better skew, pure low-level hardware implementations are inevitable because of jitter. Kinali et al. [START_REF] Kinali | Fault-tolerant clock synchronization with high precision[END_REF] implemented the Lynch-Welch algorithm on a set of FPGA boards All known implementations, however, synchronize potentially metastable inputs before computations.

Inherently, such implementations face the problem of metastable upsets: If the estimated clock offset of node i with respect to node j is digital, there exists an offset between the two clocks that results in a metastable offset measurement. While the above implementations [START_REF] Kopetz | The time-triggered architecture[END_REF][START_REF] Belschner | Flexray communication protocol[END_REF][START_REF] Kinali | Fault-tolerant clock synchronization with high precision[END_REF] solve this problem by making the probability of an upset arbitrarily small by synchronizing i's signal into j's clock domain, a solution with synchronizers increases the control loop's latency, i.e., the algorithm's synchronization period. Latency is important for high-precision synchronization, however, since clocks drift apart with rates up to during the controller latency. Further, despite increasing synchronizer stages reduces failure rates -at the cost of additional latency -a non-zero probability of failing remains. This is particularly important for the following reasons:

• Clock synchronization algorithms that strive for high precision need to operate at high synchronization frequencies. Metastable upsets become (roughly) proportionally more likely with increased frequencies.

• The Lynch-Welch algorithm requires a fully connected communication network. Metastable upset probabilities thus scale quadratically with the number of nodes.

• The point of the clock synchronization algorithm is to produce clock transitions close in time.

Standard formulas that assume uniformly distributed data arrival times within the clock period thus do not apply. Rather the algorithm potentially acts like circuits that deliberately drive a circuit into metastability -see the literature on deep metastability measurements [START_REF] Kinniment | Measuring deep metastability[END_REF][START_REF] Zhou | On-chip measurement of deep metastability in synchronizers[END_REF][START_REF] Polzer | Refined metastability characterization using a time-to-digital converter[END_REF].

• As noted before, the standard formula for metastable upset rates assumes uniform arrival times. This also is not a valid model for Byzantine nodes that drive input signals. The signals may not only be deliberately aiming to produce metastable faults by controlled transitions or high frequency oscillations, but may also be unclean signal transitions. In particular, any intermediate voltage may be applied by the Byzantine node.

For the last two point, an upper bound on the probability of faults induced by metastable upsets is impossible without further restrictions made on the Byzantine nodes.

In [START_REF] Friedrichs | Metastability-containing circuits[END_REF] we showed that metastability-containing circuits, and in particular the TDC and sorting discussed previously, can be used to design the first distributed clock synchronization algorithm that indeed tolerates Byzantine faults in a model that also captures metastability. The algorithm is a metastability-tolerant implementation of the Lynch-Welch algorithm. Figure 3.25 shows its main modules ad how they are interfaced. The phase offset is first measured by TDCs, one for each of the n-1 neighboring nodes. Offsets are assumed to be BRGC encoded; see Section 3.9.1 for such designs. Sorting networks, respectively parts of it, are used to select the (f + 1)-th and (nf )-th largest offset value; see Section 3.9.2 for solutions. The two resulting BRGC outputs are re-encoded to temperature encoded values. While we did not provide circuits for this, the function is readily seen to be metastability-containing, and the existence of metastability-containing versions of such circuits follows from Theorem 58 on page 47. It remains to show the existence of an oscillator whose frequency can be controlled depending on two temperature-encoded values, that potentially contain metastability. A design analogous to the oscillator presented in Section 3.9.3 can be used for this purpose. Note that we do not need to calculate the mid-point in thermometer encoded values, since the controllable oscillator does not depend on correct thermometer representations, but rather on the number of bits set to 1. Assuming we are in the linear control region, we may thus simply concatenate min(I) and max(I) and divide the linear slope by 2.

One observes that the proposed circuit implements the Lynch-Welch algorithm and preserves precision from the inputs to the outputs. We thus obtain: Theorem 82 ( [START_REF] Friedrichs | Metastability-containing circuits[END_REF]). In the circuit model that includes metastable upsets, the circuit in Figure 3.25 solves the distributed clock synchronization problem in a fully connected network of n > 1 nodes, in presence of up to f < n/3 Byzantine faulty nodes.

Link Controller

In [START_REF] Bund | Synchronizer-free digital link controller[END_REF] we used techniques from metastability-tolerant computing in a link controller between a sender and a receiver with their respective clock domains. Communication across clock domains, e.g., occurs in Globally Synchronous Locally Asynchronous (GALS) system [START_REF] Teehan | A Survey and Taxonomy of GALS Design Styles[END_REF][START_REF] Krstic | Globally asynchronous, locally synchronous circuits: Overview and outlook[END_REF]. From Marino's work [START_REF] Marino | General theory of metastable operation[END_REF], we know that under realistic conditions and uncorrelated clock domains, such a communication is inherently prone to metastable upsets. Different mitigation strategies in link controllers have been proposed to handle this problem:

• Gating the clock [START_REF] William | Congestion and Starvation Detection in Ripple FIFOs[END_REF] with signals that measure fill levels to prevent overflow and underrun of an asynchronous FIFO with synchronous input and output. This technique requires almost-full flags that have to be protected against metastability; making upset probabilities sufficiently small but with a remaining non-zero probability of metastable upsets.

• Clock-pausing [START_REF] Mullins | Demystifying Data-Driven and Pausible Clocking Schemes[END_REF][START_REF] Najvirt | How to Synchronize a Pausible Clock to a Reference[END_REF], at the cost of unbounded start-up times in presence of metastability.

• Synchronizers [START_REF] Chelcea | Robust Interfaces for Mixed-Timing Systems[END_REF][START_REF] William | The Even/Odd Synchronizer: A Fast, All-Digital, Periodic Synchronizer[END_REF][START_REF] Dobkin | High Rate Data Synchronization in GALS SoCs[END_REF][START_REF] Jackson | Gradual Synchronization[END_REF] at the cost of increased latency and non-zero probability of metastable upsets.

The design in [START_REF] Chelcea | Robust Interfaces for Mixed-Timing Systems[END_REF] is based on a mixed-clock first-in first-out pipeline (FIFO) with flow control logic. Synchronized full/empty and almost full/empty signals are used as handshaking signals. Its throughput is one data item per clock cycle until the almost full signal is raised; afterwards, the "true" full signal has to be considered, at the cost of increased latency and lower throughput.

In [START_REF] Dobkin | High Rate Data Synchronization in GALS SoCs[END_REF], a locally delayed latching approach is proposed: conflicting read/write operations are delayed by an asynchronous controller with a Mutex element. The controller's latency is in the order of 20 gate delays. The minimum feasible clock cycle is at least 69 gate delays.

Gradual synchronization [START_REF] Jackson | Gradual Synchronization[END_REF] allows fine-grained interweaving of synchronization and computation, also shifting conflicting ripple FIFO requests by Mutex elements at each stage.

A notable exception in how synchronizers are used is the work by Dally and Tell [START_REF] William | The Even/Odd Synchronizer: A Fast, All-Digital, Periodic Synchronizer[END_REF]. They propose a design where upset probabilities can be made arbitrarily small without increasing latency: synchronizers continually determine sender-receiver phase offsets. The offsets can then be used to skip sender/receiver cycles when upsets could occur. A drawback is that the frequency and phase measurement circuits require accurate phase tracking and can account for slow phase drifts only.

• Synchronizing sender/receiver clocks, i.e., controlling their phase offset. The benefit of this approach is that, once synchronized, communication can be done in a lightweight provably metastability-free way. The approach from [START_REF] Bund | Synchronizer-free digital link controller[END_REF], presented in this section, also falls into this class. The closest work to our approach presumably is Polzer et al. [START_REF] Polzer | A Metastability-Free Multisynchronous Communication Scheme for SoCs[END_REF]. By using the distributed DARTS clock generation mechanism [START_REF] Függer | Reconciling fault-tolerant distributed computing and systems-on-chip[END_REF], a buffer size of 9 and latency of 9 clock cycles was achieved for a receiver-sender clock shift of 4 ticks at around 25 MHz in an FPGA. While these numbers clearly can be improved in ASIC designs, DARTS inherently is slower than our approach.

Metastability-containing controller. In [START_REF] Bund | Synchronizer-free digital link controller[END_REF] we presented an alternative design for a link controller. The design is for a unidirectional link from a synchronous sender node Snd to a synchronous receiver node Rcv. For simplicity we assume that the communication is unidirectional, although a generalization to bidirectional communication is possible. Sender and receiver have two distinct controllable oscillators as clock sources. The controller makes sure that both oscillators are such that the link's buffer never underruns, overflows, or accesses the same data item at the same time. Figure 3.26 shows the setup. It comprises of three parts: (i) the tunable oscillators Osc snd and Osc rcv , (ii) the (ring) buffer Buff, and (iii) the digital link controller Ctrl.

The link operates as follows: At every active transition of the sender clock clk snd , the sender writes data to a ring buffer of even size N ∈ 2N + . On every active transition of the receiver clock clk rcv , the receiver reads data from the ring buffer. Buffer cells are numbered from 0 to N -1. We assume that the buffer is addressed by two pointers -the sender and the receiver pointer, both of which are incremented modulo N every respective clock tick.

Controller model. Assume a sender and a receiver controllable oscillator that follows the specification given in Section 3.9.3. Call their single-bit inputs md s and md r , respectively. We denote their phase at time t ∈ R + 0 with c s (t) and c r (t), respectively. Additionally assume that the two oscillators are started roughly at the same time, i.e., within some δ ≥ 0 maximum initial phase offset:

Q D ffa 0 1 s F 0 F 1 Q D ffs clk rcv md rcv md snd Figure 3
.27: Gate-level circuit of the synchronous controller ClockedTh. The controller is for a ring with N = 2 cells. Flip-flop ffa stores the address (modulo 2) that is sampled and ffs the sampled full/empty flag. From [START_REF] Bund | Synchronizer-free digital link controller[END_REF].

Solution. Figure 3.27 depicts the controller ClockedTh, a clocked gate-level circuit that has been proven to be a correct controller in [START_REF] Bund | Synchronizer-free digital link controller[END_REF].

Besides correctness, we have shown bounds on two performance measures: The link's latency, i.e., the time between consecutive accesses of the sender and receiver to the same cell plus the setup/hold time at the receiver (as the data should be stable before it is used). The link's throughput, i.e., its rate of delivered packets. We obtained:

Theorem 85 (from [START_REF] Bund | Synchronizer-free digital link controller[END_REF]). For

∆ = (f + -s -)(T osc + 1/s -+ τ max ) + f + max{τ s , τ r } + max{δ, f + τ s /2} and N ≥ 2∆
the controller ClockedTh is correct and the link has latency N/s -and throughput 1/s -.

The proof is by showing that a non-implementable, ideal, continuous controller is correct and then showing that the controller ClockedTh implements the ideal controller if parameters are chosen properly.

The link controller with the successive oscillators bears some similarities to phase locked loop (PLL) designs [START_REF] Chung | An All-Digital Phase-Locked Loop for High-Speed Clock Generation[END_REF][START_REF] Abadian | A New Low-Power and Low-Complexity All Digital PLL (ADPLL) in 180 nm and 32 nm[END_REF]: its purpose is to control a frequency with respect to a phase difference. The controller can be viewed as an all-digital phase detector. However, the biggest difference is that our design is a distributed setup with neither the receiver nor the sender dictating the frequency of the other.

Performance and comparison. Table 3.2 shows a comparison of our controller synthesized for the UMC 65 nm library. We compare the link's performance to the most closely related works, Polzer et al. [START_REF] Polzer | A Metastability-Free Multisynchronous Communication Scheme for SoCs[END_REF] and Dally and Tell [START_REF] William | The Even/Odd Synchronizer: A Fast, All-Digital, Periodic Synchronizer[END_REF]. Table 3.2: Performance and hardware overhead (buffer size N , gates, flip-flops, oscillator type) of the proposed controller with a tunable 2.0 to 2.3 GHz oscillator, [START_REF] William | The Even/Odd Synchronizer: A Fast, All-Digital, Periodic Synchronizer[END_REF], and [START_REF] Polzer | A Metastability-Free Multisynchronous Communication Scheme for SoCs[END_REF]. From [START_REF] Bund | Synchronizer-free digital link controller[END_REF]. The controller operates within 2-2.3 GHz. VHDL and Spice simulations were in accordance with predictions from theory, and no underrun or overflow was detected in the simulations. From [START_REF] Bund | Synchronizer-free digital link controller[END_REF].

ClockedTh

The VHDL code for the behavioral simulation of a ring buffer of N = 2 elements is shown below. Observe the explicit generation of X for the full-flags whenever a cell is written and read. The code outputs X in a worst-case manner for τ time, but can be adjusted to generate X for a (uniformly) random time d ∈ [0, τ ] as indicated in the code.

State Machines

While the principles of metastability-containing functions and circuits can be immediately applied to state machines, and in particular, the their state transition functions and the output functions as is, a more in-depth treatment of state machines is appropriate. The following section is based on [START_REF] Tarawneh | Metastability tolerant computing[END_REF] where we studied a subclass of state machines where metastability is restricted to a single input bit.

We start with a definition that eases writing specifications in the ternary logic B M .

Definition 86 (from [START_REF] Tarawneh | Metastability tolerant computing[END_REF]). For strings x, y

∈ B n M , with n ≥ 1, let x * y ∈ B n M such that ∀i : (x * y) i = x i if x i = y i M otherwise .
Then, for g : B n → B m , the metastable closure [g] : B n M → B m M , can be compactly written as ∀i : [g] i (x) = *

x ∈Res(x)

g i (x ) .
Recall that the transition function f in a state machine depends on the current state and the input. We refer to this input as datapath control as opposed to datapath data that does not influence state transitions. Datapath control is assumed to be c ≥ 0 bits wide and the state to be encode with b ≥ 1 bits. States from S = {0, . . . , |S|}, with |S| ≥ 1, are encoded via the injective function ε : S → B b . If clear from the context we refer both to s ∈ S and ε(s) as a state.

We may now additionally interpret a state s in B b M as superpositions of classical states, i.e., a set of states s M that comprises of all ε -1 (s ) with s ∈ Res(s), if it is well-defined for all such s , and a default value ⊥ otherwise.

An execution of a state machine is defined analogously to the round model in Section 3.3.3. We just deviate in one aspects to adapt the model to a more refined analysis for state machines:

• Executions are allowed to non-deterministically evolve via arbitrary resolutions of the current state. In particular, denoting by x(r) the datapath control part and by y(r) the encoded state at round r ≥ 1, it is y(r) ∈ [f ](y(r -1), x(r -1)) .

(3.18)

In case y(r -1) = ⊥, we allow arbitrary y(r) from B b M . • Further we assume that only the initial input is potentially metastable, and that after an a priori defined k ≥ 1 number of rounds, metastability has resolved. We thus have for

r = k + 1, y(r) ∈ Res ([f ](y(r -1), x(r -1))) . (3.19)
Example 87. Assume a system with two datapath control bits req and A. Figure 3.29 on page 69 depicts an example state machine and an execution over 3 rounds. We assume that states are In the execution the superposition collapses at time 3 into a single state. From [START_REF] Tarawneh | Metastability tolerant computing[END_REF].

encoded as ε(0) = 000, ε(1) = 001, ε(2) = 011, ε(Op1) = 010, ε(3) = 101
, and ε(Op2) = 100. For the input sequence, we assume that req is of the form 0 * (M)?1 ω , and A is either 0 ω or 1 ω . This corresponds to a scenario where the circuit has already received the (stable) control data A, and is waiting to receive the req to trigger the computation.

In the example, we see that the encoding is optimal for the given input traces: the set of superpositions is minimal. Further, observe that at round 3 the state superposition has collapsed into a single state -this may be the case either by the non-determinism of the execution, or enforced by assuming k = 2.

By contrast assume the encoding as before, but with ε(1) = 111. One observes that at time 1, the state machine is in the superposition state ⊥ allowing arbitrary future behavior.

The encoding in Example 87 is ad-hoc. So the question arises, whether there exist efficient (in terms of bit-size) encoding, that have the same properties as the presented encoding -an optimal superposition set. In [START_REF] Tarawneh | Metastability tolerant computing[END_REF] we show that this is the case, and present two efficient encodings for state machines with only a single initially potentially metastable req bit that behaves like in Example 87. The solutions are based on appending additional bits to the state encodings that mark the path (e.g., distance as thermometer encoded bits) from the initial state for distances up to k. The question of optimal encodings with log(|S|) bits is an open problem, however.

A Circuit for Voltage Droop Tolerance

In [START_REF] Függer | Fast all-digital clock frequency adaptation circuit for voltage droop tolerance[END_REF] we applied the techniques of building metastability-containing circuits to design a new clock frequency adaptation circuit. The purpose of this circuit is to slow down the clock frequency driving a synchronous circuit upon detection of a voltage droop, i.e., a sudden power supply drop. Slowing down the clock frequency is required if the synchronous circuit operates near its maximum allowed clock frequency and small droops would already lead to violations of the setup-constraint between the critical path and the launching and capturing clock paths.

Alternatively, the classical solution is to equip the clock cycle with large enough guardbands. However this is costly in terms of performance: For example, Bowman et al. [START_REF] Bowman | Dynamic variation monitor for measuring the impact of voltage droops on microprocessor clock frequency[END_REF] showed that a 12% droop in a 45 nm microprocessor required to slow down the clock frequency by 16% to accommodate the increased critical path delay.

High-frequency voltage droops. V DD variations exists at different timescales, ranging from slow temperature and aging effects to GHz localized noise. While slow variations can be coped with by classical controllers, and multiple GHz noise is too localized and fast to be coped with by current circuits, it is the MHz domain that has recently been addressed with fast frequency adaptation circuits. Typically effects in this domain are IR drops due to parasitic resistances in the power supply net and dI/dt induced noise due to die and package LC [START_REF] Kurd | Next generation intel core™ micro-architecture (nehalem) clocking[END_REF][START_REF] Jiao | Circuit design and modeling techniques for enhancing the clock-data compensation effect under resonant supply noise[END_REF][START_REF] Fojtik | A fine-grained gals soc with pausible adaptive clocking in 16 nm finfet[END_REF]. Both are varying in time, e.g., due to activity profiles. Measurements of such V DD variations when injecting sudden switching activity changes showed damped oscillatory behavior [START_REF] Fojtik | A fine-grained gals soc with pausible adaptive clocking in 16 nm finfet[END_REF].

Previously existing solutions. In the following we focus on synchronous and GALS solutions; there is a large body of work on handshaked and (partially) clockless circuits, however, which, additionally to other factors, is motivated by the above problems.

An interesting, and deceptively simple, solution is a ring oscillator whose delay lines are configured to have similar voltage-delay characteristics as critical path delays in the synchronous circuitry they clock [START_REF] Cortadella | Ring oscillator clocks and margins[END_REF]. The ring oscillator is then used as an almost instantaneously adapting frequency adaptation module. This solution can be either used globally, or locally do generate clocks for the synchronous islands in a GALS. Fojtik et al. [START_REF] Fojtik | A fine-grained gals soc with pausible adaptive clocking in 16 nm finfet[END_REF] proposed such a solution, which additionally uses circuitry to communicate between such islands without the need for deep synchronizers. They propose to combine pausible clocking with ring oscillators. They also advocate the use of local frequency adaptation over centralized, global adaptation since the latter suffers from long insertion delays of the clock tree, which may be prohibitive for fast reaction to droops. Further, local adaptation models reduce droops as they smoothen activity profiles [START_REF] Fojtik | A fine-grained gals soc with pausible adaptive clocking in 16 nm finfet[END_REF].

A large body of solutions is based on a droop detector combined with a frequency adaptation module. Solutions with frequency adaptation modules have the advantage that phase relations between local adaptation modules typically are directly available as digital states. This may be important for fast communication between such synchronous islands. Solutions with slow and fast adjusting frequency adaptation based on PLLs [START_REF] Tschanz | Adaptive frequency and biasing techniques for tolerance to dynamic temperature-voltage variations and aging[END_REF] and/or selecting among clock signals after droop detection [START_REF] Fischer | A 90-nm variable frequency clock system for a power-managed itanium architecture processor[END_REF] have been proposed. An example droop detector is proposed in [START_REF] Bowman | Dynamic variation monitor for measuring the impact of voltage droops on microprocessor clock frequency[END_REF]. It is based on mixed gate-interconnect delay line monitoring. The solution in [START_REF] Keith A Bowman | A 22 nm all-digital dynamically adaptive clock distribution for supply voltage droop tolerance[END_REF] uses the fact that a droop delays not only the critical path, but also the clock launch and capture paths. They thus concentrate on the potentially hazardous reverse effect of decreased frequency after the droop is over, and mask the clock signal until the droop is over.

Direct implementation with phase shifts. Figure 3.30 shows the principle design of a phase shift module (ϕ) acting as a frequency adaptation module and a droop detector. The module ϕ receives a, typically, stable clock Clk in and produces the shifted clock signal Clk out . The phase shift between Clk out and Clk in is incremented by a fixed amount if the enable signal is active at an active clock edge of Clk in . The droop detector (DD) drives the enable signal, repeatedly shifting the clock signal and thus slowing down its frequency during a droop. The design suffers from potential metastable-upsets, however: the enable signal provided by the droop detector is not aligned to the clock input signal a priori. Thus phase shifts may be triggered exactly when an active input clock edge occurs, leading to glitches in the output clock signal.

Synchronizing the enable signal. Metastability-containing design. In [START_REF] Függer | Fast all-digital clock frequency adaptation circuit for voltage droop tolerance[END_REF] we proposed and proved correct a different solution that does not have the problem of coupling latency and lower probability of metastable upsets. The design is shown in Figure 3.33 Again, the DD senses the occurrence of a droop and sets its enable output to active during a droop. In fact the enable signal is split into two signals, that we will discuss later and that can be viewed as duplicates for the moment. The enable then travels from the right to the left through a pipeline of delay elements (DE). These apply a phase shift between signals C I and C O by switching their internal delay from short to long. From the other direction, left to right, the clock signal is fed into the pipeline of DEs with a respective phase shift from τ i,k to τ i,k+1 applied at each DE. Each delay element also hands over the enable signal to the left, finally arriving at ϕ. This makes sure that the phase shifts are also applied to following clock transitions; preventing them from being too close to the initially delayed/shifted clock transition. 3.34 shows the timeline from the occurrence of a droop to the application of a phase shift. If the DD issues a clear active enable, the shift is immediately applied at the last delay element. Potentially the DD may be about to change its enable output during a clock transition happening at the last delay element DE n. In this case the enable output signal(s) of DE n may become metastable, and a priori, this may lead to a glitch at the clock output C O . In [START_REF] Függer | Fast all-digital clock frequency adaptation circuit for voltage droop tolerance[END_REF] we proposed a design based on a metastability-containing implementation of DE that effectively computes with such signals and prevents a glitch form occurring. The latter is possible since the output space of a phase shift is continuous. But, since we cannot prevent enable signals from becoming metastable, we split them into two signals with (monotonicity) guarantees between them when becoming metastable. The interested reader is referred to the article [START_REF] Függer | Fast all-digital clock frequency adaptation circuit for voltage droop tolerance[END_REF] for the circuitry and its analysis. Differently put, the timeline in Figure 3.34 can be interpreted as as replacing the synchronizing element by an element that computes/acts (in this case applies a phase shift) and synchronizes at the same time.

Clk in τ ↑/↓ i ϕ phase shift module DE 1 DE 2 . . . DE n DD droop detector V DD CO CI CO ĒI ĒF O ĒF I ĒS O ĒS I τ ↑/↓ i,0 CI CO ĒF O ĒF I ĒS O ĒS I τ ↑/↓ i,1 CI CO ĒF O ĒF I ĒS O ĒS I τ ↑/↓ i,2 ĒF O ĒS O Clk out τ ↑/↓ i,n
Besides a correctness and performance analysis, Spice simulation of this design are provided in [START_REF] Függer | Fast all-digital clock frequency adaptation circuit for voltage droop tolerance[END_REF], showing that clock frequencies in the GHz domain are indeed feasible.

Further reading. Dolev et al. [START_REF] Dolev | Fault-tolerant algorithms for tick-generation in asynchronous logic: Robust pulse generation[END_REF] designed and proved correct a distributed clock generation circuit that is probabilistically self-stabilizing, and tolerates less than a third of Byzantine faulty nodes. Two key design constraints were a required low number of interconnect between nodes, and the necessity to deal with metastable upsets. Bund et al. [START_REF] Bund | Pals: Plesiochronous and locally synchronous systems[END_REF] proposed a distributed clock generation circuit that is not necessarily fully connected and that provides gradient clock synchronization guarantees. Key design constraints were again a low number of interconnect, small node circuitry, tighter synchronization bounds than for clock trees, and the correct handling of metastable upsets.

Chapter 4 Dynamic Networks

In previous chapters we assumed that the machine's architecture is static. While this is plausible for standard VLSI designs in silicon, accounting for faults and inherent dynamic configurations of components requires to consider dynamic architectures. The concrete requirements of such systems may vary, depending on whether the machine changes behavior, e.g., due to a radiation fault or a component moving in space. At a certain level of abstraction, however, there is no difference between the two machine models: messages between its components are potentially dropped or corrupted. In this chapter, we study computing in the presence of such dynamic machine models. This chapter discusses results from the following research articles.

• [START_REF] Charron-Bost | Approximate consensus in highly dynamic networks: The role of averaging algorithms[END_REF] Charron-Bost, Függer, Nowak. Approximate consensus in highly dynamic networks:

The role of averaging algorithms. In 42nd International Colloquium on Automata, Languages, and Programming (ICALP), pages 528-539, 2015.

Within dynamic networks that are described by a network model, i.e., a set of communication graphs from which the adversary may freely choose in each round, we characterized solvability of approximate consensus and asymptotic consensus. Surprisingly, there exist simple solutions, namely averaging algorithms, for the solvable cases.

• [START_REF] Charron-Bost | Fast, robust, quantizable approximate consensus[END_REF] Charron-Bost, Függer, Nowak. Fast, robust, quantizable approximate consensus. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP), volume 55, pages 137:1-137:14, 2016.

We show that simple averaging algorithms do not only solve asymptotic and approximate consensus in highly dynamic networks, but can be slightly adapted to yield fast and robust solutions, with several potential applications.

• [START_REF] Függer | On the radius of nonsplit graphs and information dissemination in dynamic networks[END_REF] Függer, Nowak, Winkler. On the Radius of Nonsplit Graphs and Information Dissemination in Dynamic Networks. Discrete Applied Mathematics, 2020.

The dynamic radius of a sequence of communication graphs is related to the speed of information dissemination from a single process within the network. We show that the dynamic radius of a sequence of non-split graphs with n nodes is in O(log log n).

• [119] Függer, Nowak, Schwarz. Tight bounds for asymptotic and approximate consensus. In ACM Symposium on Principles of Distributed Computing (PODC), pages 325-334, New York, NY, USA, 2018. ACM.

We show that the approximate agreement algorithms from [START_REF] Charron-Bost | Fast, robust, quantizable approximate consensus[END_REF] are indeed optimal with respect to time complexity in dynamic networks. Our results also imply a lower bound on time complexity in classical static networks, answering a question by Dolev et al. [START_REF] Dolev | Reaching approximate agreement in the presence of faults[END_REF] on lower bounds for general approximate agreement algorithms. We present new algorithms for asymptotic and approximate consensus with multidimensional input values. Our analysis shows that the algorithms work in dynamic networks and improve the time complexity from the previously fastest approximate consensus algorithm in asynchronous message passing systems with Byzantine faults by Mendes et al. [START_REF] Mendes | Multidimensional agreement in byzantine systems[END_REF].

Models of Dynamic Networks

Traditionally, early work in distributed computing [START_REF] Lynch | Distributed algorithms[END_REF] mapped changes in a distributed machine to nodes or links within an inherently stable fully connected network. However, any such adversarial model can also be viewed as a model of a dynamic network for this particular setting. Drawing the line between distributed algorithms for dynamic networks and for classical static networks thus becomes a matter of taste. Indeed, some of the results that will be discussed in this section for highly dynamic networks will have direct applications to static networks.

Early work that emphasized on the dynamic aspect of networks is by Santoro and Widmayer [START_REF] Santoro | Time is not a healer[END_REF]. They studied agreement problem variants in a network with message faults and where processes communicate and compute in synchronous rounds. Among other results, they show that the classical exact consensus/agreement problem is not solvable in a network of n > 1 nodes, if the adversary is allowed to remove n -1 messages per round. In fact their impossibility proofs only require the adversary to choose up to n -1 omissions from a (different) sender node at each round.

Charron-Bost and Schiper [START_REF] Charron-Bost | The heard-of model: computing in distributed systems with benign faults[END_REF] introduced a unified framework for distributed algorithms that communicate within communication-closed rounds and where messages can only be deleted. Benign adversaries can thus be described as sets of allowed communication schedules, i.e., sequences of communication graphs.

Afek and Gafni [START_REF] Afek | Asynchrony from synchrony[END_REF] studied round-wise operating distributed algorithms with the intention to relate solvability of certain problems in such message passing systems to solvability in shared memory systems. The allowed communication schedules are only restricted round-wise: the adversary may schedule a communication graph if a predicate P holds on the graph. Such message adversaries were termed oblivious in [START_REF] Coulouma | A characterization of oblivious message adversaries for which consensus is solvable[END_REF]. A predicate is called message adversary in this context. Like in [START_REF] Santoro | Time is not a healer[END_REF][START_REF] Charron-Bost | The heard-of model: computing in distributed systems with benign faults[END_REF], communication graphs are not necessarily bidirectional. However, unlike this work, Afek and Gafni consider only anonymous message adversaries, i.e., if P (G) for a graph G than P (G ) for any G with renamed nodes.

Raynal and Stainer [START_REF] Raynal | Synchrony weakened by message adversaries vs asynchrony restricted by failure detectors[END_REF] studied message adversaries in the context of failure-detectors, i.e., oracles that predict properties on communication networks.

Kuhn et al. [START_REF] Kuhn | Distributed computation in dynamic networks[END_REF] studied distributed problems, like counting nodes, and on top of this, distributed function computation, in dynamic networks. By contrast to the work covered in this chapter, the communication graphs are bidirectional, however.

Casteigts et al. [START_REF] Casteigts | Time-varying graphs and dynamic networks[END_REF] systematically studied dynamic network topologies and reductions among certain classes of such networks; formalizing the concept of time varying graphs for distributed systems and providing (simulation) relations between classes of such networks. Like [START_REF] Kuhn | Distributed computation in dynamic networks[END_REF], graphs are bidirectional by definition.

In the particular context of solving exact consensus in dynamic networks, Coulouma et al. [START_REF] Coulouma | A characterization of oblivious message adversaries for which consensus is solvable[END_REF] characterized the oblivious massage adversaries in which exact consensus is solvable. Winkler et al. [START_REF] Winkler | A characterization of consensus solvability for closed message adversaries[END_REF] characterized so called closed1 message adversaries in which exact consensus is solvable, and Nowak et al. [START_REF] Nowak | Topological characterization of consensus under general message adversaries[END_REF] arbitrary message adversaries where this is the case.

A broad overview on computing in dynamic communication networks has been presented by Kuhn and Oshman [START_REF] Kuhn | Dynamic networks: models and algorithms[END_REF].

Network Models

We start with introducing a model along the lines of [START_REF] Charron-Bost | Approximate consensus in highly dynamic networks: The role of averaging algorithms[END_REF]. Consider the set [n] of n ∈ N + processes/nodes all of which operate in synchronous rounds, broadcasting a message in each round to all other processes, receiving messages from a subset of processes that have been sent in this round, and performing a computational step. The messages that are successfully received (and not altered) within this round can be described by a graph, with a link from process i to j, if the message has been received, and no link, otherwise. If not stated otherwise, we assume that messages are never altered. Further, we assume the existence of self-loops, i.e., processes always receive their own messages. Call such a directed graph a communication graph. For a communication graph G, we denote the incoming neighbors of a node i by In i (G) and the outgoing neighbors by Out i (G). Likewise, for a set S of nodes, we set In S (G) = j∈S In j (G); and similarly for Out S (G).

While several notions of stability in dynamic networks exist, e.g., how many edges can be removed in a communication graph from one round to the next, a lower bound on the existence of an edge before it may be deleted, the arguably most dynamic case is the case where the message adversary can freely choose communication graphs from a pre-defined set. Call such a (non-empty) set of graphs with nodes in [n] a network model. A network model thus corresponds to an oblivious message adversary.

A communication sequence G is a countably infinite sequence of communication graphs (G(k)) k≥1 . We say the communication sequence is from network model N if all of the communication sequence's graphs are from N .

We are now in the position to define how a distributed system advances in the presence of a communication sequence. Process i's local state at the beginning round k ≥ 1 is denoted by s i (k -1), and its state at the end of round k is s i (k). Local states are from a potentially infinite set of states. The global state, or configuration, at (the beginning of) round k is the collection of local states at the beginning of round k, one per process.

A distributed algorithm is a state machine that acts on the global state space, with its transition function restricted to locality constraints: it specifies (part of) the initial global state s(0) at the beginning of round 1, as well as a transition function f i that determines for each process i, the next state s i (k) from the states s j (k -1) of all j ∈ In i (k) it has received in round k, i.e., for all rounds k ∈ N + ,

s i (k) = f i ({s j (k -1) | j ∈ In i (k)}) . (4.1)
While f i depends only on the set of received states, any ordering may be encoded within the received states, e.g., by appending process identifiers. Further, while the model assumes that processes broadcast their complete local state in every round (potentially including process identifiers, round number, reception history, etc.), realistic implementations may broadcast only the part of the state that determines the algorithm's behavior. An algorithm that does not make use of identifiers, may simply omit broadcasting these.

Requiring that only part of the initial global state s(0) may be specified by the algorithm, the remaining part will serve as the initially presented input -analogously to the computational model presented in Section 3.3.3 where inputs are initially loaded into the input register and not changed by the environment during computation.

An execution of a distributed algorithm from global initial state s(0) with communication sequence G = G 1 , G 2 , G 3 , . . . is defined as the alternating sequence of global states and communication graphs

s(0), G 1 , s(1), G 2 , s(2), G 3 , . . .
obtained by successive application of the distributed algorithm's transition function, given the communication sequence G.

Non-split and Rooted Graphs

A communication graph is non-split if any two of its nodes have a common incoming neighbor. have common incoming-neighbors {1, 2}, nodes 2 and 3 common incoming-neighbors {1}, and nodes 1 and 3 common incoming-neighbors {1} by presence of the self-loop at 1. The graph in Figure 4.1 (b) is not non-split since nodes 2 and 3 have no common incoming-neighbors. While our treatment of non-split graphs is based on the work on approximate agreement in [START_REF] Charron-Bost | Approximate consensus in highly dynamic networks: The role of averaging algorithms[END_REF], these graphs play an important role for several applications -for example, within the work by Charron-Bost and Schiper [START_REF] Charron-Bost | The heard-of model: computing in distributed systems with benign faults[END_REF] studying such graphs as "no split predicates" and Cao et al. [START_REF] Cao | Reaching a consensus in a dynamically changing environment: A graphical approach[END_REF] as "neighbor-shared graphs".

A communication graph is rooted if there exists a node i (a root) with a path from i to any of the graph's nodes. The root is not necessarily unique, and the set of roots of a communication graph G has been referred to as the root component of G, since the subgraph that consists of all roots is strongly connected [START_REF] Schwarz | Fast consensus under eventually stabilizing message adversaries[END_REF]. The nodes of the root components, the roots, are denoted by R(G). The graph in Figure 4.1 (a) is rooted with root component {1, 2}, and the graph in Figure 4.1 (b) with root component {2}. Like non-split graphs, rooted graphs occur in diverse applications.

Relations between Non-Split and Rooted Graphs

Given a non-split communication graph G, one observes by repeatedly applying the non-split definition that G is also rooted: Lemma 88. Every non-split graph is rooted.

While the existence of a root r is immediate, its eccentricity within G, i.e., the maximum of the minimum path length from r to i, for all i ∈ [n], is not. The radius of a directed graph is the minimum eccentricity over all nodes. As such, it has implications within several distributed applications. Consider, e.g., a communication graph G that resembles a network topology of a distributed system that operates in rounds. Then the radius is a tight lower bound on when everyone has heard from a common process. Repeated application of the non-split definition, with incoming neighbors forming a binary tree yield a radius in O(log n). However, in [START_REF] Függer | On the radius of nonsplit graphs and information dissemination in dynamic networks[END_REF], we have shown that a stronger bound holds for the radius:

Example 89. The radius of the communication graph in

Theorem 90 ( [START_REF] Függer | On the radius of nonsplit graphs and information dissemination in dynamic networks[END_REF]). The radius of a non-split communication graph with n nodes is in O(log log n).

To compare, Figure 4.1 (a) is non-split and has radius 1. Only a constant lower bound of 3 is known from an example non-split graph, leaving a tight upper bound an open problem.

In the previous considerations, we have assumed a single, fixed communication graph G. However, with adapted definitions, the above two results also hold in presence of dynamic communication graphs.

For that purpose let the product communication graph G = G 1 • G 2 of two communication graphs G 1 and G 2 with same set of nodes [n], be the graph with set of nodes [n] and an edge

from i to j in G, if there is a k ∈ [n] such that (i, k) is an edge in G 1 and (k, j) is an edge in G 2 .
One observes, that for a communication sequence G 1 , G 2 , . . . , and a distributed algorithm that relays messages, the processes from which a node j has indirectly received a message at the end of round 2, are exactly those in In j (G 1 • G 2 ). The above graph product thus captures collapsing several rounds into a single macro-round.

Following [START_REF] Függer | On the radius of nonsplit graphs and information dissemination in dynamic networks[END_REF], the dynamic radius of a sequence of communication graphs G 1 , . . . , G , . . . is the smallest ≥ 1, such that G 1 • • • • • G contains a star graph. Again, the dynamic radius is a tight lower bound on when everyone has heard from a common process in the first rounds.

One can then show that Theorem 90 also holds in presence of a dynamic network: [START_REF] Függer | On the radius of nonsplit graphs and information dissemination in dynamic networks[END_REF]). The dynamic radius of a sequence of non-split communication graph with n nodes is in O(log log n).

Theorem 91 ([
This shows that multiplying O(log log n) non-split communication graphs with n nodes, one obtains a graph that contains a star graph. The property is trivially fulfilled for the non-split graph in Figure 4.1 (a), since it contains a star graph.

In fact, a similar transition from rooted to non-split by multiplying sufficiently many graphs exists. In [START_REF] Charron-Bost | Approximate consensus in highly dynamic networks: The role of averaging algorithms[END_REF] we have shown:

Theorem 92 ( [START_REF] Charron-Bost | Approximate consensus in highly dynamic networks: The role of averaging algorithms[END_REF]). The product of n -1 rooted communication graphs with n nodes is non-split.

Example 93. Let G be the rooted graph in Figure 4.1 (b) with n = 3 nodes. While G is not non-split, G n-1 = G 2 is shown in Figure 4.2, and easily verified to be non-split.

Theorem 92 has immediate consequences on the time complexity of distributed algorithms to reach agreement among processes; as we will discuss in Section 4.4. Together with Theorem 91, we also obtain: Theorem 94 ( [START_REF] Függer | On the radius of nonsplit graphs and information dissemination in dynamic networks[END_REF]). The product of O(n log log n) rooted communication graphs with n nodes contains a star graph.

Averaging Algorithms

A distributed algorithm updates its state based on all received states. In previous work, so called averaging algorithms have received particular attention for solving agreement related problems in dynamic networks; see, e.g., [START_REF] Cao | Reaching a consensus in a dynamically changing environment: A graphical approach[END_REF][START_REF] Moreau | Stability of multiagent systems with time-dependent communication links[END_REF][START_REF] Vincent D Blondel | Convergence in multiagent coordination, consensus, and flocking[END_REF][START_REF] Chazelle | The total s-energy of a multiagent system[END_REF][START_REF] Chazelle | Natural algorithms and influence systems[END_REF] Following [START_REF] Charron-Bost | Approximate consensus in highly dynamic networks: The role of averaging algorithms[END_REF], we define an averaging algorithm as one with an update rule (4.1) of the form,

s i (k) ∈ [0, 1] s i (k) = j∈Ini(k) w ji (k)s j (k -1) , (4.2)
where weights w ji (k) ∈ R + , and j∈Ini(k) w ji (k) = 1. While the above definition restricts the output value s i of every process i to be from [0, 1], we will also speak of averaging algorithms if s i is from R, and more generally, from R d with dimension d ≥ 1. For the moment, we assume bounded scalar values in [0, 1], however.

Averaging algorithms differ in how weights are locally computed from received states. Three natural averaging algorithm classes are:

• The equal neighbor averaging algorithm for which

w ji (k) = 1 | In i (k)| .
• The mean-value averaging algorithm with

w ji (k) = 1 |{s j (k -1) | j ∈ In i (k)}| .
• A fixed weight averaging algorithm for the network model N . Let d i be the maximum indegree of node i over all graphs in N , and let di ≥ d i . Then,

w ji (k) = 1 di if i = j 1 -j∈Ini(k), j =i w ji (k) otherwise .
• The midpoint algorithm has w ij (k) = 1 2 for j ∈ {m, M }, where m, M are such that s m (k -1) and s M (k -1) span the interval of the values received by process i in round k. The name is due to the fact that a process sets its new value to the midpoint of the values it receives. The midpoint algorithm lies at the heart of a distributed clock synchronization algorithm proposed by Welch and Lynch [START_REF] Lundelius | A new fault-tolerant algorithm for clock synchronization[END_REF].

• The jumping algorithm analyzed in Charron Bost et al. [START_REF] Charron-Bost | Fast, robust, quantizable approximate consensus[END_REF] is specified only for n = 2 processes. In case a process i receives a value, it sets its own weight to w ii (k) = 1 3 and the other process' weight to 2 3 .

Parameters and safety of averaging algorithms. In [START_REF] Charron-Bost | Approximate consensus in highly dynamic networks: The role of averaging algorithms[END_REF], we classified averaging algorithms with respect to two parameters that we have shown to impact time complexity in agreement problems. Towards that goal, we introduce some definitions. For a set A ⊆ R d , with dimension d ≥ 1, its diameter is given by

diam(A) = sup x,y∈A ||x -y|| . (4.3)
Note that if d = 1 and the set has finite cardinality, then diam(A) = max Amin A.

For a process i ∈ [n] and round k ∈ N + , the set of received values is denoted by

V i (k -1) = {s j (k -1) | j ∈ In i (k)}
and its minimum and maximum value by

m i (k -1) = min V i (k -1) M i (k -1) = max V i (k -1) .
The diameter of all output values in round k is denoted by

δ(k -1) = diam ({s i (k -1) | i ∈ [n]}) .
We say an averaging algorithm has parameter α, for α > 0, in a network model N , if for all nodes i, j ∈ [n] and rounds k ∈ N + in all its executions in N ,

w ji (k) ≥ α .
We omit the reference to the network model if the statement holds for all network models. The condition is identical to Assumption 1 in Blondel et al. [START_REF] Vincent D Blondel | Convergence in multiagent coordination, consensus, and flocking[END_REF]. Note that an averaging algorithm with a parameter α > 0 never drops received messages, i.e., does not set weights of received values to 0.

Example 95 (Parameters of some averaging algorithms). The equal neighbor averaging algorithm is an averaging algorithm with parameter 1/n, the mean-value averaging algorithm with parameter 1/n, and the fixed weight averaging algorithm with parameter min i∈[n] {1/ di , 1-j∈Ini(k), j =i w ji (k)}. The midpoint algorithm does not have a parameter greater than 0.2 Further, an averaging algorithm is σ-safe, for σ ∈ (0, 1 2 ], in network model N , if for all nodes i ∈ [n] and rounds k ∈ N + in all its executions in N ,

σM i (k -1) + (1 -σ)m i (k -1) ≤ s i (k) ≤ (1 -σ)M i (k -1) + σm i (k -1) ,
i.e., if process i's new value lies within relative distance σ to the interval boundaries m i (k -1) and M i (k -1) of the received values. Again, we omit the reference to the network model if the statement holds for all network models.

The following relation holds between averaging algorithms with parameter and safety.

Lemma 96 ([117]). If an averaging algorithm has parameter α > 0 in network model N , then it is αsaf e in network model N .

Proof. Consider an averaging algorithm that has parameter α > 0 in network model N For k ∈ N + , and with ĵ ∈ [n] being a process whose s j (k -1) is minimal among those received by process i, it is

s i (k) = j∈Ini(k) w ji (k)s j (k -1) = j∈Ini(k)\{ ĵ} w ji (k)s j (k -1) + w ĵi m i (k -1) ≤ j∈Ini(k)\{ ĵ} w ji (k)M i (k -1) + w ĵi m i (k -1) ≤ (1 -α)M i (k -1) + αm i (k -1) .
The lower bound follows by analogous arguments.

Example 97 (Safety of some averaging algorithms). From Lemma 96, one immediately obtains:

The equal neighbor averaging algorithm, the mean-value averaging algorithm, and the fixed weight averaging algorithm are α-safe, where α is their respective parameter. Further, by definition, the midpoint algorithm is 1 2 -safe.

Consensus Problems

A typical coordination task in a distributed system is to achieve (approximate) agreement on (part of) the processes' states. We call these consensus problems. The precise definition of when two processes are considered to agree on a state, among other problem parameters, as well as the distributed computing model, lead to either solvable or unsolvable combinations -the former with different degrees of algorithmic performance. In this chapter we will focus on the consensus problems that we studied in [START_REF] Charron-Bost | Approximate consensus in highly dynamic networks: The role of averaging algorithms[END_REF][START_REF] Charron-Bost | Fast, robust, quantizable approximate consensus[END_REF][START_REF] Függer | Tight bounds for asymptotic and approximate consensus[END_REF][START_REF] Függer | Fast multidimensional asymptotic and approximate consensus[END_REF].

As a distributed computing model we will consider highly dynamic distributed systems specified via network models. Further, we assume that the state space of each process i ∈ [n] is of the form

s i = (x i , dec i , loc i ) with x i ∈ [0, 1] , dec i ∈ {⊥} ∪ [0, 1] ,
and

loc i ∈ L ,
where L is the potentially infinite local state space of a process. While loc i serves as an internal, algorithm specific, state, x i and dec i serve as inputs and outputs to the distributed algorithm solving a consensus problem.

• Inputs. We assume that the input is one value in [0, 1] per process, initially presented to the corresponding process. In our model x i (0) is the input for process i ∈ [n]. Further, initially, dec i (0) = ⊥.

• Outputs. Process outputs for rounds k ∈ N + are x i (k) and dec i (k). We say process i has (output) value, respectively, outputs x i (t) in round t. A process may also set dec i (k) to x i (k) -but only once -after which the variable dec i does not change value anymore. If so, we say process i decides value x i (k) in round k.

Recall the definition of an averaging algorithm from Section 4.3. By slight abuse of terminology, we will call algorithms with states as defined above and that repeatedly compute weighted averages of x i instead of s i also averaging algorithms. Clearly, though an equal neighbor averaging algorithm may vary in this context depending on whether on how it sets dec i for each process i.

We are now in the position to define the different variants of consensus problems discussed in this chapter.

Exact Consensus

An algorithm achieves (exact, terminating) consensus with the communication sequence G = (G(k)) k≥1 if in each execution of the algorithm from a global initial state, that represents valid inputs to consensus problems, with communication sequence G:

• Termination. All processes eventually decide.

• Agreement. If two processes i and j decide on values v i and v j , then v i = v j .

• Validity. Any value decided by a process is among the initial values.

Further, we say an algorithm solves exact consensus in network model N if for all communication sequences with graphs in N , it achieves consensus with the communication sequence. Exact consensus is solvable in network model N if there exists an algorithm that solves exact consensus in N .

In distributed computing, the exact consensus problem is often simply referred to as the consensus problem; see [START_REF] Lynch | Distributed algorithms[END_REF] for an overview. Typically, though, termination, and depending on the fault model, also Agreement and Validity, are required to hold only for correct processes. Note that in our setting of a dynamic network, the notion of a correct process does not exist, and we require the properties to hold for all processes. Nonetheless, relations to solving consensus in classical fault models are possible and are discussed later on. Finally, note that different variants of Validity exist in classical literature [START_REF] Lynch | Distributed algorithms[END_REF].

Approximate Consensus

Achieving exact consensus is a natural subproblem when synchronizing multiple copies of databases, or in general, in the context of applications that require replica determinism as is the case for mission critical distributed embedded systems [START_REF] Kopetz | Real-time systems: design principles for distributed embedded applications[END_REF]: If the state machines at two different processes are in different states, in general, their machines may diverge arbitrarily during the successive rounds. By contrast, this is overly pessimistic for state spaces that contain a certain structure. One example is the state space [0, 1] where nearby states, in terms of a metric on [0, 1], lead to nearby future states in successive rounds. If so, it often suffices to agree on nearby states instead of exactly the same states. In the following we consider the metric space [0, 1] with the distance d(x, y) = |x -y|. We discuss generalizations in Section 4.4.4.

Let ε > 0. We say, an algorithm achieves ε-approximate (terminating) consensus with the communication sequence G = (G(k)) k≥1 if in each execution of the algorithm from a global initial state, that represents valid inputs to consensus problems, with communication sequence G:

• Termination. All processes eventually decide.

• ε-Agreement. If two processes i and j decide on values v i and v j , then |v i -v j | ≤ ε.

• Validity. Any value decided by a process is within the interval of initial values.

Solvability is defined analogously to the exact consensus problem.

Note that Termination is as in the consensus problem. Agreement has been weakened to ε-Agreement, and Validity has been weakened accordingly to allow decisions on values initially not taken by processes. The problem is also referred to as approximate agreement in literature [START_REF] Lynch | Distributed algorithms[END_REF] and has been thoroughly studied in the context of classical fault models like the fully connected communication architecture with up to f < n crashes. For work on approximate agreement; see, e.g., [START_REF] Dolev | Reaching approximate agreement in the presence of faults[END_REF][START_REF] Abraham | Optimal resilience asynchronous approximate agreement[END_REF][START_REF] David | Asymptotically optimal algorithms for approximate agreement[END_REF].

Asymptotic Consensus

For some applications the requirement of a single decision value per process may either be unnatural, simply not be required, or even too little for an application. For example, in controller applications one typically requires that the controller output converges to the desired set point with the error approaching 0 with increasing number of rounds. The same is desirable for optimization problems: ideally we would like to have an algorithm that achieves better and better solutions with increasing runtime.

Asymptotic consensus is a problem that captures these requirements in an application independent way. We say an algorithm achieves asymptotic consensus with the communication sequence G = (G(k)) k≥1 if in each execution of the algorithm from a global initial state, that represents valid inputs to consensus problems, with communication sequence G:

• Convergence. Each sequence of process outputs (x i (k)) k≥1 converges.

• Agreement. If the output sequences of two processes converge, they converge to the same limit.

• Validity. If the output sequence of a process converges, then its limit is in the interval of initial values.

Again, solvability is defined analogously to the exact consensus problem. Note that the above problem does not allow outputs whose distance to each other approaches 0, but who do not converge, but, e.g., oscillate in synchrony.

Asymptotic consensus has received considerable attention from the control community where it is often referred to as consensus. This includes work on asymptotic consensus in dynamic communication architectures with respect to averaging algorithms [START_REF] Cao | Reaching a consensus in a dynamically changing environment: A graphical approach[END_REF][START_REF] Cao | Reaching a consensus in a dynamically changing environment: convergence rates, measurement delays, and asynchronous events[END_REF], in dynamic bidirectional communication networks [START_REF] Moreau | Stability of multiagent systems with time-dependent communication links[END_REF], dynamic strongly connected communication networks [START_REF] Vincent D Blondel | Convergence in multiagent coordination, consensus, and flocking[END_REF], and work on non-averaging algorithms in static networks [START_REF] Yu | Second-order consensus for multiagent systems with directed topologies and nonlinear dynamics[END_REF], among others. For example, Blondel and Olshevsky [START_REF] Vincent | How to decide consensus? a combinatorial necessary and sufficient condition and a proof that consensus is decidable but np-hard[END_REF] study sets of matrices, whose products when multiplied with the vector of initial values, converge to a vector with common entries. These so called consensus sets of matrices directly correspond to network models of directed graphs within which averaging algorithms are executed (that determine the weights of the matrices). While the result can be seen as a specialization of the question of which network models allow to solve asymptotic consensus in case only averaging algorithms are permitted, the result is incomparable to our results from [START_REF] Charron-Bost | Approximate consensus in highly dynamic networks: The role of averaging algorithms[END_REF] presented within this chapter, however: all our network models are required to have self-loops, but algorithms are not restricted to averaging algorithms.

Before proceeding to higher dimensional generalizations of the above problems and a discussions about correctness and performance of algorithms, let us observe the behavior of two asymptotic consensus algorithms within example network models. Observe that the midpoint algorithm seems to perform better within its execution as it converges faster within the first shown rounds. While this may a priori be just bad chance for the equal neighbor algorithm since we chose graphs uniformly at random for both executions, we will show during this chapter that better performance bounds can be shown to hold for the midpoint algorithm. Example 99. To address the valid criticism in Example 98 that executions may not be representative, Figure 4.4 on page 83 shows 100 example executions for the same two averaging algorithms as in the example before. Again, communication graphs are chosen uniformly at random from the network model at each round; however the graphs, shown in the figure, differ from Example 98 and have been chosen to be non-split. Further, instead of showing the individual state outputs, we depict the diameter of the set of state outputs at each round. Like in the previous example, the midpoint algorithm seems to perform better. We will later on analyze the performance of both algorithms in non-split network models, and see that this performance ranking coincides with provable bounds.

Consensus Problems in Higher Dimensions

Until now we assumed a one-dimensional metric state space on [0, 1]. Applications like gathering of automated vehicles or drones, control of concentrations to a certain set point, etc., are multidimensional in nature, however. For exact consensus, the generalization is immediate trough reductions in both directions. In the case of asymptotic consensus, for example, for some applications it may be sufficient to converge on each coordinate separately. However, this does not guarantee a natural generalization of the Validity property of asymptotic consensus to stay in the convex hull of the input values. For applications that require this property, a natural generalization of the asymptotic consensus problem is as follows.

Following [START_REF] Függer | Fast multidimensional asymptotic and approximate consensus[END_REF], we define: Let V be some vector space with an inner product •, • from V 2 to R and norm ||x|| =

x, x . As a typical instantiation we will often use V = R d , for d ≥ 1, with inner product (x 1 , . . . , x d ), (y 1 , . . . , y d ) = d i=1 x i y i . We say, an algorithm achieves asymptotic consensus with the communication sequence G = (G(k)) k≥1 if in each execution of the algorithm from a global initial state (that represents valid inputs to consensus problems) with communication sequence G, all of the following hold: Amortized algorithms. Revisiting Theorem 92 on page 77 in terms of the macro-round construction yields a new class of algorithms that are not averaging algorithms: Given any averaging algorithm, let the algorithm compute the average of the received values only every K ∈ N rounds. In all other rounds, one relays the received values to the other processes. We termed these algorithms amortized versions of averaging algorithms [START_REF] Charron-Bost | Fast, robust, quantizable approximate consensus[END_REF].

By an analysis similar to the one in the section before, but considering only macro-rounds, one obtains:

Theorem 110 ( [START_REF] Charron-Bost | Fast, robust, quantizable approximate consensus[END_REF]). In a rooted network model with n processes, every amortized algorithm that is σ-safe, with σ > 0, achieves ε-consensus in

(n -1) log 1 1-σ 1 ε
rounds. In particular, for the amortized midpoint algorithm, with σ = 1 2 , ε-consensus is achieved in

(n -1) log 2 1 ε rounds.
Impossibility in non-rooted network models. To complete the proof for the characterization in Theorem 102 on 84 one finally shows the following result by a partitioning argument:

Theorem 111 ( [START_REF] Charron-Bost | Approximate consensus in highly dynamic networks: The role of averaging algorithms[END_REF]). No algorithm achieves ε-consensus in a network model that includes a non-rooted communication graph.

Asymptotic Consensus

While we concentrated on approximate consensus in the previous sections, several of the results presented there can be transfered to statements about asymptotic consensus. First, observe that asymptotic consensus can be reduced to approximate consensus if precomputable, globally known bounds on the termination time are known. Our solutions fulfill these properties, if the parameter ε and upper bounds on the process number n are globally (and consistently) known. If so, the approximate consensus algorithm may simply be started repeatedly and synchronously at the same round after each termination. The correctness of this approach is seen by viewing each repetition of the approximate consensus algorithm as a macro-round 3 and analyzing contraction of the output values along these macro-rounds.

In fact, however, all presented averaging algorithms, and their amortized variants, can be directly used to solve asymptotic consensus by removing the decision and termination rules. This also removes the requirements of an initial common knowledge of parameters ε and n. Mind though, that amortization may require knowledge of bounds on n if a certain performance is to be guaranteed. We discuss this later on in more detail.

On performance measures. To quantify the speed of an asymptotic averaging algorithm, measures for convergence rates have to replace time complexity measures, though. While the asymptotic consensus problem itself is stated as a limit behavior without any guarantees for finite times, practical solutions will most likely care about the speed of convergence and the guarantees for finite times.

A natural candidate is an upper bound on the round-by-round output contraction ratio ≤ 1, i.e., for all executions and rounds k ∈ N + , δ(k) ≤ • δ(k -1) .

3 Not to confuse with the macro-rounds from the amortized algorithms.

with δ being the diameter of the process output values in round k. 4 We thus readily obtain round-by-round contraction ratio bounds for all our averaging algorithms, and, at the level of macro-rounds, for their amortized versions. A clear downside of this measure is the trivial bound 1 for algorithms that do not contract every round, such as the amortized algorithms at round-scale.

A natural alternative that works around this problem is the (asymptotic) output contraction ratio defined as the supremum over all executions of lim sup

k→∞ k δ(k) . (4.8)
Algorithms with a round-by-round output contraction ratio of will also have an output contraction ratio of at most . Thus, the midpoint averaging algorithm has output contraction ratio 1 2 in network models with non-split communication graphs. Its amortized variant has output contraction ratio n-1 1 2 in network models with rooted communication graphs -making a comparison possible. However, this measure has two other problems as will be outlined in the following: (a) A class of algorithms collapses to 0 that has different convergence behavior.

(b) It ranks algorithms superior to others that intuitively should be ranked less from an application point of view.

To show (a), consider the following algorithm: take one of the averaging algorithms A mentioned before that solves asymptotic consensus, e.g., the midpoint or the equal neighbor averaging algorithm. Assume that we restrict ourselves to inputs from {0, 1} only. Now construct an algorithm B from A that uses A's analysis to derive an upper bound δA (k) on the diameter of output values when executing algorithm A, for every round k ∈ N. This can be achieved for all averaging algorithms presented in this chapter. Algorithm B then runs A and computes δA (k) for the current round k. Denote by s i,A the output of algorithm A run by process i. Analogously, s i,B denotes the output of algorithm B run by process i. In each round k, process i sets

s i,B (k) ← 0 if s i,A (k) + -δA (k), δA (k) ∩ [0, 0.5] = ∅ 1 otherwise .
In fact this algorithm solves asymptotic consensus for binary inputs (and outputs). We will not give a full proof here, but sketch the ideas:

• Convergence of a process' output follows from convergence of the output of algorithm A and the fact that the interval I i (k) = s i,A (k) + -δA (k), δA (k) converges to length 0.

• Validity follows from validity for algorithm A.

• Finally, observe that the process outputs of algorithm A coverages to the same value s * A because of the agreement property of algorithm A. If s * A ≤ 0.5, every process will always output 0 in B since their intervals necessarily contain s * A and thus intersect with [0, 0.5]. Thus agreement is fulfilled for B in this case. Otherwise, every process will eventually output 1, since its interval will have non-zero distance from 0.5; again agreement for B is fulfilled in this case. Thus agreement holds for algorithm B in all cases.

For any such algorithm B, the measure in (4.8) is 0 -irrespective of the underlying algorithm A; showing point (a).

Shortcoming (b) is seen by comparing an algorithm B based on A to the original algorithm A: While, B has measure 0 and A can be shown to have a positive measure, A may have significant advantages as its value may not drastically change in late rounds. Algorithm B can be shown to jump from 0 to 1 or vice versa arbitrarily late -otherwise, exact consensus would be achievable.

Valency and valency contraction ratio. We thus used a measure that is an adaptation of (4.8): the (asymptotic) valency contraction ratio defined as the supremum over all executions of lim sup

k→∞ k ∆(k) , (4.9)
where ∆(k) is a measure on the reachable limits after round k that will be defined in the following.

Let A be an algorithm that solves asymptotic consensus. Recall that a global state of A is a vector of local process states -we will refer to it as a configuration in the following using C(k) rather than s(k) to denote the configuration at the beginning of round k. Configurations occurring in executions with the initial configuration C(0) and a communication sequences in network model N will be called reachable from C(0) by A in N .

Following the valency definition in Fischer et al. [START_REF] Michael | Impossibility of distributed consensus with one faulty process[END_REF] for exact consensus algorithms, and a generalization of it algorithms solving asymptotic consensus we introduced in [START_REF] Schwarz | Fast consensus under eventually stabilizing message adversaries[END_REF], let the valency of a configuration C of A in N , be the set of limits of process outputs in executions by A in N that contain configuration C. This set is denoted by Y * N ,A (C). We are now in the position to define

∆ N ,A (C) = diam Y * N ,A (C) . (4.10)
For simplicity of notation, if we fix an algorithm A, a network model N , and an execution which induces the sequence of configurations C 0 , C 1 , . . . , C k , . . . , we simply write ∆(k) for ∆ N ,A (C k ). Intuitively, ∆ N ,A (C) is a measure on how much the process output is settled in configuration C: the larger ∆, the larger is the amount by which processes may change their outputs later on. As such it has great practical implications. Indeed ∆ can be bounded along an execution for the algorithms that we will present in the following. While (4.9) does not allow to bound ∆ over time, since it is a measure on the asymptotic performance for the reasons given before, we were able to show a shrinking factor of ∆ per fixed number of rounds for the algorithms discussed in [START_REF] Függer | Tight bounds for asymptotic and approximate consensus[END_REF].

Bounds of valency contraction ratio. As mentioned before, the averaging algorithms and their amortized versions can be used to solve asymptotic consensus after removing the decision and termination rules.

From Theorem 103 and the observation that the valency Y * N ,A (C) of a configuration C that occurs in the k th round of an execution of an averaging algorithm is always a subset of the convex hull of the process outputs of round k -and thus ∆(k) ≤ δ(k) -we obtain: Theorem 112. In a non-split network model of n processes, every averaging algorithm that is σ-safe, with σ > 0, achieves asymptotic consensus. For round k ∈ N + , it is

∆(k) ≤ δ(k) ≤ (1 -σ) k • δ(0) ,
and it has a valency contraction ratio of at most

1 -σ .
In particular, for the midpoint algorithm, ∆(k) ≤ 1 2 k • δ(0) and it has a valency contraction ratio of at most 1 2 .

Likewise, in a rooted network model, an analogon to Theorem 110 on page 87 can be shown:

Theorem 113.
In a rooted network model with n processes, every amortized averaging algorithm that is σ-safe, with σ > 0, achieves asymptotic consensus. For round k ∈ N + , it is

∆(k) ≤ δ(k) ≤ (1 -σ) k n-1 • δ(0) ,
and it has a valency contraction ratio of at most

n-1 √ 1 -σ .
In particular, for the midpoint algorithm, ∆(k) ≤ 1 2 k n-1

• δ(0) and it has a valency contraction ratio of at most n-1 1 2 .

Robustness to Limitations in Implementations

The averaging algorithms and their amortized variants have been analyzed with challenging communication networks in mind, but without considering limitations a practical implementation in software or hardware would have to face. In particular such limitations are:

1. Stored and transmitted values are currently assumed to be from [0, 1]. A real-world solution clearly has to deal with finite density of memory and thus quantized values.

2. While the fact that the exact number of processes n or an upper bond is known in advance, this may result in overly pessimistic parametrization, e.g., for building macro-rounds, during most of the rounds. Further, n may unpredictably change in several application.

Quantization. Addressing the first point, we studied Q-quantized versions of (amortized) averaging algorithms, with Q ∈ N + in [START_REF] Charron-Bost | Fast, robust, quantizable approximate consensus[END_REF]. For such an algorithm, after a macro-round, we set

s i (k) = [s i (k)] Q , (4.11)
where s i is computed according to (4.2) and [•] Q denotes rounding up (or rounding down; but doing this consistently) to the next multiple of 1/Q. We showed that quantization does not greatly influence the algorithm's time complexity in solving ε-consensus: Theorem 114 ( [START_REF] Charron-Bost | Fast, robust, quantizable approximate consensus[END_REF]). In a network model with only rooted graphs, the amortized midpoint algorithm achieves:

• 1/Q-consensus after (n -1) ( log 2 (Q -2) + 2 ) (4.12)
rounds.

• ε-consensus, with ε > 2/Q, after

(n -1) log 2 Q -2 εQ -2 + 1 (4.13)
rounds.

We cannot expect smaller ε than 1/Q with the property that a quantized version solves εconsensus. If so, the same algorithm would also solve exact consensus; a contradiction to unsolvability of exact consensus in arbitrary rooted network models [START_REF] Santoro | Time is not a healer[END_REF].

Underestimating the number of processes. Underestimating the process number n leads to the loss of the guarantee that macro-rounds are non-split. However, we showed that the time complexity gracefully degrades with how much this estimate is off: Theorem 115 ( [START_REF] Charron-Bost | Fast, robust, quantizable approximate consensus[END_REF]). Given an amortized σ-safe algorithm with estimate n as the number of processes. In a system with n processes, the algorithm achieves ε-consensus in

O Lσ -L log 1 ε (4.14)
macro-rounds, where L = n-1 n-1 .

A similar statement holds for a scenario where n is a correct estimate of n, but rooted graphs are only guaranteed to occur with some frequency.

Multidimensional Consensus

Several of the discussed averaging algorithms and their amortized versions directly carry over to solve multidimensional approximate and asymptotic consensus. An example that falls into this class is the equal neighbor algorithm. Unfortunately, the midpoint algorithm that outperforms the equal neighbor algorithm for both problems is not even well-defined for dimensions d > 1: the notion of a minimum and a maximum of a finite subset of R d is not defined.

Generalizing the Midpoint Algorithm

A first natural generalization of averaging algorithms, and thus also the midpoint algorithm, is to apply the averaging rules coordinate-wise. For dimension d = 2, one can show that this is indeed a valid approach for the midpoint algorithm. However, for dimensions d ≥ 3, the updated value may lie outside of the convex hull of received values. The algorithm thus violates the validity condition of approximate and asymptotic consensus. 5 The following example shows a problematic scenario.

Example 116 (Midpoint algorithm applied component-wise). Consider the case of a 3-dimensional input and output space and three nodes with initial values (1, 0, 0), (0, 1, 0), and (0, 0, 1). The plane spanned by the three points is x + y + z = 1. The component-wise midpoint of the three points is M = 1 2 • (1, 1, 1), which is seen not to fulfill the plane equation. See below for a visualization.

x y z M

In [START_REF] Charron-Bost | Multidimensional asymptotic consensus in dynamic networks[END_REF] and [START_REF] Függer | Fast multidimensional asymptotic and approximate consensus[END_REF] we proposed different generalizations of the midpoint algorithm:

• Centroid. A natural algorithm is to update one's value to the centroid of the polyhedron that is the hull of all received values.

• MidExtremes. Choose two received values a, b ∈ R d that realize the diameter of the received values. The new value is the midpoint on the line ab. Formally, for a node i ∈ [n] and round

k ∈ N + , a, b ← argmax u,v∈Ini(k) ||x u (k -1) -x v (k -1)|| x i (k) ← a + b 2 .
• ApproachExtreme. Choose a received value a ∈ R d that has maximum distance to one's own value y. The new value is the midpoint on the line ay. Formally, for a node i ∈ [n] and round

k ∈ N + , a ← argmax u∈Ini(k) ||x u (k -1) -x i (k -1)|| x i (k) ← a + x i (k -1) 2 .
While technically this is not generalizing the midpoint algorithm in the sense that it is equivalent to it in dimension 1, it relies on a similar idea.

Terminating variants of these algorithms for approximate agreement and amortized versions for rooted network models are defined analogously to the midpoint algorithm in dimension 1. Figure 4.6 shows outputs during an execution prefix of the MidExtremes algorithm in the same setting (with respect to initial values and network model) as Figure 4.5 on page 91 for the equal neighbor algorithm. At the first sight, both seem to perform similarly. We will discuss the performance of the three proposed algorithms in the following though, showing that they have output contraction ratios independent of the number of nodes n in non-split network models; which is not the case for the equal neighbor algorithm. Coordinate system. Before discussing contraction ratios, let us take a look at coordinate systems. When considering higher-dimensional input and output spaces, coordinate systems relative to which the node's values are determined, play a role.

While a designed cluster running distributed optimization and repeatedly calling an approximate consensus algorithm may very well resort to an a priori determined common coordinate system, a swarm of biological nodes may not. Likewise, moving autonomous vehicles may potentially not easily agree or have access to such a common coordinate system. Rather, it may be more practical to let each node have its own local coordinate systems within which it determines the positions of neighboring nodes.

Another property of algorithms is if process outputs depend on the initially chosen global or local coordinate systems. For example, outputs may change in coordinate-wise algorithms when the coordinate system is rotated. By contrast, other algorithms may guarantee that the outcomes are invariant under several transformations of the coordinate system like rotation and translation.

One observes that the Centroid algorithm, the MidExtremes algorithm, and the ApproachExtreme algorithm require only local coordinate systems and are invariant under rotation and translation.

Performance bounds. By geometric considerations of process outputs that stem from executions in non-split networks, we showed the following results.

In [START_REF] Charron-Bost | Multidimensional asymptotic consensus in dynamic networks[END_REF] we analyzed the performance of the Centroid algorithm in non-split network models. The result relies on a reshaping technique of the convex hull of received process values. The reshaped convex hull is shown to not change an a priori fixed coordinate of the Centroid. for all rounds k ≥ 1. In the particular case of d = 1, the algorithm is equivalent to the midpoint algorithm and achieves c(k) ≤ 1/2. By previously discussed techniques, bounds for rooted network models are also obtained for the Centroid and the amortized Centroid algorithm, as well as for their quantized variants.

In [START_REF] Függer | Fast multidimensional asymptotic and approximate consensus[END_REF] we analyzed the two other previously discussed algorithms that rely on extreme values. For the MidExtremes algorithm in non-split networks we obtained: There may, however, be plausible reasons to resort to the ApproachExtremes algorithm if one has the choice in designed systems. Besides benefits in computational complexity, it may simply be impossible or hard to estimate distances between all "visible", i.e., received, values, while it may be plausible to measure distances between oneself and remote nodes. This is particularly the case if values are not transmitted but reception simply means seeing another node and estimating its position with respect to oneself. For some naturally occurring biological systems like a flock of birds, this algorithm may also be more plausible to be the case.

Comparison of performance. Table 4.1 on page 95 summarizes the performance of our three algorithms [START_REF] Charron-Bost | Multidimensional asymptotic consensus in dynamic networks[END_REF][START_REF] Függer | Fast multidimensional asymptotic and approximate consensus[END_REF] and compares it to two previously existing algorithms for multidimensional approximate/asymptotic consensus: the Mendes-Herlihy (MH) and the Vaidya-Garg (VG) algorithms proposed in [START_REF] Mendes | Multidimensional agreement in byzantine systems[END_REF]. For the purpose of comparison with algorithms that do not necessarily contract outputs every round, we resort to output contraction ratios rather than the round-byround output contraction ratio. However, for all except MH, the given performance measure is also a valid bound on the round-by-round contraction. The table also includes local computational complexity. One observes that the VG algorithm's performance depends on the number of nodes n, while the other algorithm's performance does not. A dependency on the dimension d is observed for MH and Centroid. Notably, the MidExtremes and ApproachExtreme algorithm's performance depends on neither.

Implications on Algorithms for Static Networks

The three presented algorithms are correct for non-split network models, and thus for rooted network models, by previously discussed techniques. Faster, amortized versions for rooted network models are obtained analogously to previously discussed algorithms. Further, the algorithms may as well be used in classical, static systems with failures.

One such classical network is a fully connected network with asynchronous message passing and up to f Byzantine nodes. For example, the VG and MH algorithms have been designed for this setting [START_REF] Mendes | Multidimensional agreement in byzantine systems[END_REF], given that n > (d + 2)f . For d = 1 this gives the requirement of n > 3f shown by Fischer et al. [START_REF] Michael | Easy impossibility proofs for distributed consensus problems[END_REF] to be necessary to solve approximate consensus. While Mendes et al. [START_REF] Mendes | Multidimensional agreement in byzantine systems[END_REF] focused on approximate consensus, similar considerations as discussed in the following hold for asymptotic consensus. Processes proceed in asynchronous rounds by waiting for nf messages from the current round before proceeding to the next round; a common technique in designing algorithms for asynchronous systems. The idea by Mendes et al. [START_REF] Mendes | Multidimensional agreement in byzantine systems[END_REF] was to use a safe area calculation in each round. They compute a subspace from received values that lies within the convex hull of values received from correct nodes, and that is shown to pairwise intersect if computed by correct nodes.

Plugging in our algorithms instead of the VG or MH approximate consensus algorithms, but using the same safe area calculation, we are able to achieve ε-consensus within O log ∆ ε rounds, where ∆ is the initial diameter of correct node values [START_REF] Függer | Fast multidimensional asymptotic and approximate consensus[END_REF]. By contrast, the MH algorithm, e.g., has a worst-case round complexity of Ω d log d∆ ε that depends on the dimension d.

Lower Bounds on Valency Contraction Ratios and Time Complexity

The previous sections discussed several algorithms solving asymptotic consensus and upper bounds on their output contraction ratios within several network models. A natural question is if these are optimal, i.e., if no algorithm can do better. This would be particularly encouraging since the proposed algorithms are simple and do not require, or require only little, state to be stored besides the current output value. For comparison, in general, an algorithm can be full-information, i.e., compute upon and broadcast all its history in each round. For example, processes may use higher order filters that overshoot and set their outputs outside the convex hull of received values. In [START_REF] Függer | Tight bounds for asymptotic and approximate consensus[END_REF] we addressed this question of lower bounds for general algorithms with the results summarized in the following.

Related work. Only a small body of literature addressed lower bounds of valency/output contraction ratios in dynamic networks. Cao et al. [START_REF] Cao | A lower bound on convergence of a distributed network consensus algorithm[END_REF] showed lower bounds on so called scrambling constants of stochastic matrices which are weighted versions of the adjacency matrices of the communication graphs. However, such bounds on scrambling constants do not directly imply bounds on valency/output contraction ratios.

By contrast, lower bounds for static classical settings have received attention in distributed computing. For example, Dolev et al. [START_REF] Dolev | Reaching approximate agreement in the presence of faults[END_REF] posed the question of optimal contraction ratios in fully-connected asynchronous6 message passing systems with f Byzantine failures. Abraham et al. [START_REF] Abraham | Optimal resilience asynchronous approximate agreement[END_REF] improved on the algorithm in terms of required resilience. Dolev et al. [START_REF] Dolev | Reaching approximate agreement in the presence of faults[END_REF] proved a lower bound on the round-by-round valency contraction ratio for a class of algorithms within this setting. Fekete [START_REF] David | Asymptotically optimal algorithms for approximate agreement[END_REF][START_REF] Fekete | Asynchronous approximate agreement[END_REF] proved asymptoticly tight valency contraction ratios along execution prefixes for both the synchronous case (including crashes and Byzantine faults) and the asynchronous case (crashes with n > 2f ).

Related is also the work on lower bounds of time complexity of approximate consensus. For dynamic networks, Hoest and Shavit [START_REF] Hoest | Toward a topological characterization of asynchronous complexity[END_REF] proved lower bounds on the time complexity of approximate consensus algorithms in the non-uniform iterated immediate snapshot (NIIS) model; a shared memory communication model which they introduced in this work.

Valency and Output Contraction Ratios

Recall that for a configuration C that appears in an execution of an algorithm solving exact, approximate, or asymptotic consensus, we write δ(C) for diam(x), where x is the vector of process outputs. For averaging algorithms we showed [START_REF] Függer | Tight bounds for asymptotic and approximate consensus[END_REF] that upper bounds on output contraction ratios lead to upper bounds on valency contraction ratios.

Lemma 120. Let C be a configuration of averaging algorithm A that solves asymptotic consensus in network model N . Then

∆ N ,A (C) ≤ δ(C) .
In particular, for an averaging algorithm that guarantees contraction of output values by a factor c < 1 every k ∈ N + rounds, the valency contraction ratio is at most k √ c.

Valency Contraction Ratios in Dynamic Networks

In [START_REF] Függer | Tight bounds for asymptotic and approximate consensus[END_REF], we established (asymptotically) tight lower bounds for several network models, showing (asymptotic) optimality of some of the previously discussed asymptotic consensus algorithms. Key to showing optimality is Lemma 120 that is used to transfer results about output contraction to upper bounds on valency contraction ratios. While all lower bounds hold for arbitrary dimensions, tightness was only shown for dimension 1. The question about asymptotically tight valency contraction ratios for higher dimensions thus remains an interesting open problem to date.

Two nodes. We start with the simplest of all network models in which exact consensus is not solvable, but in which asymptotic consensus is solvable. The graphs of this rooted network model for n = 2 nodes are shown in Figure 4.7. From [START_REF] Függer | Tight bounds for asymptotic and approximate consensus[END_REF].

H 0 1 2 H 1 1 2 H 2 1 2
For this network model, we showed a lower bound of 1/3: models is asymptotically optimal. In particular, we showed this bound for a network model that comprises the following graphs Ψ 1 to Ψ 3 : For i ∈ [3] we construct communication graph Ψ i by

• nodes 4 to n forming a path with edges from j ∈ {4, . . . , n -1} to j + 1,

• nodes [START_REF] Manohar | Asynchronous signalling processes[END_REF] \ {i} having n as their in-neighbor and node 4 as their out-neighbor, and

• node i having node 4 as its out-neighbor.

The graphs for n = 6 are shown in Figure 4.9. We then proved that:

Theorem 123 ( [START_REF] Függer | Tight bounds for asymptotic and approximate consensus[END_REF]). The contraction ratio of any asymptotic consensus algorithm in an oblivious message adversary that includes the graphs Ψ 1 , Ψ 2 , and Ψ 3 is greater or equal to n-2 1/2.

Network models with α-diameter. An interesting approach of a characterization of network models in which exact consensus is solvable was presented by Coulouma et al. [START_REF] Coulouma | A characterization of oblivious message adversaries for which consensus is solvable[END_REF]. At its heart is the α-relation, defined as follows.

Definition 124 ([126]). Let N be a network model. Let G, H, K ∈ N .

Gα K H :⇔ In R(K) (G) = In R(K) (H) .
Further, Gα N H is the smallest relation for which

Gα K H :⇐ ∃K ∈ N : In R(K) (G) = In R(K) (H) ,
and that is closed transitively.

Based on this definition, we introduced the α-diameter of a network model N in [START_REF] Függer | Tight bounds for asymptotic and approximate consensus[END_REF]: ]). Let N be a network model. We say that N is α N -connected if it has a single α * N -equivalence class. Otherwise, it is α N -disconnected. Let N be a network model that is α N -connected. The α N -diameter of N is the smallest D ≥ 1 such that for all G, H ∈ N there exist communication graphs H 0 , . . . , H q ∈ G and K 1 , . . . , K q ∈ G with q ≤ D such that G = H 0 , H = H q , and H r-1 α Kr H r for all r ∈ [q]. With this definition in place, we were able to prove that even if a network model does not fall into the classes previously discussed, its α-diameter provides a lower bound on the valency contraction ratio: Theorem 126 ( [START_REF] Függer | Tight bounds for asymptotic and approximate consensus[END_REF]). Let N be a network model for which exact consensus is not solvable. If N is α N -connected, then the valency contraction ratio of any asymptotic consensus algorithm in N is at least 1/(D + 1) where D is the α N -diameter of N .

Definition 125 ([ 119
We discuss an application of this bound in the next section.

Valency Contraction Ratios in Static Networks with Failures

A classically considered static network is the fully connected network with processes communication by asynchronous message-passing. Given that there are n ∈ N + processes, we allow for up to f < n/2 crashes.

A common technique to design algorithms for such systems is to construct communicationclosed rounds [START_REF] Lynch | Distributed algorithms[END_REF]: each process broadcasts its current round's message that contains its current state, and waits until it has received at least nf messages corresponding to this round. Upon doing so, it updates its state based on the received states and proceeds to the next round. Old messages from previous rounds are simply dropped, making the round communication-closed.

Each such round may be viewed as a communication graph with nf in-neighbors at each node corresponding to a correct process. Establishing a bound on the α-diameter in such systems, and applying Theorem 126 yields that no algorithm operating in asynchronous rounds can achieve a valency contraction ratio less than 1 n/f +1 [START_REF] Függer | Tight bounds for asymptotic and approximate consensus[END_REF]. The bound asymptotically matches the valency contraction ratio established by an algorithm by Fekete [START_REF] Fekete | Asynchronous approximate agreement[END_REF] for system with f < n/2 crashes. Further, the bound asymptotically matches the valency contraction ratio for asynchronous algorithms for systems of size n > 5f with up to f Byzantine failures by Dolev et al. [START_REF] Dolev | Reaching approximate agreement in the presence of faults[END_REF], for which the same lower bound of 1 n/f +1 can be shown to hold with the discussed technique.

Implications for Approximate Consensus

All presented lower bounds have been derived for asymptotic consensus. We showed in [START_REF] Függer | Tight bounds for asymptotic and approximate consensus[END_REF] that lower bounds on the time complexity of approximate consensus algorithms can be deduced from these bounds for the same network models. The proof relies on a reduction of asymptotic consensus to approximate consensus.

Averaging Algorithms in Physical Systems

We finish our discussion of asymptotic consensus algorithms with an application. The simplicity of the averaging algorithms that solve asymptotic consensus may suggest their use in sensor nodes, mobile robots, or nodes in a cluster with potentially faulty links and online reconfiguration. The following example shows that they may be also used to analyze existing physical systems.

Consider a certain chemical substance dispersed within an incompressible medium8 over a onedimensional space. Denote with c(x, t), with unit [1/m 3 ], the concentration of the substance within the medium at location x ∈ R and time t ∈ R + 0 . Further, J(x, t) is the flux at position x and time t. Now let us assume that there is an inflow of the medium at position x = 1, and an outflow at position x = 0. The inflow, and because of incompressibility of the medium, also the outflow, is assumed to have constant velocity v ≥ 0 over space. In particular, it holds that ∇v = 0. Further, the concentration of the substance in the inflow is 0 and the substance is neither generated nor consumed at any position x. We thus have, g(x, t) = 0 (4.16)

Its unit is [1/m 3 • m/s] = [1/(m 2 s)].
J(x, t) = -D∇ • c(x, t) + v • c(x, t) , (4.17)
where D > 0, with unit [m 2 /s], is the diffusion coefficient, assumed to be constant over space and time. In particular, we will use that ∇D = 0. The first term in (4.17) accounts for flux by diffusion, the second for flux by drift, also referred to as convection. Using, ∇v = 0 and ∇D = 0, we get

∂ ∂t c(x, t) -D∇ 2 • c(x, t) + v • ∇c(x, t) = g(x, t) . (4.18)
Let us next discretize (4.18) in space and time. For discretization in space, we uniformly quantize the sample space with discretization granularity δx > 0. Setting ĉ(i, t) = c(iδx, t), for i ∈ Z, we then use the facts that,

∇c(x, t) = lim δx→0 1 2 ĉ(i + 1, t) -ĉ(i, t) δx + ĉ(i, t) -ĉ(i -1, t) δx = lim δx→0 1 2δx (ĉ(i + 1, t) -ĉ(i -1, t)) (4.19) ∇ 2 c(x, t) = lim δx→0 1 δx ĉ(i + 1, t) -ĉ(i, t) δx - ĉ(i, t) -ĉ(i -1, t) δx = lim δx→0 1 (δx) 2 (ĉ(i + 1, t) -2ĉ(i, t) + ĉ(i -1, t)) . (4.20)
Clearly alternative discretization Ansätze could have been used. For example instead of the seemingly overcomplicated (4.19), simple forward or backward Euler formulas would have also fulfilled the required limit equations. The chosen discrete approximations have the benefit that they are symmetric in space, which will be crucial when analyzing the system in terms of dynamic communication graphs. Combining (4.15), (4.17), (4.19), and (4.20), we readily obtain

lim δt→0 ĉ(i, t + 1) -ĉ(i, t) δt = lim δx→0 1 (δx) 2 (ĉ(i + 1, t) -2ĉ(i, t) + ĉ(i -1, t)) -lim δx→0 v 2δx (ĉ(i + 1, t) -ĉ(i -1, t)) ,
where we used forward Euler discretization in time. From this we get the discrete time and space recurrence,

ĉ(i, t + 1) =ĉ(i, t) 1 - 2 δt(δx) 2 + ĉ(i -1, t) 1 δt(δx) 2 + v 2δtδx + ĉ(i + 1, t) 1 δt(δx) 2 - v 2δtδx .
Looking at this recurrence, we observe that:

1. The coefficients of ĉ for certain parameter ranges of δx > 0, δt > 0, and v ∈ R are within [0, 1]. In the following we will assume that the parameters are chosen such that this is the case. If not, one observes that they can be made to do so by decreasing δx and δt -this corresponds to a finer discretization of the differential equation.

2. The coefficients sum up to 1.

Viewing ĉ(i,

•) as the output of node i over time, the static communication graph is a line graph with nodes being bidirectionally connected to neighboring nodes on the line.

The above recurrence can thus be viewed as all nodes i on the line graph executing an averaging algorithm. The results previously discussed on averaging algorithms thus apply and in particular may be used to derive time bounds on when concentrations have sufficiently well equilibrated across the liner space. This view even carries over to the more interesting case of dynamic networks: assume instead of a constant v, a time dependent v(t). If so, weights within the averaging algorithm will change over time. This may result in some coefficients becoming (almost) 0, in which case we can remove these links from the communication network. The resulting network is not anymore bidirectional, and in fact may change over time as v(t) changes. Similar techniques may be used in higher dimensional spaces, with different and changing flows. Again previously discussed results on averaging algorithms apply.

Further reading. In [START_REF] Függer | Diffusive clock synchronization in highly dynamic networks[END_REF] we applied averaging algorithms to solve clock synchronization in network were the nodes to be synchronized reside within a dynamic network structure. Example of such networks are networks of sensor nodes in harsh environments, vehicles, or drones.

Chapter 5

Outlook

This chapter discusses results from the following research articles.

• [START_REF] Függer | Digital circuit design for biological and silicon computers[END_REF] Matthias Függer, Manish Kushwaha, Thomas Nowak. Digital circuit design for biological and silicon computers. In Vijai Singh, editor, Advances in Synthetic Biology. Springer, Heidelberg, March 2020.

The work compares digital circuits in computers made from silicon and those in synthetic biology aimed for implementation within microbiological entities like bacteria.

• Within a chemical reaction network (CRN) inspired by a growing population of two types of bacteria we analyze a simple protocol that we show to solve majority consensus with high probability if the initial gap between the number of the bacteria that make up the majority and the other bacteria is large enough. We also show that this happens in constant expected time and how this protocol can be used to implement Boolean gates.

Circuits in Microbiological Entities

So far, when we were discussing circuits, we made the silent assumption that they are intended for implementation in silicon; typically within the CMOS (Complementary Metal Oxide Semiconductor) process, which is the dominating design process for digital circuits at date. However, circuits are not restricted to gates in silicon. The by far larger body of existing circuits is discovered within viruses, cells, and among cells. These circuits sense environmental states, adapt internal states accordingly, and trigger externally observable actions. In the past two decades, additionally to naturally evolved circuits, engineered/synthetic circuits have been designed and implemented [START_REF] Nielsen | Genetic circuit design automation[END_REF]. While the focus in engineered circuits is on digital circuits with Boolean gates, naturally evolved circuits are typically mixed-signal: signal levels are controlled with feedback loops and adapt their set points over time to sense over large input ranges [START_REF] Alon | An introduction to systems biology: design principles of biological circuits[END_REF]. The interested reader is referred to [START_REF] Alon | An introduction to systems biology: design principles of biological circuits[END_REF]154] for an overview on such microbiological circuits. Teo et al. [START_REF] Teo | Synthetic biology: A unifying view and review using analog circuits[END_REF] discuss natural and synthetic circuits from an analog circuit perspective. An introduction to synthetic circuits is given in [START_REF] Myers | Engineering Genetic Circuits[END_REF][START_REF] Jennifer | Principles of genetic circuit design[END_REF].

In [START_REF] Függer | Digital circuit design for biological and silicon computers[END_REF] we discussed commonalities and differences of such circuits and circuits in silicon. We summarize some of these in the following.

Digital circuits

Like our initial assumption of silicon as the target material, we also focused on digital circuits in this writeup, motivated by their great success in numerous applications.

The concept of a digital circuit as opposed to an analog circuit allows the designer to implement noise-tolerant input-output behavior with manageable complexity for the design. Thereby tolerance to noise is achieved by partitioning the value domain into a clear logical 0, a clear logical 1, and an intermediate domain. For the computation the exact analog input and output values do not play a role. As long as they are (and with noise added, stay) within the respective 0 and 1 domains, the outputs also stay in their respective 0 and 1 domains. A priori, the circuit may behave arbitrarily, if this assumption is violated, e.g., with the inputs being in the intermediate domain. However, typically, further assumptions on the gate's behavior are made, e.g., that a single (fast enough) transition at the inputs of a certain gate produces a single transition at the output. In Chapter 3 we discussed circuit behavior under even weaker assumptions by considering operation in case of metastable, i.e., arbitrary and unstable, analog values.

To guarantee that noisy inputs which stay in their logical domains lead to outputs that stay in their logical domain, amplification (away from the intermediate domain) and saturation (to ensure tightly bounded logical domains) are used; see Here an identity gate is shown with input x and output y. The green input range that is significantly larger than the logical 0 domain is compressed into the logical 0 domain at the output.

Tightly bounded domains via saturation also ensure (i) fast transitions of outputs upon input changes and (ii) simple composition of gates with matching domains.

Specifying Circuits

Widely used hardware description languages are Verilog and VHDL. While similar to softwaretargeted high-level languages in several aspects, main differences to software-targeted languages are (i) a high degree of inherent parallelism: in hardware each gate operates in parallel to each other gate, and (ii) dedicated means to specify structural composition of modules. We will briefly describe a third language, Communicating hardware processes (CHP) [START_REF] Martin | Programming in vlsi: From communicating processes to delay-insensitive circuits[END_REF] that we believe to be of particular interest within synthetic biology.

Synthetic biology has not yet decided on a common specification languages. While subsets of Verilog have been used [START_REF] Nielsen | Genetic circuit design automation[END_REF], designs are typically specified in SBML and stochastic semantics and ODE semantics of these are used for simulations. At the heart of both semantics are chemical reaction networks (CRNs) that we will discuss in this chapter later on.

Communicating hardware processes. The language of communicating sequential processes (CSP) by Hoare [START_REF] Antony | Communicating sequential processes[END_REF] greatly shaped the landscape of parallel process semantics until today. Martin [START_REF] Martin | Programming in vlsi: From communicating processes to delay-insensitive circuits[END_REF] adapted this software-centered undertaking to circuits in hardware. In [START_REF] Függer | Digital circuit design for biological and silicon computers[END_REF] we discussed a simplified/restricted class of CHP as a language to specify circuits in silicon. However, Chemical reaction networks. A chemical reaction network describes the evolution of species counts over time. Updates to species counts follow (probabilistic) rules specified via reactions with reactants on one side and products on the other side. Each reaction further has a kinetics assigned to it that determines the rate of the reaction. Typically the mass action kinetics is used, where the rate is fully determined by a rate constant.

While CRNs have received some attention in the context of distributed computing, see, e.g. [START_REF] Ho-Lin Chen | Deterministic function computation with chemical reaction networks[END_REF][START_REF] Severson | Composable computation in discrete chemical reaction networks[END_REF], the more restricted population protocols [START_REF] Angluin | The computational power of population protocols[END_REF][START_REF] Aspnes | An introduction to population protocols[END_REF] have received more attention in distributed computing. Examples of problems studied are function computation [START_REF] Angluin | The computational power of population protocols[END_REF] and (selfstabilizing) leader election [START_REF] Doty | Stable leader election in population protocols requires linear time[END_REF][START_REF] Burman | Efficient selfstabilizing leader election in population protocols[END_REF] among others. Population protocols restrict reactions to have exactly two reactants and two products and assume a fairness condition on events motivated by a stochastic interpretation rather than rates. Several variants of population protocols have been proposed [START_REF] Aspnes | An introduction to population protocols[END_REF]; some models allowing for infinitely large species sets (where agents have nonconstant state). An interesting variant that partially reintroduces timing into population protocols is by Beauquier et al. [START_REF] Beauquier | On utilizing speed in networks of mobile agents[END_REF].

Following a standard stochastic formalization based on the collisions between species [START_REF] Daniel T Gillespie | Exact stochastic simulation of coupled chemical reactions[END_REF] that we also used in [START_REF] Cho | Distributed computation with continual population growth[END_REF], CRNs are defined by:

• A set S of species as well as an initial count I : S → N for each species.

• A set of reactions upon the species. Thereby a reaction is triple (r, p, α) where r, p ∈ S → N and the reaction's rate constant α ∈ R + 0 . A reactant is a species with non-zero count in r, a product a species with non-zero count in p. For ease of notation, one writes r α p instead of (r, p, α). Typically only non-zero entries of r and p are written as weighted sums.

Executions are sequences of configurations that are obtained by successively applying applicable reactions to the initial configuration given by the initial count I:

• A configuration of a CRN is an element of S → N. As a unit we will use counts within a fixed volume v > 0. The fixed volume has unit [l], and the counts are unitless numbers. Equivalently, species counts will sometimes be given in terms of mol (within the fixed volume).

where c(S) r(S) is the binomial coefficient of c(S) and r(S). In particular, the binomial coefficient is 1 if r(S) = 0, and 0 if r(S) > c(S).

Following the above specification, the unit [α] depends on the number of reactants. For reactions with a single reactant, it is [mol -1 s -1 ] for S in mol and [s -1 ] for unitless S, resulting in the propensity having unit [s ]. We make use of the stochastic semantics of rates in the following.

• Applying reaction r α p to configuration c, results in configuration c = cr + p.

• The stochastic kinetics of a CRN is a continuous-time Markov chain whose states are the configurations, see, e.g., [START_REF] Sheldon | Introduction to probability models[END_REF]. For any two states x and y, let the transition rate Q(x, y) be the sum of propensities of reactions in configuration x that result in configuration y if being applied to x.

Thus, in the stochastic model, species counts within an a priori fixed volume change over time, with the time until a reaction takes place being an exponential random variable with rate equal to the reaction's propensity [START_REF] Daniel T Gillespie | Exact stochastic simulation of coupled chemical reactions[END_REF]. The following states propensities for some example reactions and configurations: Commonalities between CHP and CRN specifications. The production rule A → B ↑ with some delay function and the reaction A α A + B clearly bear some similarities: both trigger a rising voltage of A or increase the species count of A in presence of B. In CMOS, production rules occur in pairs with complementary guards, however, and biological applications of CRNs require conservation of mass which is violated by the above reaction. We will detail on this in the next section.

Implementing Circuits: Decoupling and Driving

A key benefit of circuits implemented in silicon, and in particular in CMOS, is decoupling between gates. Ideally, a gate's output behavior does not change its input voltage, i.e., the output behavior of the gate that drives one of its inputs. High-impedance decoupling with field-effect transistors (FETs) is central to achieve this goal. The charge used to load the gate's output capacitance is not taken from the input charge, but from an ideally undepletable power source connected to the gate's V DD input.

A second key benefit in CMOS that does not necessarily hold for other processes (e.g., NMOS) is the fact that rising and falling output transitions are actively driven with low resistance and not just pulled up/down by a passive resistor.

While also applicable to synthetic biological circuits, many circuits do not ensure both properties. In [START_REF] Függer | Digital circuit design for biological and silicon computers[END_REF] we discussed circuits in CMOS and biology with respect to decoupling and how they drive outputs. The discussion is summarized in the following.

CMOS gate. Given two production rules with negated Boolean guards, one setting an output to 0 and the other to 1, one can readily implement these rules within a combinational CMOS gate. For a gate with the rules P up → Z ↑ P down → Z ↓ one first ensures that P up comprises only of AND/OR combinations of negated variables, and P down of AND/OR combinations of positive variables. If not, inputs are negated, or duplicated and negated, accordingly. A valid example is P up = ¬A ∧ ¬B and P down = A ∨ B, corresponding to a Nor-gate.

Each rule is then implemented by its own transistor stack: the P up by the p-stack of p-type FET transistors, and the P down by the n-stack of n-type FET transistors. Purpose of the respective stacks is to connect the output to V DD or ground when the respective guard becomes true, and ground (= logical 0) The output load is represented by a capacitive load. For the inverter with input A and output Z, P up = ¬A and P down = A. The p-stack (above, in green) is the above p-type FET transistor and connects V DD to Z if A = 0. The n-stack (below, in magenta) is the bottom n-type FET transistor and connects ground to Z if A = 1. From [START_REF] Függer | Digital circuit design for biological and silicon computers[END_REF].

charging/discharging the output capacitance via the connected stack, while the other stack is disconnected. Figure 5.2 shows this schematic for a CMOS Inv-gate. Driving outputs. The CMOS Inv implementation actively drives 0 via the connected n-stack and 1 via the connected p-stack, depending on whether the gate's input is 1 or 0. No highresistance pull-networks are used to drive either value.

Decoupling inputs and outputs. When driving, the Inv-gate uses charge from the power source via its V DD port, rather than using charge from input A. Similarly, the output is discharged to ground. Both thus do not change the input's value.

Microbiological gates. Synthetic gates in living organisms have been built making use of many different pathways within a cell like a bacterial host [START_REF] Jennifer | Principles of genetic circuit design[END_REF]. Examples range from transcriptional control via transcription factors [START_REF] Nielsen | Genetic circuit design automation[END_REF], CRISPRi (such as CRISPR-dCas9) [START_REF] Miles W Gander | Digital logic circuits in yeast with crispr-dcas9 nor gates[END_REF][START_REF] Santos-Moreno | Multistable and dynamic crispri-based synthetic circuits[END_REF][START_REF] Zhang | Engineered dcas9 with reduced toxicity in bacteria: implications for genetic circuit design[END_REF] to recombinase/flippase-based approaches [START_REF] Guiziou | An automated design framework for multicellular recombinase logic[END_REF].

We will focus on enzymatic-type reactions that are at the basis of several evolved and synthetic circuits. Thereby a substrate species S is modified to obtain a product species P via an enzyme E. Letting S be the input and P the output, and using the notation from CMOS gates of A = S and Z = P , the reaction is of the form

A + E AE → E + O .
Thus there is no decoupling happening, with the input being directly used to produce the output. Decoupling is obtained, however, if E = A plays the role of the input and S is the abundant charge available via V DD , in which case the gate becomes

S + A AS → A + O .
To be precise, and much like gate current in CMOS, the reaction may bind a considerable amount of input A while producing O. Decoupling is maximal if a small such amount already leads to a large production of O; ensured via the reactions' rates.

A related decoupling, combining the above reactions, is by letting AE be the active enzyme that uses a substrate to produce O from S. In this case,

A + E AE → AE + O S
The input/output behavior of the last two reactions can be described by the single production rule A → Z ↑ in case A = 1. by contrast, if A = 0, the output Z is not actively driven to 0, but decays; much like in a pull-down network. We may thus write Z → Z ↓, since this process is ongoing even if A = 1. The semantics of such a production rule -in particular since two conflicting rules may be active at the same time -may be defined via CRNs.

For a discussion of more involved microbiological gates and their corresponding production rules, the reader is referred to [START_REF] Függer | Digital circuit design for biological and silicon computers[END_REF].

Distributed Microbiological Circuits

Circuits that are distributed in space, e.g., by circuit components partitioned among communicating host cells, have recently gained in interest [START_REF] Macía | Distributed computation: the new wave of synthetic biology devices[END_REF]. A main motivation for distribution is the large metabolic load of even small circuits of a few gates. Other motivations are solving problems that are inherently distributed in nature and robustness to failures in a single cell.

In the following we will summarize our work on distributed computation of growing microbiological entities [START_REF] Cho | Distributed computation with continual population growth[END_REF], as it is the case for bacteria.

Circuits in Growing Populations as Chemical Reaction Networks

In [START_REF] Cho | Distributed computation with continual population growth[END_REF] we defined (distributed) protocols of birth systems as a model for circuits executed by growing populations of microbiological entities like bacteria.

Definition 129 ([151]

). A protocol for a birth system with input species I and output species O is a CRN with the following properties:

• Sets I, called the protocol's inputs, and O, the protocol's outputs, are not necessarily disjoint finite sets.

• The CRN's set of species S comprises the species in I ∪ O and a finite disjoint set of internal species L.

• For each internal or output species, the protocol defines the initial species counts.

• The protocol specifies a finite set of reactions R on the species in S.

• For each species X ∈ S, there is a duplication reaction of the form X γ 2X . All duplication reactions have the same reaction rate constant γ > 0.

The probabilistic execution space of a protocol for a birth death system is then defined by the protocol and initial species counts for its inputs. It is the execution space of the corresponding CRN with respective initial counts.

Growing Populations Solving Majority Consensus

Consensus-type problems as discussed in Chapter 4 also play a role within distributed circuits. However, a variant of consensus with a stronger validity condition is relevant in these systems. In [START_REF] Cho | Distributed computation with continual population growth[END_REF] we identified majority consensus as a key building block to tolerate noise in distributed circuits: microbiological agents may deviate from the correct outcome of a computation, but the majority consensus building block will make sure that the correct ones will finally determine the outcome of the computation; much like the amplification of analog values to clear logical values in CMOS circuits. Formally, we defined: Definition 130 (A-B protocol, from [START_REF] Cho | Distributed computation with continual population growth[END_REF]). The A-B protocol is a protocol for a birth system with input species A and B. Given a rate constant δ > 0, its reactions are:

A γ 2A B γ 2B A + B δ ∅
The protocol thus has an annihilation rule between A and B as the single rule besides the required birth rules. We then defined consensus and majority consensus by: Definition 131 (Consensus and majority consensus, from [START_REF] Cho | Distributed computation with continual population growth[END_REF]). Consensus is reached if at least one of A or B becomes extinct. Majority consensus is reached if:

1. In case initially A(0) = B(0), consensus is reached and the species that was initially in majority is not extinct.

2. In case initially A(0) = B(0), one species is extinct and the other is not.

Our main result on majority consensus in [START_REF] Cho | Distributed computation with continual population growth[END_REF] is stated in the following. Its proof is based on discrete and continuous time couplings to random walks. The gate thus provides a linear gap at its output by producing sufficiently separated dual-rail output species in a sufficient number, given that the dual-rail input species are sufficiently noisefree. Combining the gate with the A-B protocol as an amplification stage, thus allows one to compute Boolean functions and afterwards regenerate the Boolean signal; ready to be fed into the next upstream gate.

Concluding Remarks

Low-level implementations with design entries at the hardware/circuit-level often rely on statemachine-based approaches. Assumptions made during the design and analysis stages greatly ease this process. However, in several cases simplifying assumptions have to be dropped. Examples are (i) pronounced analog/timed behavior of switching signals, the related problem of non-binary signals, respectively, metastable upsets, and (iii) faulty or mobile components that led to distributed circuits with unstable communication between components. This work discussed approaches and solutions to these cases.

In this last chapter a quick overview on our recent work was presented: the study and design of synthetic biological distributed circuits. At the time of writing, Manish Kushwaha (INRAE), Thomas Nowak (LRI), and myself have formed a group and are working on further pushing this direction. We belief that a combined, interdisciplinary approach in the domains of circuit design, distributed computing, and synthetic biology has great potential to contribute to the road that recent work in the domain of synthetic biology has shown with numerous applications in drug production and intelligent drugs. Based on our previous work and recent unpublished work, we are working on communicating bacterial consortia to design robust distributed circuits. Besides many implementation and circuit design questions that have to be solved along this road, immediate questions from the theory of distributed computing are (i) improved majority consensus algorithms and/or an improved analysis with resource limitations, and (ii) stability of co-cultures that run different circuit parts. The author believes that advancing on some of the techniques presented in this work will be fruitful in solving these questions.

Figure 1 . 1 :

 11 Figure 1.1: Example circuit with two inputs, two outputs, and internal nodes. Internal and output node labels are shown in gray.

Figure 1 .Figure 1 . 2 :Figure 1 . 3 :

 11213 Figure 1.2: Example of a channel (d, f ) with input signals s 1 and s 2 and f ≡ And. The channel induces the output signal o.

Figure 1 . 4 :Example 4 (

 144 Figure 1.4: Channel from Example 3.

3 . 5 . 6 .

 356 The following rising transition of s 2 at time 2 results in an event (2 + δ , 0) = (3, 0) being added to o. 4. Thus o = [(-∞, 0), (4, 1), (3, 0)]. Function doCancellations returns o = [(-∞, 0), (3, 0)], canceling the event at time 4. Function removeRedundant returns o = [(-∞, 0)], removing the second redundant transition.

Figure 1 . 5 :

 15 Figure 1.5: Channel from Example 4. Two types of order violations are depicted in the two scenarios.(left) An order violation between events with the same value; here 1. The event with the dotted arrow is canceled. (right) An order violation between events with opposing values. Again, the event with the dotted arrow is canceled. The second event is later removed by the algorithm, since it is redundant.

Figure 1 . 6 :

 16 Figure 1.6: Signals of a register initialized to 0, first sampling 1 and then 0. Red areas indicate setup-hold windows where D is required to be stable.

Figure 1 . 8 :

 18 Figure 1.8: Phases of a clock cycle. Red (X) indicates unstable signals. (1) register output stabilization, (2) propagation of outputs through combinational logic to register inputs, and (3) stable register inputs.

Figure 2 . 1 :

 21 Figure 2.1: A glitch propagating through a buffer chain. The glitch shrinks in length and is suppressed after the second buffer. Blue arrows indicate combined gate and interconnect delays.

  The pulse at the input of buffer g14 is attenuated by buffer g14 and filtered out by g15.

Figure 2 . 2 :

 22 Figure 2.2: Two scenarios of a buffer chain with a short input pulse. The first 4 buffers, g10 to g13, are used to shape the input signal. Input signals of the buffers g14, g15, g16 are shown in the figure. Threshold crossings are shown as red markings. Layout and routing was done in Cadence Encounter, Spice simulations in Cadence Spectre. V DD = 0.8 V.

τ 4 T 4 (

 44 b) Forgetful bounded single-history channel.

Figure 2 . 3 :

 23 Figure 2.3: Behavior of a non-forgetful and a forgetful bounded single-history channel with f ≡ id and identical δ. The output events at times t 2 and t 3 are canceled. This leads to different T 4 for the two channel variants.

  l i b r a r y i e e e ; use i e e e . s t d l o g i c 1 1 6 4 . a l l ; e n t i t y BUF i s Port ( X: in s t d l o g i c ; Y: out s t d l o g i c ) ; end BUF; a r c h i t e c t u r e B U F t r a n s p o r t of BUF i s begin

Figure 2 . 1 δ 1 Figure 2 . 4 :

 21124 Figure 2.4: Pure delay function with parameters δ ∞ = 1 (blue) and δ ∞ = 1.5 (red).

T 1 δ 1 T 0 Figure 2 . 5 :

 1025 Figure 2.5: Inertial delay function with parameters T 0 = 1 and δ ∞ = 1 (blue) and δ ∞ = 1.5 (red).

T 1 δ 1 Figure 2 . 6 :

 126 Figure 2.6: Two DDM delay functions with parameters τ = 1, T 0 = 1, and δ ∞ = 1 (blue) and δ ∞ = 1.5 (red).

Figure 2 . 7 :

 27 Figure 2.7: Reducing a single-input bistable element stabilizing within bounded time to a bounded SPF circuit.

Figure 2 .

 2 Figure 2.8 depicts the circuit that solve unbounded SPF. It comprises of a storage loop formed by the Nor and Inv gates, and a successory low threshold Inv gate. Such an inverter has a shifted input-output function that maps a larger (upper) voltage range of input values to logical 1 and a smaller (lower) voltage range to logical 1.Figure2.9 provides an intuition why the circuit indeed solves the unbounded SPF problem: The (blue) input signal may lead to a metastable upset of the storage loop, resulting in the (green) signal at the low threshold inverter input. However, the low-threshold inverter interprets a sufficiently large voltage range, including the metastable region of the storage loop, as a logical 1 and thus maps it to 1. Metastable upsets thus lead to arbitrarily late, but not spurious, transitions at the inverter output. One easily verifies that the circuit thus fulfills all properties required for solving unbounded SPF.

. 10 )Figure 2 . 1 δ 1 Figure 2 . 11 :

 10211211 Figure 2.11 on page 24 shows examples for delay functions δ ↑ for an exp-channel with two different parameters.

Figure 2 .

 2

Figure 2 . 14 :

 214 Figure 2.14: Measured (solid) and simulated (dashed) waveforms at taps Q1 , Q 3 , Q 5 (bottom, shifted by -V dd ) and Q 2 , Q 4 , Q 6 (top), with V DD = 0.6 V.The lower output voltage is due to the amplifier gain of 0.15. From[START_REF] Najvirt | Experimental validation of a faithful binary circuit model[END_REF].

Figure 2 . 16 :

 216 Figure 2.16: Measured waveform (solid) for the UMC-90 inverter chain, with the predictions according to the involution model (red long up/down-arrows) and the DDM (blue short up/down arrows). From [20].

Figure 3 . 1 :

 31 Figure 3.1: Crossing clock domains in in a Moore state machine implementation. The dashed output register is not necessarily part of the implementation. On the left and right circuits that are not under the control of the clock clk, e.g., either unclocked or clocked by a different clock signal.

Figure 3 . 3 :

 33 Figure 3.3: Synchronous circuit computing f : synchronize followed by compute.

Figure 3 . 4 :

 34 Figure 3.4: Metastability-containing computation of f : compute during synchronization.

Figure 3 . 5 :

 35 Figure 3.5: Clocked Moore state machine implementation with pre-initialized input registers.

1 Figure 3 . 6 :

 136 Figure 3.6: Three register types.

Figure 3 .Figure 3 . 7 :

 337 Figure 3.7 shows the schematics of the combinational circuit Smux that resembles the standard gate-level circuit implementation of a multiplexer. Indeed the circuit implements Mux in our model, i.e., is a multiplexer. Note that technically, simple input and output registers are required by our model. Since this is a single round computation, we omit them.

Figure 3 . 8 :

 38 Figure 3.8: The metastability-containing multiplexer Cmux1.

Figure 3 . 9 :

 39 Figure 3.9: Metastability-containing multiplexer using a 1-masking register.

Lemma 43 (

 43 [START_REF] Friedrichs | Metastability-containing circuits[END_REF]). Let C be a purely combination circuit with m inputs and let f C : B m M → B n M be the function that maps C's input to its (unique, since C only comprises of gates) output with n bits. Then for all inputs ι

Lemma 65 .

 65 There exists no circuit C such that ∈ N + rounds of C implement f Mcr,n with < n, i.e., that solves the n-bit metastability-containing replication problem in < n rounds.Lemmas 64 and 65 finally yield the existence of a non-trivial hierarchy: Theorem 66 ([START_REF] Friedrichs | Metastability-containing circuits[END_REF]). For all r ∈ N + , we have Fun r M Fun r+1 M .A characterization of the classes Fun r M is an open problem and subject to ongoing research.

Example 69 .

 69 For the k-bit binary code, γ = bin, with bin : {0, . . . , 2 k -1} → B k , encoded numbers are given by un(0) = 0 . . . 0, un(1) = 0 . . . 01, un(2) = 0 . . . 010, etc. Example 70. For the k-bit binary reflected gray code (BRGC), γ = rg, with rg : {0, . . . , 2 k -1} → B k with un(0) = 0 . . . 0, un(1) = 0 . . . 01, un(2) = 0 . . . 011, un(3) = 0 . . . 010, etc.

2 .

 2 f Inc,un ((0) un , (7) un ) = (7) un = 011111111 and f Inc,un ((1) un , (7) un ) = (8) un = 111111111.Thus f Inc,un (M,[START_REF] Maly | Realistic fault modeling for vlsi testing[END_REF] un ) = Res M (M1111111).

Figure 3 . 11 :

 311 Figure 3.11: Tapped delay-line TDC. Latches are initially enabled and output 0. The delayed starting signal iteratively sets latches to 1 until the stopping signal disables them.

Figure 3 . 12 :

 312 Figure 3.12: Critical windows for the linear TDC in Figure 3.11 with well separated windows.

Figure 3 . 13 :

 313 Figure 3.13: Critical windows for the linear TDC in Figure 3.11 with overlapping critical windows.

Figure 3 . 14 :

 314 Figure 3.14: Generic ring TDC architecture with coarse counter output C. Latches and counter are initialized to 0. The counter increments on rising and falling transitions on inc if enabled.

Figure 3 Figure 3 .

 33 Figure 3.15: TDC-bin implementation of the coarse counter. Binary counters C 0 and C 1 as well as latch L are initialized to 0. The increment inputs of C 0 and C 1 are driven via a buffer with delay T Buf . Counter C 0 increments on rising transitions and counter C 1 on falling transitions.

Figure 3 . 16 :

 316 Figure 3.16: Critical windows for TDC-bin.

  77 hints at an interesting interpretation of the counter values and b. Since C b is a binary counter, the binary representation of 2C b + b is easily obtained by concatenation of C b and b.

Figure 3 .

 3 Figure 3.17: TDC-gray design. The counter C (shown in blue) is initialized to 1. Register R C is initialized to 0. Both are triggered by rising transitions.

Figure 3 . 18 :

 318 Figure 3.18: Critical windows for TDC-gray. Note the period during which the counter C increments (in blue) and the subsequent critical window intervals W 1 C and W 2 C of the register R C that latches the result.

Figures 3. 19

 19 Figures 3.19, 3.20, and 3.21 demonstrate Theorem 81. They show three cases for even, odd, and metastable coarse counters. Observe that in all cases, the final BRGC encoded values correctly encode the TDC measurement value with the same precision as the inputs (precision 1).

Figure 3 . 19 :Figure 3 . 20 : 1 Figure 3 . 21 :

 3193201321 Figures 3.19, 3.20, and 3.21 demonstrate Theorem 81. They show three cases for even, odd, and metastable coarse counters. Observe that in all cases, the final BRGC encoded values correctly encode the TDC measurement value with the same precision as the inputs (precision 1).

Figure 3 . 22 :

 322 Figure 3.22: TDC-graybit design. The counter C (shown in blue) and the flip-flop L are initialized to 0.

Figure 3 . 23 :

 323 Figure 3.23: Critical windows for TDC-graybit.

Figure 3 . 24 :

 324 Figure 3.24: Computing the minimum of two thermometer encoded values x and y. The circuit is metastability-containing: an input with precision 1 results in an output with precision 1.

(

  C1) The output signal o always has instantaneous frequencies within [s -, f + ]. (C2) If i = 0 during time [t -T osc , t] then the instantaneous output frequency of c at time t is within the slow frequency bounds [s -, s + ]. We say the oscillator is in slow mode at time t. (C3) If i = 1 during time [t -T osc , t] then the instantaneous output frequency of c at time t is within the fast frequency bounds [f -, f + ]. We say the oscillator is in fast mode at time t.

Figure 3 . 25 :

 325 Figure 3.25: Metastability-tolerant implementation of the Lynch-Welch algorithm to tolerate Byzantine faults in a model that accounts for metastability. The circuitry for node i ∈ [n] is shown. The time-offset of the received clock transitions is measured in a metastability-containing TDC with BRGC encoded outputs. The values are sorted, and the f +1 and n-f largest re-encoded to temperature code. The two values are then used to change node i's oscillator frequency.

Figure 3 .Figure 3 . 28 :

 3328 Figure 3.28 shows a subtrace of the VHDL simulations with potentially metastable signals in red color.

  l i b r a r y IEEE ; use IEEE . s t d l o g i c 1 1 6 4 . a l l ; use IEEE . m a t h r e a l . a l l ; entity Ring i s port ( c l k s n d : in s t d l o g i c ; c l k r c v : in s t d l o g i c ; f u l l : out s t d l o g i c v e c t o r ( 0 to 1 ) := " 10 " ) ; end Ring ; architecture behv of Ring i s s h a r e d variable s n d a d d r : i n t e g e r := 1 ; s h a r e d variable r c v a d d r : i n t e g e r := 0 ; constant tau : time := 0 . 1 2 5 ns ; constant N: i n t e g e r := 2 ; begin u p d a t e f u l l f l a g s : process ( c l k s n d , c l k r c v ) --v a r i a b l e s f o r uniform variable seed1 , s e e d 2 : p o s i t i v e ; variable r : r e a l ; variable d : time ; begin i f ( c l k s n d ' e v e n t and c l k s n d = '1 ') then --w r i t e t h e f u l l f l a g uniform ( seed1 , seed2 , r ) ; d := r * tau ; f u l l ( s n d a d d r ) <= transport 'X' a f t e r 0 ps , ' 1 ' a f t e r tau ; --( wc ) was d --f i n a l l y i n c r e m e n t a d d r e s s p o i n t e r s n d a d d r := ( s n d a d d r + 1 ) mod N; end i f ; i f ( c l k r c v ' e v e n t and c l k r c v = '1 ') then --w r i t e t h e f u l l f l a g uniform ( seed1 , seed2 , r ) ; d := r * tau ; f u l l ( r c v a d d r ) <= transport 'X' a f t e r 0 ps , ' 0 ' a f t e r tau ; --( wc ) was d --f i n a l l y i n c r e m e n t a d d r e s s p o i n t e r r c v a d d r := ( r c v a d d r + 1 ) mod N; end i f ; end process ; end behv ;

Figure 3 . 29 :

 329 Figure 3.29: Example execution of state transitions. The current superposition state is shown in gray.In the execution the superposition collapses at time 3 into a single state. From[START_REF] Tarawneh | Metastability tolerant computing[END_REF].

Figure 3 . 30 :

 330 Figure 3.30: System architecture of a direct frequency adaptation module implementation: the DD senses occurrence of a droop and signals the ϕ module when to shift the phase of the input clock.

Figure 3 .

 3 31 on page 71 shows a natural solution to this problem: the use of synchronizers for the enable signal. Different shades of red symbolically show the decrease of probability of a metastable enable output from right to left in the figure.

Figure 3 .Figure 3 . 31 :Figure 3 . 32 :

 3331332 Figure 3.31: System architecture of the frequency adaptation module implementation with synchronizers for the enable signal.

Figure 3 . 33 :

 333 Figure 3.33: System architecture of the proposed frequency adaptation module implementation from[START_REF] Függer | Fast all-digital clock frequency adaptation circuit for voltage droop tolerance[END_REF].

Figure

  Figure 3.34 shows the timeline from the occurrence of a droop to the application of a phase shift. If the DD issues a clear active enable, the shift is immediately applied at the last delay element. Potentially the DD may be about to change its enable output during a clock transition happening at the last delay element DE n. In this case the enable output signal(s) of DE n may become metastable, and a priori, this may lead to a glitch at the clock output C O . In[START_REF] Függer | Fast all-digital clock frequency adaptation circuit for voltage droop tolerance[END_REF] we proposed a design based on a metastability-containing implementation of DE that effectively computes with such signals and prevents a glitch form occurring. The latter is possible since the output space of a phase shift is continuous. But, since we cannot prevent enable signals from becoming metastable, we split them into two signals with (monotonicity) guarantees between them when becoming metastable. The interested reader is referred to the article[START_REF] Függer | Fast all-digital clock frequency adaptation circuit for voltage droop tolerance[END_REF] for the circuitry and its analysis.

Figure 3 . 34 :

 334 Figure 3.34: Timeline from droop happening until application of the phase shift at the phase shift module ϕ.

Figure 4 .

 4 1 (a) depicts a communication graph that is readily seen to be non-split: nodes 1

Figure 4 . 1 :

 41 Figure 4.1: (a) Non-split and (b) rooted communication graph with set of nodes [3]. Self-loops, that exist at all nodes, are not shown.

Figures 4. 1

 1

  (a) is 1 since all nodes are reachable from node 1 over 1 edge. The graph in Figure4.1 (b) as radius 2 with all nodes reachable from node 2 over 2 edges.

3 G 2 Figure 4 . 2 :

 3242 Figure 4.2: Non-split graph from graph product. Self-loops are not shown.

Example 98 .

 98

Figure 4 .

 4 3 on page 82 shows example executions for two different averaging algorithms: the equal neighbor algorithm and the midpoint algorithm. Both are executed within a network model comprising three rooted communication graphs G 0 , G 1 , and G 2 shown in the figure.

1 Figure 4 . 3 :

 143 Figure 4.3: Two example executions for two algorithms executed in a system with network model N = {G 0 , G 1 , G 2 } as specified in the figure.There are N = 3 nodes, with initial values 1 for node 1 (red, left), 0 for node 2 (black, bottom), and 0.1 for node 3 (blue, right). For each node i its state x i is depicted over 10 rounds. All graphs are rooted and have been chosen uniformly at random from the network model along the execution.

Figure 4 . 5 :

 45 Figure 4.5: A system of N = 3 nodes with node states from dimension d = 3. The figures shows the outputs of the three nodes during a prefix of an execution of the equal neighborhood algorithm for T = 5 rounds. The communication graphs were chosen uniformly at random from the network model shown at the top of the figure.

Figure 4 . 6 :

 46 Figure 4.6: A system of N = 3 nodes with node states from dimension d = 3. The figures shows the outputs of the three nodes during a prefix of an execution of the MidExtremes algorithm for T = 5 rounds. The communication graphs were chosen uniformly at random from the network model shown in Figure 4.5.

Theorem 117 (

 117 [START_REF] Charron-Bost | Multidimensional asymptotic consensus in dynamic networks[END_REF]). For a non-split network model and input values from an arbitrary dimension d ≥ 1, the Centroid algorithm guarantees a round-by-round output convergence ratio of c(k) ≤ d d + 1

Theorem 118 (

 118 [START_REF] Függer | Fast multidimensional asymptotic and approximate consensus[END_REF]). For a non-split network model and input values from an arbitrary dimension d ≥ 1, the MidExtremes algorithm guarantees a round-by-round output convergence ratio of c(k) ≤ 7/8 for all rounds k ≥ 1. In the particular case of d = 1, the algorithm is equivalent to the midpoint algorithm with c(k) ≤ 1/2. An analogous result was obtained for the ApproachExtremes algorithm. The performance bound we proved is slightly worse than for the MidExtremes algorithm.Theorem 119([121]). For a non-split network model and input values from an arbitrary dimension d ≥ 1, the ApproachExtremes algorithm guarantees a round-by-round output convergence ratio of c(k) ≤ 31/32 for all rounds k ≥ 1. In the particular case of d = 1, the algorithm achieves c(k) ≤ 3/4.

Figure 4 . 7 :

 47 Figure 4.7: The rooted communication graphs H 0 , H 1 , and H 2 for n = 2. Self-loops are shown.From[START_REF] Függer | Tight bounds for asymptotic and approximate consensus[END_REF].

3 Figure 4 . 9 :

 349 Figure 4.9: Rooted communication graph Ψ 1 , Ψ 2 , and Ψ 3 for n = 6. Self-loops are omitted.

Figure 5 Figure 5 . 1 :

 551 Figure 5.1: Amplification and saturation in digital gates. Here an identity gate is shown with input x and output y. The green input range that is significantly larger than the logical 0 domain is compressed into the logical 0 domain at the output.

•

  For a species S, we use S = S(S) to denote this count, and [S] 1 as its molar concentration in [mol/l] = [M ]. • A reaction r α p is applicable to configuration c if r(S) ≤ c(S) for all S ∈ S. The propensity of reaction r α p in configuration c is equal to α S∈S c(S) r(S) ,

  -1 ]. For reactions with two reactants, it is [mol -2 s -1 ] respectively [s -1 ], again resulting in unit [s -1 ] for propensity. This deviates from notations for ODE semantics where the additive contribution to the rate of change d[P ]/dt 2 by a reaction r α p for product P is given as α p(P ) S∈S c(S) r(S) (5.2) instead of (5.1). An analogous additive negative contribution holds if P appears as a reactant in a reaction. Since (5.2) describes the change of [P ] over time, the unit of the term is [M/s]. In this case, for reactions with a single reactant, [α ] = [s -1 ] and for two reactants, [α ] = [s -1 M -1

Example 128 (

 128 CRN). Consider the reaction A + B α A and configuration c with c(A) = 10 and c(B) = 5. The propensity of this reaction in configuration c is α • c(A) • c(B). The reaction's application results in the configuration with c(A) = 10 and c(B) = 4. The propensity of A γ ∅ is γ • c(A). The reaction's application results in the configuration with c(A) = 9 and c(B) = 5.The propensity of2A δ ∅ is δ • 1 2 • c(A) • (c(A) -1). The reaction's application results in the configuration with c(A) = 8 and c(B) = 5.

Figure 5 . 2 :

 52 Figure 5.2: CMOS implementation of an Inv-gate (left) driving its output, e.g., a gate (right).The output load is represented by a capacitive load. For the inverter with input A and output Z, P up = ¬A and P down = A. The p-stack (above, in green) is the above p-type FET transistor and connects V DD to Z if A = 0. The n-stack (below, in magenta) is the bottom n-type FET transistor and connects ground to Z if A = 1. From[START_REF] Függer | Digital circuit design for biological and silicon computers[END_REF].

Figure 5 .Figure 5 . 3 :

 553 Figure 5.3: CMOS implementation of an Inv-gate in operation. Both Boolean input cases along with charging and discharging paths are shown. From [150].

Theorem 132 (

 132 [START_REF] Cho | Distributed computation with continual population growth[END_REF]). Given,• an initial population n = A(0) + B(0), and• an initial gap ∆ = |A(0) -B(0)|,the A-B protocol reaches consensus in expected time O(1) and in time O(log n) with high probability. It reaches majority consensus with probability 1 -e -Ω(∆ 2 /n) . From this one obtains: Corollary 133 ([151]). Given, • an initial population n = A(0) + B(0), and • an initial gap ∆ = |A(0) -B(0)| ∈ Ω √ n log n , the A-B protocol reaches consensus in expected time O(1) and in time O(log n) with high probability. It reaches majority consensus with high probability.• Y (t) = n, and• Y y (t) -Y ¬y (t) = Ω(n), where y = ¬(a ∧ b).

  Algorithm 1 Algorithm computing the induced output signal until time t ≥ 0. Input: signals s 1 , . . . , s k and time t ← smallest time greater than τ of an event in s 1 , . . . , s k ; +∞ if does not exist

	Output: signal o
	τ ← -∞	initial event time
	o ←	initial event list
	do
	δ ← δ(τ ; s)	get delay
	v ← f s 1 (τ ), . . . , s k (τ )	new output value
	o.append (τ + δ , v)	add event
	τ while τ ≤ t
	o ← doCancellations(o)	cancel events that violate order
	o ← removeRedundant(o)	generate signal without redundant events
		add event
	end for
	return Pending
	end function
	function removeRedundant(s)	defined for signals s with finite number of events
	if no events in s then
	return s
	end if
	Pending ←
	Pending.append first event in s).

function doCancellations(s) defined for signals s with finite number of events Pending ← for (τ, v) in s do remove all events with times τ ≥ τ from Pending we say (τ, v) cancels these events Pending.append (τ, v) .

  •[START_REF] Függer | Unfaithful glitch propagation in existing binary circuit models[END_REF] Függer, Nowak, Schmid. Unfaithful glitch propagation in existing binary circuit models.

IEEE Transactions on Computers 65.3 (2015): 964-978, and [17] Függer, Nowak, Schmid. Unfaithful glitch propagation in existing binary circuit models. In IEEE 19th International Symposium on Asynchronous Circuits and Systems (ASYNC), pages 191-199, 2013.

1 ≤ s 2 for two signals s 1 , s 2 , if the relation holds point-wise. Similarly functions like |s 1 -s 2 | that denote the inequality signal of s 1 , s 2 , are defined point-wise.

  Let s 1 and s 2 be signals such that s 1 ≤ s 2 and let C be a channel. Then, C is monotone in the sense that f

	As a first result, monotonicity of unbounded single-history channels is established via:
	Lemma 32 ([18]).

Table 3 . 1 :

 31 .1. Encoding the ring latch states from thermometer encoded values to BRGC encoded values. The example shows the case for a ring of size n = 8 with n -1 latches and the coarse counter.

		ring latch states (thermometer encoded)	BRGC encoded	counts
	0	1	2	3	4	5	6	0	1	2	#1s #0s
	0

  • [120] Charron-Bost, Függer, Nowak. Multidimensional asymptotic consensus in dynamic networks. CoRR, abs/1611.02496, 2016, and [121] Függer, Nowak. Fast multidimensional asymptotic and approximate consensus. In 32nd International Symposium on Distributed Computing (DISC), Leibniz International Proceedings in Informatics (LIPIcs), pages 27:1-27:15, 2018.

Table 4 .

 4 1: Comparison of four algorithms for asymptotic and approximate consensus in non-split network models. From[START_REF] Függer | Fast multidimensional asymptotic and approximate consensus[END_REF].

		MidExtremes ApproachExtreme Centroid	MH	VG
	output contraction ratio	7 8	31 32	d d+1	d 1 2	1 -1 n
	local TIME	O(n 2 d)	O(nd)	#P-hard O(nd) O(nd)
	coordinate-free	yes	yes	yes	no	yes

  The generator function g(x, t) describes the generation (if positive) or consumption rate (if negative) of the substance at position x and time t. Its unit is [(1/m 3 )/s] = [1/(m 3 s)]. We use the common notation ∇ = ∂ ∂x ; in our case for dimension one. The continuity equation relates the above quantities by

	∂ ∂t	c(x, t) + ∇ • J(x, t) = g(x, t) .	(4.15)

  [START_REF] Cho | Distributed computation with continual population growth[END_REF] Da-Jung Cho, Matthias Függer, Corbin Hopper, Manish Kushwaha, Thomas Nowak, Quentin Soubeyran. Distributed computation with continual population growth. In Hagit Attiya, editor, 34th International Symposium on Distributed Computing (DISC), volume 179 of Leibniz International Proceedings in Informatics (LIPIcs), pages 7:1-7:17, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum für Informatik.

A glitch is a short pulse that typically occurs as unintended transient behavior.

Any state-holding gate with at least two stable internal states was shown to contain a third metastable internal state in which it may reside for an unbounded time[START_REF] Marino | General theory of metastable operation[END_REF].

Definitions of correct and faulty have to be adapted to correct and faulty within a certain time interval. The same holds for the definition of an algorithm solving fault-tolerant distributed pulse generation.

We use the notation δ∞ since δ(∞) = δ∞. While this may seem heavy in notation for a constant delay channel, we will follow this scheme also for more refined channels. We call δ∞ the long-term delay since it is the delay for a channel that has not seen an input for increasingly long durations.

While one may argue that such a continuous model neglects quantum effects with discrete energy potentials, note that these potentials are steady-state solutions. A more severe limitation, is the lack of probabilistic effects in our model. We will discuss probabilistic, or in this case, nondeterministic, extensions in Section 2.10, however, a relation to quantum effects is open at this point.

The duty cycle of a periodic signal is the ratio of high-time and period. For a non-periodic pulse train, we define the duty cycle of pulse i ≥ 1 as the ratio of the high-time of the i th cycle and its total length.

For ease of presentation the clock signal is supposed to be internal to the synchronizer.

The authors call a message adversary, i.e., a set of allowed communication schedules, closed if for each sequence that is not in the set there exists a prefix with all extensions not being in the set.

The statement holds for the algorithm as it is specified. However, one can show that the midpoint algorithm can be rewritten into an algorithm with a positive parameter that produces the same outputs.

Such ratios are sometimes called rates, including in own previous work. We will use the term ratio in this writeup, since small ratios mean fast contraction, which is counterintuitive with the notation of a rate.

In fact the validity condition is a condition on the decided value or the limit and not on a single step. However, one can show that the output values may also lie outside of the convex hull of initial values after arbitrarily many steps and not just a single step.

The paper also studied synchronous systems. Since for these exact consensus is solvable if n > 3f , the valency contraction ratio is 0. An interesting question, however, is lower bounds for round-by-round valency contraction ratios.

The concentration of the substance within the incompressible medium, i.e., the density of the substance, however, can vary.

Not to be confused with the units of S.

Analogous considerations hold for dP/dt.

Acknowledgements

Further, assume the setup shown in Figure 3.26 with N cells. We define cell access and validity of a cell as in [START_REF] Bund | Synchronizer-free digital link controller[END_REF]:

(A1) The receiver's continuous address pointer is p r (t) = c r (t).

(A2) The sender's continuous address pointer is p s (t) = c s (t) + N/2.

(A3) The receiver's discrete address pointer is P r (t) = p r (t) mod N = C r (t) mod N . We say the receiver (starts to) access cell ∈ {0, . . . , N -1} at time t if P r (t) = .

(A4) The sender's discrete address pointer is P s (t) = p s (t) mod N = C s (t) + N/2 mod N . We say the sender (starts to) access cell ∈ {0, . . . , N -1} at time t if P s (t) = .

(A5) To account for non-zero access of cells, we assume that an access has a duration τ s for the sender and τ r for the receiver.

(A6) On initialization, cells ∈ {0, . . . , N/2 -1} are valid, and all other cells are invalid.

(A7) If the sender accesses an invalid cell at time t, the cell becomes valid at time t + τ s until it is invalidated by the receiver. If the reader accesses a valid cell at time t, it becomes invalid at time t + τ r until it becomes valid by the sender.

Linked to each cell , there is a full/empty flag F . Its value at time t is:

(F1) 1 if cell is valid at time t, (F2) 0 if cell is invalid at time t, (F3) arbitrary within B M , otherwise.

The specification of the controller-oscillator interface is as follows. With T ctr > 0 being an upper bound on the controller latency: (L1) If the controller output sets md s to b ∈ B during [t -T ctr , t], then md s (t) = b. An analogous statement holds for md s .

(L2) In all other cases md s and md r are arbitrary within B M .

Problem. We are now in the position to state the problem of a correct link controller in our sender-receiver setting.

Definition 83 (from [START_REF] Bund | Synchronizer-free digital link controller[END_REF]). A link is correct if the following holds for all executions:

(P1) No underrun: the receiver accesses only valid cells.

(P2) No overflow: the sender accesses only invalid cells.

Definition 84 (from [START_REF] Bund | Synchronizer-free digital link controller[END_REF]). Controller Ctrl is correct if it computes the signals md s and md r out of the inputs (F ) ∈{0,...,N -1} so that the link is correct. • Convergence. Each sequence of process outputs (x i (k)) k≥1 converges.

• Agreement. If the output sequences of two processes converge, they converge to the same limit.

• Validity. If the output sequence of a process converges, then its limit is in the convex hull of initial values.

The above definition is analogous to the scalar case, except that we generalized the interval of initial values to the convex hull of initial values in the Validity condition.

Analogously, we say, an algorithm achieves ε-approximate (terminating) consensus with the communication sequence G = (G(k)) k≥1 if in each execution of the algorithm from a global initial state (that represents valid inputs to consensus problems) with communication sequence G, all of the following hold:

• Termination. All processes eventually decide.

• ε-Agreement. If two processes i and j decide on values v i and v j , then ||v i -v j || ≤ ε.

• Validity. Any value decided by a process is within the convex hull of initial values.

Here, ε-Agreement has been generalized to the norm on V , and Validity to the convex hull of initial values.

A note on a priori bounded versus unbounded domains. In the one-dimensional case, we assumed that initial values are from a domain that is a priori bounded, in our case [0, 1]. Note that this is central for solving ε-approximate consensus, however, not for solving asymptotic consensus. For the latter, all our negative and positive results also hold for values in unbounded domain R. An analogous statement holds for the higher-dimensional case: we will thus assume initial values to be from [0, 1] d when discussing ε-approximate consensus.

Solutions to Consensus Problems

We have already mentioned some of the related work on approximate and asymptotic consensus when discussing dynamic networks and consensus problems. Let us briefly sketch the difficulty in solving consensus problems at the example of two publications.

We start with network models that comprise only bidirectional, strongly connected graphs. Kuhn et al. [START_REF] Kuhn | Distributed computation in dynamic networks[END_REF] showed the following result (rephrased in our model):

Theorem 100 (from [START_REF] Kuhn | Distributed computation in dynamic networks[END_REF]). In a network model with only (bidirectional) strongly connected communication graphs, exact consensus is solvable in n -1 rounds.

Proof idea. The algorithm solving exact consensus relays messages during n -1 rounds. From the fact that graphs are strongly connected, any node i that has not yet received a value from another node j must be connected via a path from i to j. Along this path there must be two neighbors that differ in the fact whether they have received j's value. Consequently this node must receive j's value. This can happen at most n -1 times. This promising result is complemented with a result by Santoro and Widmayer [START_REF] Santoro | Time is not a healer[END_REF] who showed that (rephrased in our model) in a network model with graphs that are almost complete and connected but not strongly connected (and not bidirectional), exact consensus is not solvable: Theorem 101 (from [START_REF] Santoro | Time is not a healer[END_REF]). In a network model that is the set of all communication graphs with n ≥ 2 nodes, where at most one node has outgoing links to a subset of nodes, but all other nodes have outgoing links to all other nodes, exact consensus is not solvable.

In particular, such a network model results from an adversary that is allowed to remove up to n -1 messages from a fully connected communication graph in each round [START_REF] Santoro | Time is not a healer[END_REF].

Coulouma et al. [START_REF] Coulouma | A characterization of oblivious message adversaries for which consensus is solvable[END_REF] characterized the network models in which exact consensus is solvable; with the above two theorems showing up as special cases.

Approximate Consensus

As previously discussed, for many applications exact consensus in fact is an overkill -raising hopes for less strict conditions on the network model for solvability. Indeed, in [START_REF] Charron-Bost | Approximate consensus in highly dynamic networks: The role of averaging algorithms[END_REF] we proved the following characterization of network models in which approximate consensus is solvable under quite weak conditions: Theorem 102 ( [START_REF] Charron-Bost | Approximate consensus in highly dynamic networks: The role of averaging algorithms[END_REF]). Approximate consensus is solvable in network model N , if and only if N contains only rooted communication graphs.

We sketch the proof outline that we gave in [START_REF] Charron-Bost | Fast, robust, quantizable approximate consensus[END_REF] in the following. For that purpose, say an algorithm is -contracting in network model N , if in all its executions within N , and all rounds

Using the fact that non-split communication graphs have common incoming neighbors for each pair of processes and thus non-empty intersections among the intervals of received values for these processes, we showed that: Theorem 103 ( [START_REF] Charron-Bost | Fast, robust, quantizable approximate consensus[END_REF]). In a network model with only non-split communication graphs, a σ-safe averaging algorithm is (1 -σ)-contracting.

For some of our results, a more conservative contraction bound was used. Observing that, for 0 < ≤ 1,

we have, that an algorithm that is -contracting in a network model, also is e -(1-) -contracting in that network model.

By repeated application of (4.4), the following bound on the time complexity can be shown for -contracting averaging algorithms: Lemma 104 ( [START_REF] Charron-Bost | Fast, robust, quantizable approximate consensus[END_REF]). For all network models N , and all -contracting averaging algorithms, with 0 < < 1, the algorithm solves approximate consensus in N . It achieves ε-agreement in

rounds.

The inequality follows from the observation before. From the observations in Example 97, we further have: Lemma 105 ( [START_REF] Charron-Bost | Fast, robust, quantizable approximate consensus[END_REF]). In any network model with communication graphs with n processes, the equalneighbor averaging algorithm and the mean-value averaging algorithm are 1 n -safe. The midpoint algorithm is 1 2 -safe.

Putting everything together, we thus obtain:

Theorem 106 ( [START_REF] Charron-Bost | Approximate consensus in highly dynamic networks: The role of averaging algorithms[END_REF]). In a non-split network model of n processes, every averaging algorithm that is σ-safe, achieves ε-consensus in

rounds. In particular:

• The equal neighbor averaging algorithm and the equal value averaging algorithm achieve ε-consensus in n log e 1 ε rounds.

• The midpoint algorithm achieves ε-consensus in log 2 1 ε rounds.

The case n = 2. There is an interesting algorithmic solution for n = 2 processes [START_REF] Charron-Bost | Fast, robust, quantizable approximate consensus[END_REF]: the jumping algorithm. Consider the algorithm for process i ∈ [2] that sets:

where j = i if i receives a message not only from itself, and j = i, otherwise. While, this algorithm only has parameter 1 3 , and is only 1 3 -safe, one can directly show that it is 1 3 -contracting, i.e.,

for rounds k ∈ N + .

Analysis of macro-rounds. While Theorem 106 is promising for non-split network models, such network models may seem highly limited in their range of application. We will next show that this is not the case, when collapsing rounds into larger blocks of rounds -so called, macro-rounds.

First observe, that the output sequence of an averaging algorithm is generated by successive multiplication of the the vector of initial values with adjacency matrices of the communication graphs, whose weights correspond to the weights assigned by the algorithm. Thus,

where s(k) ∈ R n×1 and W (k) ∈ R n×n with entries w ji (k) as defined in (4.2).

This representation, e.g., has been used in a different proof strategy [START_REF] Charron-Bost | Approximate consensus in highly dynamic networks: The role of averaging algorithms[END_REF] as discussed in this chapter to establish bounds for averaging algorithms with positive parameters. Here, we stress on another point that has been used in [START_REF] Charron-Bost | Fast, robust, quantizable approximate consensus[END_REF] and follow-up work to obtain effective time complexity bounds for averaging algorithms: one may regroup the matrices into blocks of common sizes K ∈ N + . For k mod K ≡ 0, we thus obtain

with matrices W ( ) ∈ R n×n as the respective products of matrices. Along this lines, following [START_REF] Charron-Bost | Fast, robust, quantizable approximate consensus[END_REF], we say a network model N is K-non-split, for K ∈ N + , if all products of K communication graphs from N are non-split. By assessing that the parameters of this hypothetical algorithm shrinks with the power K due to the matrix product, one obtains: Theorem 107 ( [START_REF] Charron-Bost | Approximate consensus in highly dynamic networks: The role of averaging algorithms[END_REF]). Let N be a K-non-split network model with n processes. Then, an averaging algorithm with parameter > 0 achieves ε-consensus in

We may now apply Theorem 92 on page 77 and obtain that if we choose blocks of length K = n -1 in a rooted network model with n processes, the communication graphs W ( ) are non-split. Accordingly: Theorem 108 ( [START_REF] Charron-Bost | Approximate consensus in highly dynamic networks: The role of averaging algorithms[END_REF]). In a rooted network model with n processes, every averaging algorithm with parameter > 0 achieves ε-consensus in

rounds. For the equal neighbor averaging algorithm, with

Theorem 108 is restricted to averaging algorithms with a positive parameter, and thus a priori cannot be directly applied to the midpoint algorithm that performed well in non-split network models. This is due to the fact that the forming of blocks in (4.7) was performed at matrix-level, resulting in lower bounds on product matrix entries. By contrast, if we multiply these blocks including the initial vector, the fact that an algorithm is σ-safe can be applied to prove bounds instead. Indeed one obtains an analog statement as in Theorem 107 for safety: Theorem 109 ( [START_REF] Charron-Bost | Fast, robust, quantizable approximate consensus[END_REF]). Let N be a K-non-split network model with n processes. Then, a σ-safe algorithm is (1 -σ K )-contracting over each block of length K.

While Theorem 109 may be applied to the midpoint algorithm obtaining a better time complexity bound, we may still improve the bound by considering macro-rounds without averaging.

Theorem 121 ([119]). The valency contraction ratio of any asymptotic consensus algorithm for

The bound is matched by the output contraction ratio of 1/3 for the jumping algorithm [START_REF] Charron-Bost | Fast, robust, quantizable approximate consensus[END_REF] discussed in Section 4.5.1. Applying Lemma 120, we obtain that the valency contraction ratio is tight.

Nodes with no incoming messages. Choose an arbitrary communication graph G with n nodes and let the set nonlistening(G) be the set of n communication graphs obtained from G by removing the incoming links to a node i, except its self-loop, for each node i. In each such graph, node i does not receive messages. All shown graphs are rooted; which is not necessarily the case for all G. Self-loops are shown.

We proved the following result for network models that are supersets of nonlistening(G), for arbitrary communication graphs G: Theorem 122 ( [START_REF] Függer | Tight bounds for asymptotic and approximate consensus[END_REF]). Let G be a communication graph with n ≥ 3 nodes The valency contraction ratio of any asymptotic consensus algorithm in a network model that includes all graphs from nonlistening(G) is at least 1/2. First observe that the theorem holds for all G, including ones that are not rooted, or whose set nonlistening(G) contains non-rooted communication graphs. While the theorem's bound is also true for these, the valency contraction ratio is 1 in this case, since asymptotic consensus cannot be solved for non-rooted network models [START_REF] Charron-Bost | Approximate consensus in highly dynamic networks: The role of averaging algorithms[END_REF]; see also Theorem 102 on page 84.

Further, setting G = K n , i.e., to the complete graph with n nodes, Theorem 122 also shows that the network model of all non-split communication graphs has a valency contraction ratio of at least 1/2, since this network model is a superset of nonlistening(K n ). The lower bound of 1/2 is met for this network model by the midpoint algorithm; see Theorem 112 on page 89 7 and the application of Lemma 120 on page 96.

Rooted network models. Both previous lower bounds are derived by round-by-round considerations on the valency. While these bounds are met by algorithms for non-split network models, (amortized) algorithms for rooted network models provide only guaranteed contraction per n -1 rounds. In search of matching lower bounds for such algorithms, we thus studied valency contraction along communication sequences instead of single rounds. In [START_REF] Függer | Tight bounds for asymptotic and approximate consensus[END_REF] we showed that with this strategy one can show that the midpoint algorithm with a contraction of n-1 1/2 in rooted network 7 Precisely, the round-by-round output contraction ratio bound is used.

we will see that this language is also well suited to describe synthetic biological circuits at a higher level of abstraction than CRNs, while still remaining close to CRNs.

Following [START_REF] Martin | Programming in vlsi: From communicating processes to delay-insensitive circuits[END_REF] and the presentation in [START_REF] Függer | Digital circuit design for biological and silicon computers[END_REF], a (simplified) CHP circuit is a term among:

• A variable assignment. Let x be a variable from some alphabet and b be a Boolean expression on 0, 1, and variable names. A variable assignment is of the form Further, a circuit comprises of an initial Boolean assignment of all used variables. An execution of a circuit is a timed sequence of variable assignments, similarly to the circuit execution from Chapter 1, where:

• A variable assignment leads to the specified assignment (after some time).

• A guard leads to this term waiting until the guard becomes true.

• Sequential and parallel composition are sequential and aprallel execution of the respective terms.

• A repeat execution is the repeated execution of this term.

Similarly as discussed in Chapter 2, the timing of such executions is specified via delay models. While Martin considered asynchronous executions for CHP in [START_REF] Martin | Programming in vlsi: From communicating processes to delay-insensitive circuits[END_REF], more constrained delay models may be used instead. Martin [START_REF] Martin | Compiling communicating processes into delay-insensitive VLSI circuits[END_REF][START_REF] Martin | Synthesis of asynchronous VLSI circuits[END_REF] studied the automated translation of CHP circuits into ones that only comprise of production rules, and that behave equivalently.

Distributed Gates

Along the idea to use the majority consensus as an amplifier for noisy/unclean signals, leading to their regeneration, we defined dual-rail signals and gates with dual-rail inputs and outputs in [START_REF] Cho | Distributed computation with continual population growth[END_REF] as follows. Dual-rail encoded signals are used in clockless circuits to allow the receiver to distinguish old from new data [START_REF] Myers | Asynchronous Circuit Design[END_REF][START_REF] Sparsø | Principles asynchronous circuit design[END_REF].

A signal is defined as in Section 1.2 as a potentially infinite sequence of events. However, taking into account non-binary/intermediate values that play an important role in microbiological circuits, we allow events values to be from {0, 1, M}, where M denotes the unstable/metastable value.

A port is from a finite alphabet Σ = {X, Y, . . . }. Each port X is assigned a signal x; and we use x(t) for the value of x at time t. For each signal X, there are two species X 0 and X 1 , making up the two rails of the dual-rail signal; e.g., high numbers of X 0 and low numbers of X 1 at time t encode x(t) = 0; and vice versa for x(t) = 1. We use x(t) = M for the case where neither is the case. Formally: Definition 134 (Dual-rail encoding, from [START_REF] Cho | Distributed computation with continual population growth[END_REF]). Let X 0 , X 1 be species of a dual-rail encoding of signal X. Let X(t) = X 0 (t) + X 1 (t). For n, ∆ ∈ N, we say signal X is initially (n, ∆)-correct with value x ∈ {0, 1} if X(0) ≥ n and

The initial gap of signal X is X x (0) -X ¬x (0).

One observes that the initial gap of an initially (n, ∆)-correct signal is bounded by

Equipped with this encoding of signals, we defined a protocol for a birth system that computes a Boolean function; in this case of a Nand gate. Other Boolean functions are computable along the same lines.

Definition 135 (Nand gate implementation, from [START_REF] Cho | Distributed computation with continual population growth[END_REF]). The implementation of a Nand gate with input signals A, B and output signal Y is as a protocol for a birth system with 1. input species I = {A 0 , A 1 , B 0 , B 1 }, 2. output species O = {Y 0 , Y 1 } with initial counts 0, and 3. no internal species. For all a, b ∈ {0, 1} and y = ¬(a ∧ b), the protocol contains a reaction

where α > 0 is the gate's reaction rate constant. Additionally, all species have duplication reactions with a reaction rate constant γ > 0.

Based on a reduction to Yule processes, we proved our main result on the gate's behavior which is as follows: Ce travail se concentre sur trois aspects : (i) le calcul dans des conditions où les effets temporels ne peuvent être négligés, (ii) lorsque les signaux non binaires jouent un rôle central, et (iii) le calcul dans une infrastructure changeante, i.e., les réseaux dynamiques. Bien que la majeure partie de ce travail soit consacrée aux implémentations en silicium, les circuits microbiologiques sont abordés dans les perspectives.

Title : Computing at the border of abstractions: the power of timed, non-binary, distributed circuits Keywords : models of computation, circuits, distributed computing, timing, metastability, robustness Abstract : The design and analysis of low-level computing devices directly implemented in hardware is commonly based on finite state machine models. In this work we review some of the assumptions made in these designs and discuss techniques for the cases where the assumptions fail to hold.

The work concentrates on three such aspects: (i) computing under conditions where low-level timing effects cannot be neglected, (ii) when nonbinary signals play a central role, and (iii) computing within a changing infrastructure, i.e., dynamic networks. While most of this work is devoted to implementations in silicon, microbiological circuits are discussed in the outlook.