hide
Free keywords:
Computer Science, Distributed, Parallel, and Cluster Computing, cs.DC
Abstract:
Communication across unsynchronized clock domains is inherently vulnerable to
metastable upsets; no digital circuit can deterministically avoid, resolve, or
detect metastability (Marino, 1981). Traditionally, a possibly metastable input
is stored in synchronizers, decreasing the odds of maintained metastability
over time. This approach costs time, and does not guarantee success.
We propose a fundamentally different approach: It is possible to
\emph{contain} metastability by logical masking, so that it cannot infect the
entire circuit. This technique guarantees a limited degree of metastability
in---and uncertainty about---the output. We present a synchronizer-free,
fault-tolerant clock synchronization algorithm as application, synchronizing
clock domains and thus enabling metastability-free communication.
At the heart of our approach lies a model for metastability in synchronous
clocked digital circuits. Metastability is propagated in a worst-case fashion,
allowing to derive deterministic guarantees, without and unlike synchronizers.
The proposed model permits positive results while at the same time reproducing
established impossibility results regarding avoidance, resolution, and
detection of metastability. Furthermore, we fully classify which functions can
be computed by synchronous circuits with standard registers, and show that
masking registers are computationally strictly more powerful.
