Do any computer systems use randomness as a way to avoid livelock? In the car example, cars could randomly choose whether to back up or stay still. Is "random" choosing too costly to implement?
hofstee
@jhibshma Bounded randomness is sometimes considered. Another strategy that is used is exponential backoff, so we will wait 1 time unit, then 2, then 4, etc. until some maximum limit.
rmanne
And this is why starting a million pthreads is different from starting a million ispc tasks. The pthread implementation has a risk of starvation because all the threads could end up being interleaved.
Updog
One good example of livelock that most people encounter daily is WiFi. The wireless medium is a shared channel, and multiple devices contend with each other for access. Access to the channel is not centrally scheduled, but rather each device will listen on the medium, and if it is clear it will make a transmission. If the medium is busy, the device backs off a random amount of time, and the maximum this random amount can be increases exponentially with repeated backoffs. A node also backs off it it doesn't receive an ACK after a transmission (likely due to a collision with another node). So if there are a lot of devices trying to use WiFi in the same area, the average backoff time for any given node will be large, which is why everyone's connection is slow. You can read more here.
Lawliet
How would exponential back off help lifelock if they all back off the same amount before trying again?
fleventyfive
@Lawliet, you are absolutely correct. Exponential back off would not help solve livelock if they all back off the same amount before trying again. Therefore, from Wikipedia: "The hosts must choose a random value within an acceptable range to ensure that this situation doesn't happen." The randomization of the chosen time to wait helps solve this problem.
Even then, it is very likely that two hosts can choose the same random time!
In that case, the hosts slowly increase the "range" of choosing random values to gradually increase the chances of choosing different waiting times, thereby guaranteeing with high probability, that one of them can proceed after a finite number of retries.
Do any computer systems use randomness as a way to avoid livelock? In the car example, cars could randomly choose whether to back up or stay still. Is "random" choosing too costly to implement?
@jhibshma Bounded randomness is sometimes considered. Another strategy that is used is exponential backoff, so we will wait 1 time unit, then 2, then 4, etc. until some maximum limit.
And this is why starting a million pthreads is different from starting a million ispc tasks. The pthread implementation has a risk of starvation because all the threads could end up being interleaved.
One good example of livelock that most people encounter daily is WiFi. The wireless medium is a shared channel, and multiple devices contend with each other for access. Access to the channel is not centrally scheduled, but rather each device will listen on the medium, and if it is clear it will make a transmission. If the medium is busy, the device backs off a random amount of time, and the maximum this random amount can be increases exponentially with repeated backoffs. A node also backs off it it doesn't receive an ACK after a transmission (likely due to a collision with another node). So if there are a lot of devices trying to use WiFi in the same area, the average backoff time for any given node will be large, which is why everyone's connection is slow. You can read more here.
How would exponential back off help lifelock if they all back off the same amount before trying again?
@Lawliet, you are absolutely correct. Exponential back off would not help solve livelock if they all back off the same amount before trying again. Therefore, from Wikipedia: "The hosts must choose a random value within an acceptable range to ensure that this situation doesn't happen." The randomization of the chosen time to wait helps solve this problem. Even then, it is very likely that two hosts can choose the same random time! In that case, the hosts slowly increase the "range" of choosing random values to gradually increase the chances of choosing different waiting times, thereby guaranteeing with high probability, that one of them can proceed after a finite number of retries.