Optimal Short-Circuit Resilient Formulas

We consider fault-tolerant boolean formulas in which the output of a faulty gate is short- circuited to one of the gate’s inputs. A recent result by Kalai et al. [FOCS 2012] converts any boolean formula into a resilient formula of polynomial size that works correctly if less than a fraction 1/6 of the gates (on every input-to-output path) are faulty. We improve the result of Kalai et al., and show how to efficiently fortify any Boolean formula against a fraction 1/5 of short-circuit gates per path, with only a polynomial blowup in size. We additionally show that it is impossible to obtain formulas with higher resilience and sub-exponential growth in size.

Towards our results, we consider interactive coding schemes when noiseless feedback is present; these produce resilient Boolean formulas via a Karchmer-Wigderson relation. We develop a coding scheme that resists up to a fraction 1/5 of corrupted transmissions in each direction of the interactive channel. We further show that such a level of noise is maximal for coding schemes with sub-exponential blowup in communication. Our coding scheme takes a surprising inspiration from Blockchain technology.

Joint work with Mark Braverman, Klim Efremenko, and Michael A. Yitayew

Reliable and secure communication in Globally Asynchronous Locally Synchronous (GALS) systems

The intensive use of portable devices such as smart phones and wearable medical devices has heightened the need to protect the sensitive information processed and stored on these devices. The weakest points, in terms of security, are the intra-communication links within the device, which are exposed to fault injection attacks. In Globally Asynchronous Locally Synchronous (GALS) systems, communication over these parallel point-to-point links is asynchronous. An attacker can tamper with the transmitted data by changing the propagation time of the signals and/or by injecting glitches which are additional pulses in between the transmitted signals.

It is impossible to prevent attacks, but it is possible to increase the hardware’s immunity by adding countermeasures that can detect malfunctioning with high probability, or make the circuit fault tolerant, i.e., enable it to function correctly in the presence of faults.

In this talk we'll present new methods for designing reliable and secure communication across asynchronous channels that suffer from an arbitrary number of skews and glitches.

Embracing Uncertainty - What We Can, Cannot, and Would Like to Do

When Facing Metastability

In recent years, we've been studying to what extent metastability can be handled without resorting to synchronizers or analog design. The main goal is to avoid synchronizer delay, bearing the promise of faster - and thus more accurate - mixed signal control loops for tasks requiring a very small reaction time, e.g. adaptive voltage control or clock synchronization. In this paradigm, metastability is treated as a third state of the "digital" logic, which can be contained using logical masking. An additional useful tool are masking registers; in a nutshell, these use high- or low-threshold inverters at their output to effectively transform metastability into late transitions. I will present an overview of both positive and negative results regarding such circuits, highlighting the utility as well as known limitations of these techniques. I will also touch some open questions and future research.

Presentation slides: PPT.

Asynchronous Signalling Processes

A model of processes that interact via asynchronous wires carrying Boolean signals is presented. In this model, modules, called processes, can be made arbitrarily complex, can maintain local memory and can have an arbitrary number of inputs and outputs. A variety of circuit models can be represented by networks of signalling processes. It is shown that in a network of signalling processes consisting solely of single-ouput processes and forks, every module is an eventual C element. Consequently, the computational power of such a network is severely limited. This establishes that the celebrated C-element property of DI circuits follows solely from the fact that single output modules communicate over stable asynchronous wires. Conversely, it is shown that any Boolean function can be implemented using four- input/two-output processes where every process is either one gate (single output) or a pair of gates (two output).

This is joint work with Rajit Manohar from Yale.

Presentation slides: PDF.

Digital Modeling of Asynchronous Integrated Circuits

We present some of the results and open challenges in the development of a purely digital model for asynchronous circuits, which shall enables accurate and fast dynamic timing analysis and formal verification of such designs. In our research, we primarily consider advanced delay models, where the input-to-output delays depend on previous inputs also. Such models shall not only be accurate, but also realistic (we coined the term faithful for their conjunction), in the sense that the behavior of circuits described in the model is exactly, i.e., within the modeling accuracy, the same as the behavior of the corresponding real circuit. We proved that all the existing standard delay models, including pure and inertial delays, are not faithful, and proposed the involution delay model as the only faithful alternative known so far. In this talk, we will present an overview of our results and report on some of the problems we are currently working on in this area.

Presentation slides: PDF.

Stacked Asynchronous Circuits

In this talk we will look at digital circuits from the viewpoint of electrical circuit theory, i.e. as loads to power sources. Such circuits, especially when they are asynchronous can be seen as voltage controlled oscillators. Their switching behaviour, including their operating frequency is modulated by the supply voltage. Interestingly, in the reverse direction if they are driven by external event sources, their switching frequency determines their inherent impedance which itself makes them ideal potentiometers or voltage dividers. Such circuits can be stacked like non-linear resistors in series and parallel, and lend themselves to interesting theoretical and practical results, such as RC circuits with hyperbolic capacitor discharges and designs of dynamic frequency mirrors.

Presentation slides: PDF.