Research report 2017 - Max Planck Institute for Informatics
Containing Metastability or: The Art of Choosing between two Equal Bales of Hay
Lenzen, Christoph.; Wiederhake, Ben
Theorie verteilter und eingebetteter Systeme / D1 – Algorithmen und Komplexität
SummaryUnlike Buridan’s ass, horses do not starve to death when placing them exactly between two identical bales of hay. But what happens, if the horse does not see whether there’s hay to its left and/or right? What if we don’t know either, and if we possibly can’t see where the horse goes? Can we reliably decide whether the horse starves? Interestingly, answers to such questions become highly relevant when considering so-called metastability in circuits. This article explains these terms, their connection, and why it is important to know whether the horse dies or not.