11 ms·

One of the most interesting results I found in Leslie Lamport's papers is Buridan's Principle: A discrete decision based upon an input having a continuous rang

by triska 4y ago

One of the most interesting results I found in Leslie Lamport's papers is Buridan's Principle: A discrete decision based upon an input having a continuous range of values cannot be made within a bounded length of time. Quoting from https://lamport.azurewebsites.net/pubs/buridan.pdf https://lamport.azurewebsites.net/pubs/buridan.pdf: "The significance of Buridan’s Principle lies in its warning that decisions may, in rare circumstances, take much longer than expected. Before the problem was recognized by computer designers, some computer systems probably failed regularly (perhaps once or twice a week) because arbiters took longer than expected to reach a decision. Real accidents may occur because people cannot decide in time which of two alternative actions to take, even though either would prevent the accident. Although Buridan’s Principle implies that the possibility of such an accident cannot be eliminated, awareness of the problem could lead to methods for reducing its probability." In the accompanying notes at https://lamport.azurewebsites.net/pubs/pubs.html https://lamport.azurewebsites.net/pubs/pubs.html, Lamport states: The four reviews ranged from "This well-written paper is of major philosophical importance" to "This may be an elaborate joke." One of the other reviews was more mildly positive, and the fourth said simply "My feeling is that it is rather superficial." The paper was rejected.

l33t2328 4y ago
What about a decision like “can this wave be faithfully represented by this set of points?” Wouldn’t the Sampling Theorem give an answer in some bounded time? Is the idea that the time required to crank the algorithm can grow without bound?
- deleted 4y ago
  [deleted]
- deleted 4y ago
  [deleted]
- Kranar 4y ago
  I feel like Buridan's Principle is either poorly worded, or most likely I just completely fail to understand it. The principle says: "A discrete decision based upon an input having a continuous range of values cannot be made within a bounded length of time." But certainly I can make a discrete decision in a constant amount of time, just choose to always go left. I must therefore be missing something here. The next possibility is that a discrete decision procedure that guarantees success is not possible in an unbounded amount of time. This is more sensible and I think the idea is that there will be some kind of infinite regress. For example a donkey will starve to death if it doesn't eat in exactly 100 seconds. The donkey can choose to walk left X meters, or walk right Y meters to some food. There are certain values of X and Y where the donkey dies no matter what, if X and Y are sufficiently far away that the donkey can never get to them in 100 seconds then the donkey dies. There are also certain values of X and Y where the donkey can pick either of them and survive since the donkey can get to X or Y in well less than 100 seconds, so the donkey lives. The above two scenarios are boundary conditions of sorts, where it's fairly trivial to come to a decision, the principle is about what happens when there is a value of X where it takes almost exactly 100 seconds to get to X, (and assume way more than 100 seconds to get to Y), but in order for the donkey to come to that realization the donkey needs to spend some time thinking about it and by the time the donkey has made a decision the donkey won't have enough time to carry it out. So the donkey has to take into account not only the amount of time to get to X, but also the amount of time it takes to come to a decision to get to X, but that too takes some finite amount of time... so the donkey has to take time to come to a decision about how long it takes to come to a decision to get to X, so on so forth... and you end up with an unbounded amount of time. I could be way off here but I feel there is some subtlety in the way this principle is described that I'm missing.
  - worik 4y ago
    My guess without looking it up.... > "A discrete decision based upon an input having a continuous range of values cannot be made within a bounded length of time." "A discrete OPTIMAL decision...."
  - kevhito 4y ago
    The missing piece of "just choose to always go left" is that this is a degenerate and uninteresting case. No decision is being made. The range must be discrete and at least 2 possible values. There is nothing about optimality at all here. Even if both possible outputs are equally "optimal", there is no procedure to pick one in a finite amount of time.
    - Kranar 4y ago
      I doubt the issue has anything to do with being interesting or not. Do you know this for a fact or can give me anything to follow up on what it means for a decision to be interesting? For example if a decision procedure required the choice of chocolate or vanilla depending on the current time of day (a continuous input resulting in a discrete output), and I present an algorithm that categorically chooses chocolate regardless of what time it is, I doubt you'd turn around and claim that my algorithm is not making a decision because it always chooses chocolate. If an algorithm takes an input, continuous or discrete, discards that input and returns a constant value, that algorithm is just as "legitimate" as any other algorithm in so far as being an algorithm is concerned. It may not produce the optimal output for some given cost, but it is a formal and rigorous decision procedure that manages to output a discrete value given a continuous input in a bounded amount of time. At any rate, reading the comments when this was last posted it looks like the issue has to do with producing the optimal output in a given time frame. If an optimal discrete decision must be made in the next T seconds on the basis of a continuous input X, then there always exists some value of X that requires more than T seconds to compute. This will be true for any value of T regardless of how large.
  - andi999 4y ago
    Yes, always go left (except if you start at 1) is a solution. It is dismissed by Lamport though because the function is not continuous in 1. Somehow he believes not beiing continuous violates some principles of physics.
- gryn 4y ago
  the signal needs to have a maximal frequency for samling theorem to be aplicable. not all functions on a continious domain have that, in fact i think its the oposite most don't unless proved otherwise.
froh 4y ago
uh --- which implications does this have for driving AI? Possibly none, if the acceptance criterion for AI is: "it kills fewer people than humans would. possibly others, but fewer overall." ?
- Afton 4y ago
  None, unless you think that people are somehow able to side-step this problem in a way that a computer can't mimic.
  - kevhito 4y ago
    The paper specifically details several situations in which humans are the ones making the decision, and the result is the same. There is no bounded-time decision procedure that can take continuous (i.e. physical) inputs and render a discrete decision.
- charcircuit 4y ago
  Driving AI doesn't require continuous input variables. Approximations are good enough in the real world.
  - kevhito 4y ago
    What do you mean? All the inputs are continuous: light sensors, LIDAR, infra-red, inputs from mechanical sensors from the driver. Sure, the sensor package's hardware/firmware/software converts these to discrete inputs before it reaches the Driving AI, but all of the Buridan's Paradox results still apply to those sensor packages. They can't perform their tasks in a finite amount of time -- either they will sometimes fail to make a decision at all, or they will render an invalid output (e.g. rather than outputting voltage corresponding to logical 0 or 1, they will go into a meta-stable or astable output mode that is not a valid output voltage).
    - charcircuit 4y ago
      >rather than outputting voltage corresponding to logical 0 or 1, they will go into a meta-stable or astable output mode that is not a valid output voltage It sounds like you could easily avoid this. You can use a microprocessor and lead in analog input on one pin and then set an output pin based off that. You will always output a valid voltage. Sensors have noise anyways so it's not a big deal if the output is slightly wrong.
EGreg 4y ago
I emailed back and forth with Leslie a lot about this, when I first read his paper. There is an earlier analysis of the same phenomenon by different people (the arbiter problem) which I discovered later. At first, I had trouble to believe it, and tried to find counterexamples, until I realized that the composition of continuous functions is continuous. I still wonder sometimes whether an infinite composition of continuous functions has to be continuous (limit of a sequence) if it represents some real world evolving process. Can it produce a discontinuity in the limit? Anyway, Buridan’s principle informs our consensus process in Intercoin Protocol[1] [2] — it is why the consensus groups are always of a bounded finite size, so we don’t approach the errors in Buridan’s priciple (I think this is also called unstable problems). 1. Beyond blockchains https://community.intercoin.org/t/intercoin-technology-consensus/ https://community.intercoin.org/t/intercoin-technology-conse... 2. Experimental improvements https://community.intercoin.org/t/experimental-improvements-for-intercoin-consensus/ https://community.intercoin.org/t/experimental-improvements-... Anyone who reads the above … I would be very interested in your feedback on our forum.
- deleted 4y ago
  [deleted]
- raegis 4y ago
  > I still wonder sometimes whether an infinite composition of continuous functions has to be continuous (limit of a sequence) ... No, as you expected. Take f(x) = x^2 on [0,1]. Then f(f(f(...f(x))) converges to g(x) = { 0, if 0 <= x < 1; 1, if x=1 }
  - EGreg 4y ago
    Right. So now the question is -- are you able to give a physical example of physical (continuous) processes which can create a discontinuous output from a continuous initial state, in a finite amount of time? I think this is a sort of Zeno's paradox...
    - juhanima 4y ago
      Tossing a coin?
grayclhn 4y ago
From skimming the paper, "continuity" seems to be a deceptively strong assumption here, and the claim "this is a physical system so it's continuous" is doing a lot of heavy lifting. Unless I'm misunderstanding the example in the first paragraph, "move towards point 1 at a constant pace" can't be represented as a continuous A_t(x) for t above some finite threshold.
- thfuran 4y ago
  Why not? How are you getting discontinuities out of constant velocity motion?
  - harerazer 4y ago
    Consider the following decision: If x < 0.5 go left at a constant speed till the hay is reached, else go right at a constant speed until the hay is reached. Then A(t,x) is clearly not continuous in x, and we can easily bound the time required to make a decision. The nuance here is that we have to somehow be able to distinguish 0.5 - eps from 0.5 for very small epsilon. Edit: on further thought, suppose we had a device which measured reasonably well. More precisely it tells us x < 0.5 if x is actually <= 0.5 - c, it tells us x >= 0.5 if x > 0.5 + c, and tells us it is unsure otherwise. We do not know c, but it is deterministic (and hopefully reasonably small). Then we can decide to go left if it tells us x < 0.5, and right if it tells us unsure or that x >= 0.5.
    - irishsultan 4y ago
      > The nuance here is that we have to somehow be able to distinguish 0.5 - eps from 0.5 for very small epsilon. If you ignore the problem then the problem indeed goes away. The need for distinguishing very small epsilon exists because of the continuity assumption, and because of the continuity assumption you can't really solve it either. > Then we can decide to go left if it tells us x < 0.5, and right if it tells us unsure or that x >= 0.5. Now you just moved the problem to deciding at which point you are unsure. As long as there is a decision to take the issue persists, it's only if you always go left (or always go right) that the issue doesn't exist.
emmelaich 4y ago
Discussed at https://news.ycombinator.com/item?id=22884831 https://news.ycombinator.com/item?id=22884831
bsedlm 4y ago
to be fair, the paper has a funny tone, like an elaborate joke would have... I feel like he may deliver a punch-line at any point before I finish reading the paper and then I'd have to choose whether to burst out laughing or not
deleted 4y ago
[deleted]
im3w1l 4y ago
I think Buridan's ass is like an inverted pendulum. There is no particular reason why it should fall either way but the slightest gust of wind or vibration will trigger a self-reinforcing process that breaks the stalemate. Now, an inverted pendulum can be stabilized with a control system, and this might be possible to relate with adversarial inputs of some system.
pontusrehula 4y ago
> Real accidents may occur because people cannot decide in time which of two alternative actions to take, even though either would prevent the accident. Reminds me of one of the Boeing 737 crashes where pilots were reading the manual but had not enough time to reach the relevant pages.
Animats 4y ago
This is a very real phenomenon. But Lamport didn't discover it. It was known a decade earlier. The classic paper is Kinniment and Wood, 1976.[1] The earliest patent in this area is from 1972.[2] It's quite difficult to do this right. Arbiters today recognize "A was first", "B was first", and "ambiguous, must retry". The system has to be prepared for rare retry delays. In theory there can be an infinite number of retries, but the odds of needing more than one retry are very low. It comes up all the time in multiport memories, where several CPUs are accessing the same memory, and there has to be an arbiter to decide who gets access access for near-simultaneous requests. Requests can be very close to simultaneous. If two CPUs with 3 GHz clocks are contending for memory access, and the clocks are not synchronized but close, about once per second they will be within 10^-19 seconds of whatever difference is most troublesome. This was a serious problem with some early multiprocessor mainframes. Early in my career we saw this happening with multiprocessor UNIVAC 1108 machines. They had an unsound arbiter, and, once in a while, every few hours, they'd botch a memory access. Early on, the software stability was so bad the OS crashed more often than the hardware did, but as the OS got better, it became clear there was a race condition at the hardware level. [1] http://async.org.uk/David.Kinniment/Research/papers/IEE1976.pdf http://async.org.uk/David.Kinniment/Research/papers/IEE1976.... [2] https://patents.google.com/patent/US3824409A/en https://patents.google.com/patent/US3824409A/en
- gradschool 4y ago
  Kinniment expands on the idea at length in [1]. Chaney is another good source on the history of arbiters [2]. Specialists in asynchronous circuit design think about arbiters a lot. Alex Yakovlev and Alain Martin have published some papers about them. [1] http://www.async.org.uk/David.Kinniment/DJKinniment-He-Who-Hesitates-is-Lost.pdf http://www.async.org.uk/David.Kinniment/DJKinniment-He-Who-H... [2] https://arl.wustl.edu/~jst/cse/260/glitchChaney.pdf https://arl.wustl.edu/~jst/cse/260/glitchChaney.pdf edit: typo
  - Animats 4y ago
    And, finally, here's a data sheet for a 74F786 4-bit asynchronous bus arbiter IC.[1] Here's the answer to the paradox of Buridan's ass[2], in a 16-pin dual inline package. It doesn't take free will. "The 74F786 is designed so that contention between two or more request signals will not glitch or display a metastable condition. In this situation an increase in the BRn to BGn tPHL may be observed. A typical 74F786 has an h = 6.6ns, t = 0.41ns and To = 5µsec." "If two or more BRn inputs are asserted at precisely the same time, one of them will be selected at random, and all BGn outputs will be held in the high state until the selection is made. This guarantees that an erroneous BGn will not be generated even though a metastable condition may occur internal to the device." So, usually, you get a win within a specified time, but sometimes it takes longer. The limit on the longest time is probabilistic, but the odds of settling increase rapidly with time, by orders of magnitude per nanosecond. In this part, we get to see a simple standalone arbiter with its own data sheet. A logic diagram is given, so you can see how this is built out of simple gates. Note that diagram can't be read as abstract logic; propagation delay matters. While the arbiter is in a metastable state, an inhibit signal is generated which prevents any output from appearing. Once the arbiter has settled, the winning output is allowed out. The gate thresholds matter. The inhibit signal doesn't turn off until there's only one clear winner. It's an old part, from 1991, because today this function is usually part of a larger function such as a CPU chip or a DRAM interface. [1] https://www.digikey.com/en/htmldatasheets/production/96092/0/0/1/74f786.html https://www.digikey.com/en/htmldatasheets/production/96092/0... [2] https://en.wikipedia.org/wiki/Buridan%27s_ass https://en.wikipedia.org/wiki/Buridan%27s_ass
zozbot234 4y ago
> A discrete decision based upon an input having a continuous range of values cannot be made within a bounded length of time. I understand that this is true for deterministic decisions. But a limited amount of randomness/noise is generally an acceptable alternative to a requirement for unbounded precision.
lisper 4y ago
Why is an analog-to-digital converters not a counterexample? For that matter, why is a comparator (a one-bit ADC) not a counterexample? Or, for that matter, a wire tied to ground? Or a 3x5 card with the word "YES" printed on it?
- kazinator 4y ago
  I think it's because these devices do not always make the correct decision between two values. Lamport's paper covers this in the interrupt example: a computer must decide whether an interrupt line is signaled or not in a finite amount of time (the next instruction). The interrupt is continuous: it passes through some halfway voltage level like 2.5 between 0 and 5, and so it can be called the wrong way. Basically the whole result is a restatement of real numbers not being computable. The discrete sample value you get from an ADC is not based on knowing the underlying real number absolutely, and then choosing the nearest value. It's a time limited process of discovering the value partially. Since the value is not partially known, it is not known whether the reported sample value is the closest one.

by triska 4y ago

l33t2328 4y ago

What about a decision like “can this wave be faithfully represented by this set of points?” Wouldn’t the Sampling Theorem give an answer in some bounded time? Is the idea that the time required to crank the algorithm can grow without bound?

deleted 4y ago
[deleted]
deleted 4y ago
[deleted]
Kranar 4y ago
I feel like Buridan's Principle is either poorly worded, or most likely I just completely fail to understand it. The principle says: "A discrete decision based upon an input having a continuous range of values cannot be made within a bounded length of time." But certainly I can make a discrete decision in a constant amount of time, just choose to always go left. I must therefore be missing something here. The next possibility is that a discrete decision procedure that guarantees success is not possible in an unbounded amount of time. This is more sensible and I think the idea is that there will be some kind of infinite regress. For example a donkey will starve to death if it doesn't eat in exactly 100 seconds. The donkey can choose to walk left X meters, or walk right Y meters to some food. There are certain values of X and Y where the donkey dies no matter what, if X and Y are sufficiently far away that the donkey can never get to them in 100 seconds then the donkey dies. There are also certain values of X and Y where the donkey can pick either of them and survive since the donkey can get to X or Y in well less than 100 seconds, so the donkey lives. The above two scenarios are boundary conditions of sorts, where it's fairly trivial to come to a decision, the principle is about what happens when there is a value of X where it takes almost exactly 100 seconds to get to X, (and assume way more than 100 seconds to get to Y), but in order for the donkey to come to that realization the donkey needs to spend some time thinking about it and by the time the donkey has made a decision the donkey won't have enough time to carry it out. So the donkey has to take into account not only the amount of time to get to X, but also the amount of time it takes to come to a decision to get to X, but that too takes some finite amount of time... so the donkey has to take time to come to a decision about how long it takes to come to a decision to get to X, so on so forth... and you end up with an unbounded amount of time. I could be way off here but I feel there is some subtlety in the way this principle is described that I'm missing.
- worik 4y ago
  My guess without looking it up.... > "A discrete decision based upon an input having a continuous range of values cannot be made within a bounded length of time." "A discrete OPTIMAL decision...."
- kevhito 4y ago
  The missing piece of "just choose to always go left" is that this is a degenerate and uninteresting case. No decision is being made. The range must be discrete and at least 2 possible values. There is nothing about optimality at all here. Even if both possible outputs are equally "optimal", there is no procedure to pick one in a finite amount of time.
  - Kranar 4y ago
    I doubt the issue has anything to do with being interesting or not. Do you know this for a fact or can give me anything to follow up on what it means for a decision to be interesting? For example if a decision procedure required the choice of chocolate or vanilla depending on the current time of day (a continuous input resulting in a discrete output), and I present an algorithm that categorically chooses chocolate regardless of what time it is, I doubt you'd turn around and claim that my algorithm is not making a decision because it always chooses chocolate. If an algorithm takes an input, continuous or discrete, discards that input and returns a constant value, that algorithm is just as "legitimate" as any other algorithm in so far as being an algorithm is concerned. It may not produce the optimal output for some given cost, but it is a formal and rigorous decision procedure that manages to output a discrete value given a continuous input in a bounded amount of time. At any rate, reading the comments when this was last posted it looks like the issue has to do with producing the optimal output in a given time frame. If an optimal discrete decision must be made in the next T seconds on the basis of a continuous input X, then there always exists some value of X that requires more than T seconds to compute. This will be true for any value of T regardless of how large.
- andi999 4y ago
  Yes, always go left (except if you start at 1) is a solution. It is dismissed by Lamport though because the function is not continuous in 1. Somehow he believes not beiing continuous violates some principles of physics.
gryn 4y ago
the signal needs to have a maximal frequency for samling theorem to be aplicable. not all functions on a continious domain have that, in fact i think its the oposite most don't unless proved otherwise.

froh 4y ago

uh --- which implications does this have for driving AI? Possibly none, if the acceptance criterion for AI is: "it kills fewer people than humans would. possibly others, but fewer overall." ?

Afton 4y ago
None, unless you think that people are somehow able to side-step this problem in a way that a computer can't mimic.
- kevhito 4y ago
  The paper specifically details several situations in which humans are the ones making the decision, and the result is the same. There is no bounded-time decision procedure that can take continuous (i.e. physical) inputs and render a discrete decision.
charcircuit 4y ago
Driving AI doesn't require continuous input variables. Approximations are good enough in the real world.
- kevhito 4y ago
  What do you mean? All the inputs are continuous: light sensors, LIDAR, infra-red, inputs from mechanical sensors from the driver. Sure, the sensor package's hardware/firmware/software converts these to discrete inputs before it reaches the Driving AI, but all of the Buridan's Paradox results still apply to those sensor packages. They can't perform their tasks in a finite amount of time -- either they will sometimes fail to make a decision at all, or they will render an invalid output (e.g. rather than outputting voltage corresponding to logical 0 or 1, they will go into a meta-stable or astable output mode that is not a valid output voltage).
  - charcircuit 4y ago
    >rather than outputting voltage corresponding to logical 0 or 1, they will go into a meta-stable or astable output mode that is not a valid output voltage It sounds like you could easily avoid this. You can use a microprocessor and lead in analog input on one pin and then set an output pin based off that. You will always output a valid voltage. Sensors have noise anyways so it's not a big deal if the output is slightly wrong.

EGreg 4y ago

I emailed back and forth with Leslie a lot about this, when I first read his paper. There is an earlier analysis of the same phenomenon by different people (the arbiter problem) which I discovered later. At first, I had trouble to believe it, and tried to find counterexamples, until I realized that the composition of continuous functions is continuous. I still wonder sometimes whether an infinite composition of continuous functions has to be continuous (limit of a sequence) if it represents some real world evolving process. Can it produce a discontinuity in the limit? Anyway, Buridan’s principle informs our consensus process in Intercoin Protocol[1] [2] — it is why the consensus groups are always of a bounded finite size, so we don’t approach the errors in Buridan’s priciple (I think this is also called unstable problems). 1. Beyond blockchains https://community.intercoin.org/t/intercoin-technology-consensus/ https://community.intercoin.org/t/intercoin-technology-conse... 2. Experimental improvements https://community.intercoin.org/t/experimental-improvements-for-intercoin-consensus/ https://community.intercoin.org/t/experimental-improvements-... Anyone who reads the above … I would be very interested in your feedback on our forum.

deleted 4y ago
[deleted]
raegis 4y ago
> I still wonder sometimes whether an infinite composition of continuous functions has to be continuous (limit of a sequence) ... No, as you expected. Take f(x) = x^2 on [0,1]. Then f(f(f(...f(x))) converges to g(x) = { 0, if 0 <= x < 1; 1, if x=1 }
- EGreg 4y ago
  Right. So now the question is -- are you able to give a physical example of physical (continuous) processes which can create a discontinuous output from a continuous initial state, in a finite amount of time? I think this is a sort of Zeno's paradox...
  - juhanima 4y ago
    Tossing a coin?

grayclhn 4y ago

From skimming the paper, "continuity" seems to be a deceptively strong assumption here, and the claim "this is a physical system so it's continuous" is doing a lot of heavy lifting. Unless I'm misunderstanding the example in the first paragraph, "move towards point 1 at a constant pace" can't be represented as a continuous A_t(x) for t above some finite threshold.

thfuran 4y ago
Why not? How are you getting discontinuities out of constant velocity motion?
- harerazer 4y ago
  Consider the following decision: If x < 0.5 go left at a constant speed till the hay is reached, else go right at a constant speed until the hay is reached. Then A(t,x) is clearly not continuous in x, and we can easily bound the time required to make a decision. The nuance here is that we have to somehow be able to distinguish 0.5 - eps from 0.5 for very small epsilon. Edit: on further thought, suppose we had a device which measured reasonably well. More precisely it tells us x < 0.5 if x is actually <= 0.5 - c, it tells us x >= 0.5 if x > 0.5 + c, and tells us it is unsure otherwise. We do not know c, but it is deterministic (and hopefully reasonably small). Then we can decide to go left if it tells us x < 0.5, and right if it tells us unsure or that x >= 0.5.
  - irishsultan 4y ago
    > The nuance here is that we have to somehow be able to distinguish 0.5 - eps from 0.5 for very small epsilon. If you ignore the problem then the problem indeed goes away. The need for distinguishing very small epsilon exists because of the continuity assumption, and because of the continuity assumption you can't really solve it either. > Then we can decide to go left if it tells us x < 0.5, and right if it tells us unsure or that x >= 0.5. Now you just moved the problem to deciding at which point you are unsure. As long as there is a decision to take the issue persists, it's only if you always go left (or always go right) that the issue doesn't exist.

emmelaich 4y ago

Discussed at https://news.ycombinator.com/item?id=22884831 https://news.ycombinator.com/item?id=22884831

bsedlm 4y ago

to be fair, the paper has a funny tone, like an elaborate joke would have... I feel like he may deliver a punch-line at any point before I finish reading the paper and then I'd have to choose whether to burst out laughing or not

deleted 4y ago

[deleted]

im3w1l 4y ago

I think Buridan's ass is like an inverted pendulum. There is no particular reason why it should fall either way but the slightest gust of wind or vibration will trigger a self-reinforcing process that breaks the stalemate. Now, an inverted pendulum can be stabilized with a control system, and this might be possible to relate with adversarial inputs of some system.

pontusrehula 4y ago

> Real accidents may occur because people cannot decide in time which of two alternative actions to take, even though either would prevent the accident. Reminds me of one of the Boeing 737 crashes where pilots were reading the manual but had not enough time to reach the relevant pages.

Animats 4y ago

This is a very real phenomenon. But Lamport didn't discover it. It was known a decade earlier. The classic paper is Kinniment and Wood, 1976.[1] The earliest patent in this area is from 1972.[2] It's quite difficult to do this right. Arbiters today recognize "A was first", "B was first", and "ambiguous, must retry". The system has to be prepared for rare retry delays. In theory there can be an infinite number of retries, but the odds of needing more than one retry are very low. It comes up all the time in multiport memories, where several CPUs are accessing the same memory, and there has to be an arbiter to decide who gets access access for near-simultaneous requests. Requests can be very close to simultaneous. If two CPUs with 3 GHz clocks are contending for memory access, and the clocks are not synchronized but close, about once per second they will be within 10^-19 seconds of whatever difference is most troublesome. This was a serious problem with some early multiprocessor mainframes. Early in my career we saw this happening with multiprocessor UNIVAC 1108 machines. They had an unsound arbiter, and, once in a while, every few hours, they'd botch a memory access. Early on, the software stability was so bad the OS crashed more often than the hardware did, but as the OS got better, it became clear there was a race condition at the hardware level. [1] http://async.org.uk/David.Kinniment/Research/papers/IEE1976.pdf http://async.org.uk/David.Kinniment/Research/papers/IEE1976.... [2] https://patents.google.com/patent/US3824409A/en https://patents.google.com/patent/US3824409A/en

gradschool 4y ago
Kinniment expands on the idea at length in [1]. Chaney is another good source on the history of arbiters [2]. Specialists in asynchronous circuit design think about arbiters a lot. Alex Yakovlev and Alain Martin have published some papers about them. [1] http://www.async.org.uk/David.Kinniment/DJKinniment-He-Who-Hesitates-is-Lost.pdf http://www.async.org.uk/David.Kinniment/DJKinniment-He-Who-H... [2] https://arl.wustl.edu/~jst/cse/260/glitchChaney.pdf https://arl.wustl.edu/~jst/cse/260/glitchChaney.pdf edit: typo
- Animats 4y ago
  And, finally, here's a data sheet for a 74F786 4-bit asynchronous bus arbiter IC.[1] Here's the answer to the paradox of Buridan's ass[2], in a 16-pin dual inline package. It doesn't take free will. "The 74F786 is designed so that contention between two or more request signals will not glitch or display a metastable condition. In this situation an increase in the BRn to BGn tPHL may be observed. A typical 74F786 has an h = 6.6ns, t = 0.41ns and To = 5µsec." "If two or more BRn inputs are asserted at precisely the same time, one of them will be selected at random, and all BGn outputs will be held in the high state until the selection is made. This guarantees that an erroneous BGn will not be generated even though a metastable condition may occur internal to the device." So, usually, you get a win within a specified time, but sometimes it takes longer. The limit on the longest time is probabilistic, but the odds of settling increase rapidly with time, by orders of magnitude per nanosecond. In this part, we get to see a simple standalone arbiter with its own data sheet. A logic diagram is given, so you can see how this is built out of simple gates. Note that diagram can't be read as abstract logic; propagation delay matters. While the arbiter is in a metastable state, an inhibit signal is generated which prevents any output from appearing. Once the arbiter has settled, the winning output is allowed out. The gate thresholds matter. The inhibit signal doesn't turn off until there's only one clear winner. It's an old part, from 1991, because today this function is usually part of a larger function such as a CPU chip or a DRAM interface. [1] https://www.digikey.com/en/htmldatasheets/production/96092/0/0/1/74f786.html https://www.digikey.com/en/htmldatasheets/production/96092/0... [2] https://en.wikipedia.org/wiki/Buridan%27s_ass https://en.wikipedia.org/wiki/Buridan%27s_ass

zozbot234 4y ago

> A discrete decision based upon an input having a continuous range of values cannot be made within a bounded length of time. I understand that this is true for deterministic decisions. But a limited amount of randomness/noise is generally an acceptable alternative to a requirement for unbounded precision.

lisper 4y ago

Why is an analog-to-digital converters not a counterexample? For that matter, why is a comparator (a one-bit ADC) not a counterexample? Or, for that matter, a wire tied to ground? Or a 3x5 card with the word "YES" printed on it?

kazinator 4y ago
I think it's because these devices do not always make the correct decision between two values. Lamport's paper covers this in the interrupt example: a computer must decide whether an interrupt line is signaled or not in a finite amount of time (the next instruction). The interrupt is continuous: it passes through some halfway voltage level like 2.5 between 0 and 5, and so it can be called the wrong way. Basically the whole result is a restatement of real numbers not being computable. The discrete sample value you get from an ADC is not based on knowing the underlying real number absolutely, and then choosing the nearest value. It's a time limited process of discovering the value partially. Since the value is not partially known, it is not known whether the reported sample value is the closest one.