3 ms·
There is an interesting and important theorem from control theory that is relevant for this situation. In a paper from 1984, Leslie Lamport has called it Burida
by triska 7y ago
There is an interesting and important theorem from control theory that is relevant for this situation. In a paper from 1984, Leslie Lamport has called it Buridan's Principle and phrased it as follows:
“A discrete decision based upon an input having a continuous
range of values cannot be made within a bounded length of time.”
The paper is available from:
http://lamport.azurewebsites.net/pubs/buridan.pdf http://lamport.azurewebsites.net/pubs/buridan.pdf
It shows that under very general assumptions, a decision cannot be made in bounded time, leading to starvation (metaphorically and also literally). An example is a 4-way stop with other cars arriving at various times.
The paper's history is also very interesting:
https://lamport.azurewebsites.net/pubs/pubs.html#buridan https://lamport.azurewebsites.net/pubs/pubs.html#buridan
- marnett 7y agothanks for sharing this - this is fascinating. Admittedly I have never been exposed to Control Theory before, so I see a rabbit hole in my future.
- triska 7y agoEssentials of Control Techniques and Theory by John Billingsley is a book with many superb examples.
- gowld 7y agoNote that Lamport admitted that his result was never accepted by the scientific community. > continuous (The paper implicitly assumes non-discrete continuity) Differential-equation based hysical models are continuous. Computational systems are discrete, as long as the clock is slower than the . Lamport surely knows this, the transition duration. He waves away the empirical disproof of his claim by arguing that reality is merely a finite approximation where low probabilities runs down to zero. He even mentions this stuff in the paper, making the paper quite weird. My only guess is that he fell into the trap of forgetting that infinitesimal objects ate idealized mathematical models not physical realities.