×

A new explanation of the glitch phenomenon. (English) Zbl 0721.94028

Summary: We consider a discrete model for asynchronous circuits and show that, under very mild restrictions, this model excludes the existence of glitch-free arbiters. This result contradicts a long standing conjecture that the nonexistence of glitch-free arbiters is due to the continuous nature of such circuits.

MSC:

94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
68Q05 Models of computation (Turing machines, etc.) (MSC2010)

Software:

UNITY
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Black, D.: On the existence of delay-insensitive fair arbiters: trace theory and its limitations. Distrib. Comput.,1, 205–225 (1986) · Zbl 0643.94041
[2] Chandy, K., Misra, J.: How processes learn. Distrib. Comput.1, 40–52 (1986) · Zbl 0602.68026
[3] Chandy, K., Misra, J.: Parallel program design: A foundation, pp. 89–94. Reading, MA: Addison Wesley 1988 · Zbl 0717.68034
[4] Chaney, T., Molnar, C.: Anomalous behavior of synchronizer and arbiter circuits. IEEE Trans. Comput. C22, 421–422 (1973)
[5] Fischer, M., Lynch, N., Patterson, M.: Impossibility of distributed consensus with one faulty process. J. ACM.32, 374–382 (1985) · Zbl 0629.68027
[6] Hurtado, M., Elliot, D.: Ambiguous behavior of logic bistable systems. Proceedings of the 13th Annual Allerton Conference on Circuit and Systems Theory, October 1975, pp. 605–611
[7] Lamport, L.: Buridan’s principle. SRI Technical Report. October 1984
[8] Marino, L.: General theory of metastable operation. IEEE Trans. Comput., C30, 107–115 (1981) · Zbl 0455.94034
[9] Martin, A.: Compiling communicating processes into delay-insensitive VLSI circuits. Distrib. Comput.1, 226–234 (1986) · Zbl 0643.94039
[10] Miller, R.: Speed independent switching circuit theory. In: Switching theory. Sequential circuits and machines, Vol. 2, Chap. 10. New York: Wiley 1965
[11] Palais, R., Lamport, L.: On the glitch phenomenon. Technical report CA-7611-0811, Massachusetts Computer Associates, Wakefield, Massachusetts, November 1976
[12] Seitz, C.: System timing. In: Mead, C., Conway, L. (eds.). Introduction to VLSI systems, Chap. 7. Reading, MA: Addison-Wesley 1980
[13] Udding, J.: A formal model for defining and classifying delay-insensitive circuits and systems. Distrib. Comput.1, 197–204 (1986)
[14] Vosbury, M.: Hazards in asynchronous sequential circuits due to unrestricted input changes. Ph. D. dissertation, Rensselaer Polytechnic Institute, Troy, New York, December 1973
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.