One of us (MJU) [1] has shown experimentally that it is possible to put any logic flip-flop into a metastable state by careful choice of input switching pulse amplitude and duration. The process is akin to balancing a pencil on its point; any error in the initial setting with respect to the unstable fixed point is then subject to exponential growth. Surprisingly, the noise inherent in the flip-flop circuitry does not affect the statistics of the settling out from the metastable state which is thus induced. This is for the following two reasons; first, the noise is of zero mean when averaged over time, and second, the effect of such added noise is to perturb the initial conditions and therefore the entry point to the metastable state. Usually the process determining the initial condition is similarly noiselike, and so the circuit noise simply adds to this uncertainty, leaving the probability of entering metastability unaffected. In fact, the circuit noise over time causes as many additional entries to metastability as it prevents. That said, the addition of noise to the initial setting error can have two independent effects. First, it can tip the balance so that the flip-flop settles into the opposite state. Second, in any isolated instance, it will increase or decrease the settling time. Thus a random distribution of initial states which grows exponentially with time results in the circuit settling randomly into one or other of its two stable states. Flip-flops are composed of a number of inverting gates accompanied by pairs of inverting buffers. The buffers come in pairs because it is necessary to preserve the inverting character of the gates. Each gate or buffer has an associated time constant. Simple flip-flops have two associated poles, and in a standard technology both these poles have the same time constants. However, flip-flops made up from standard double-buffered gates will have six poles. This has important consequences for the dynamics of gate settling in the metastable region, as we shall see.
In general, flip-flops consist of non-inverting amplifiers with positive feedback. Thus the switching time depends on the transfer function pole with the largest positive real part in a linearised approximation. Experimentally, [1], the flip-flops made up from double-buffered gates display between 4 and 7 cycles of oscillation before settling randomly. The hypothesis is that this is due to the s-shaped transfer function resulting in the positive gain being non-linear and settling so that there are a pair of poles on the imaginary axis which determine the gain as far as the real positive pole associated with the notional linear transfer function (a chord on the s-shaped characteristic) is concerned. The remaining three poles are of no consequence, as far as settling from metastability is concerned.
The consequence of all this is that the flip-flop output stays
undefined, or oscillatory, in terms of its logic state, for many
time constants. One estimates this number of time constants by
postulating that the unstable solution has to grow from the
initial
random
level (which can be arbitrarily small even in the
presence of significant noise), to the logic level,
exponentially. In a gate engineered to operate at a repetition
speed of fHz the noise power associated with the gate input is
NkTf where N is the noise factor, k Boltzmann's constant,
and T the absolute temperature. Assuming a best design of noise
factor of 2, room temperature operation at 300K, and a design
impedance level for the terminated
interconnecting transmission lines of 50
, this gives us
a
voltage noise level on the gate input of about 650
picovolts/Hz
.
Thus at a conservative switching speed f of 100MHz,
one has an uncertainty of about 6.5 microvolts on the gate input.
The typical logic level reached will be about 3.3 volts say, and
so the ratio of logic level to noise level will be about
.
In the case that the initial setting error is comparable with the
inherent gate noise, it will take 
times the time constant
associated with the unstable pole for the gate to settle.
Clearly, if the initial setting error is significantly less than this
noise level then the final state of the gate is randomly chosen
by the arbiter. If however the setting error is greater than the
noise level, the added noise will not usually result in an error
of judgement. We should assume noise whose amplitude is
distributed according to a Gaussian distribution; then given the
setting error it is possible to calculate the statistics of
erroneous arbitrations.
Now typically, we can hypothesize that when strongly driven ( i.e. not deliberately placed into a metastable state) the flip flop transition time will be of the order of a single time constant associated with the buffers. Again we can hypothesize that at maximum operating speed, the flip flop is set and reset over a time interval no longer than about five times this time constant. This is because we assume equal ramp up and ramp down times, and a total transition time comparable with the total static time in the fastest gate cycle. Thus entry into metastability will interfere with the following three transitions of the flip flop. Comparing this time with the 13 time constants it takes a gate that is initially set within the noise to settle, it is clear that delays in switching due to metastability are at least as important as errors due to added noise in describing the reliability of operation.
Now consider arbitration circuits. Functionally, these cannot be engineered to behave any faster or better than their component flip-flops. The purpose of an arbitration circuit is to impose branching on the machine trajectory depending on which of two inputs changes first in time. Again, considering a maximum slew rate for the input, if the inputs change simultaneously within the noise criterion referred to earlier, then the output of the arbiter will be quite unpredictable and indeterminate, not related to the input request values, and possibly metastable, resulting in the arbiter being withdrawn from effective service for about three logic periods on average.
We hypothesize that the arbiter accepts inputs which slew up over
1/5 of a logic period, remain stable for 3/5 of a logic period,
the slew down over the remaining 1/5 of a logic period. Thus to
remain within the noise limitations referred to above, both input
transitions must be timed to within 
of a logic
period. There will thus be about 
probability
per
arbitration request of error, or indeterminate output, or
metastability, in an asynchronous parallel machine where we
assume all inputs to the arbiter change at a uniformly
distributed random time within a hypothetical clock period.
We now have to estimate the number of such arbitration requests per second. This will depend directly on the degree of parallelism in the machine, the machine logic speed, and the architecture. It is clearly possible to design a machine having minimal requests on arbiters; we suggest that this will necessarily involve a trade off in potential speed.
It has been suggested that it is possible to take steps to avoid arbitration errors and metastability problems. [3]. However, to the authors' knowledge, all such systems rely on concepts such as the stretchable clock, which presupposes the arrival times are under the control of the system, combined with metastability detectors, which presupposes that a metastable event has occurred which it is desired to avoid in future. We contend that all such methods sacrifice the speed and advantages of parallel computation, by essentially imposing a serial nature on some or all of the machine operation. At the error rate postulated here, such an overhead will be significant.
To conclude this section, if the asynchronous parallel machine
has P parallel paths involving arbitrations which are requested
at a probability p per logic period, and the basic machine speed
which is set by the maximum repetition rate of the logic elements, is
fHz, then we propose that there will be at least 
arbitration uncertainties or errors per second. Nothing can be said
about the quantities P and p without considering the specific
architecture and problem, but we may estimate f to be of the order
or greater than 
Hz.