The select statement and "fairness"

[Chris Conway]

I'm curious about the precise semantics of the select statement. The language specification says:

If multiple cases can proceed, a pseudo-random fair choice is made to decide which single communication will execute.

But the word "fair" is not precisely defined. Is it intended to denote the classical technical definition of fairness ("if a case can proceed infinitely often, it will execute infinitely often")? Or perhaps "weak fairness" ("if a case can proceed continuously, it will eventually execute")?

-Chris

[Kyle Lemons]

It means that no particular case is given an unfair advantage (e.g. there is an equal chance that any case will execute).  See the following example:

http://play.golang.org/

package main

import "fmt"

func randbit(out chan<- int) {

for {

select {

case out <- 0:

case out <- 1:

}

}

}

func main() {

bits := make(chan int)

go randbit(bits)

for i := 0; i < 10; i++ {

fmt.Print(<-bits)

}

fmt.Println()

[Chris Conway]

On Thursday, January 12, 2012 2:27:37 PM UTC-5, Kyle Lemons wrote:

It means that no particular case is given an unfair advantage (e.g. there is an equal chance that any case will execute).

I hope it doesn't mean that! The term of art for this would be "uniform" whereas "fair" has a well-established technical meaning in this context.

Is the following accurate?

Let c be a case in a select statement s with n cases. If c can proceed in k executions of s, c will execute at least once with probability >= (1 - 1/n)^k.

This would be a perfectly reasonable guarantee, but not what is usually called "fair".

-Chris

[Kyle Lemons]

On Thursday, January 12, 2012 2:27:37 PM UTC-5, Kyle Lemons wrote:

It means that no particular case is given an unfair advantage (e.g. there is an equal chance that any case will execute).

I hope it doesn't mean that! The term of art for this would be "uniform" whereas "fair" has a well-established technical meaning in this context.

Is the following accurate?

Let c be a case in a select statement s with n cases. If c can proceed in k executions of s, c will execute at least once with probability >= (1 - 1/n)^k.

This would be a perfectly reasonable guarantee, but not what is usually called "fair".

That definition is inscrutable.  The way it is written might not stand up in a court of law, but it is pretty explicit and very readable (like the rest of the document).  It's fair in the way that a dice roll is fair or a coin toss is fair.

[Chris Conway]

I don't propose adding the above wording to the specification. I'm just testing my understanding by stating an implication of the specification in my own words. I *do* think the document should be revised, though, since the use of the word "fair" in this context will confuse anybody familiar with the theory of concurrent systems. I would suggest "uniform pseudo-random choice" instead of "pseudo-random fair choice".

-Chris

[peterGo]

Chris,

I don't think that's right. At a particular point in time, there are x
communications ready to proceed spread across y cases. What does your
algorithm say about the likelihood that a particular communication
will execute?

Peter

[Chris Conway]

On Thu, Jan 12, 2012 at 3:34 PM, peterGo <go.pe...@gmail.com> wrote:

Chris,

I don't think that's right. At a particular point in time, there are x
communications ready to proceed spread across y cases. What does your
algorithm say about the likelihood that a particular communication
will execute?

Peter,

I think you're right that my formula was wrong (it's actually the probability of *never* executing the case!). I think the correct formula for a select statement with n cases where case c is continuously enabled is:

P[c executing at least once in k iterations] >= 1 - [(n-1)/n]^k

 

It's enough to use n for the lower bound. If at most x cases are enabled in each iteration, then

P[c executing at least once in k iterations] >= 1 - [(x-1)/x]^k >= 1 - [(n-1)/n]^k

-Chris

[⚛]

The Go language has no idea whether the outcome of a particular
selection will be positive or negative. Thus "uniform pseudo-random
choice" is a fair policy. The specification correctly says that it is
a "pseudo-random fair choice".

From a different point of view, the specification is describing what
the Go language implementation should be. If the specification says
that "pseudo-random fair choice is made", it can be interpreted as a
*goal* to be reached by Go language implementation(s). The meaning of
"pseudo-random" and "fair" is intentionally imprecise.

[Chris Conway]

The conversation thus far appears to have gotten confused between a few different questions:

1) What is the implemented policy for choosing which case of a select statement gets executed?

2) Is the wording of the specification clear and unambiguous about that policy?
3) Is it a good policy?

The reaction I'm getting seems to assume that I'm concerned with (3), whereas I'm solely concerned with (1) and (2). I recognize that uniform random choice between unblocked cases is a perfectly reasonable policy.

If that is the policy, I do not think that "a pseudo-random fair choice" is a good choice of words to describe it, because "fair" has a misleading technical meaning in this context (http://en.wikipedia.org/wiki/Unbounded_nondeterminism#Fairness). I would suggest "a uniform pseudo-random choice" to describe this behavior. However, I see that Rob Pike changed the wording from "a uniform fair choice", which is the earliest wording AFAICT, in revision 5798. I'd be curious to hear what his thinking was in dropping the word "uniform" and keeping the word "fair".

The difference between a "fair" choice and a "uniform" choice is whether the following program is guaranteed to terminate or is only highly likely to terminate:

func writer(out chan<- int, quit <-chan bool, done chan<- bool) {

defer close(out)

defer close(done)

for {

select {

case out <- 0:  // Loop case

case <-quit: return  // Cancellation

}

}

}

func reader(in <-chan int) {

for _ = range in {}

}

func main() {

c, q, d := make(chan int), make(chan bool), make(chan bool)

go writer(c, q, d)

go reader(c)  // Repeatedly enables the loop case of writer

close(q)  // Enables the cancellation case of writer

<-d  // Blocked until writer exits

}

-Chris

[Christopher Hundt]

On Fri, Jan 13, 2012 at 11:51 AM, Chris Conway <clco...@google.com> wrote:

The conversation thus far appears to have gotten confused between a few different questions:

1) What is the implemented policy for choosing which case of a select statement gets executed?

2) Is the wording of the specification clear and unambiguous about that policy?
3) Is it a good policy?

The reaction I'm getting seems to assume that I'm concerned with (3), whereas I'm solely concerned with (1) and (2). I recognize that uniform random choice between unblocked cases is a perfectly reasonable policy.

If that is the policy, I do not think that "a pseudo-random fair choice" is a good choice of words to describe it, because "fair" has a misleading technical meaning in this context (http://en.wikipedia.org/wiki/Unbounded_nondeterminism#Fairness). I would suggest "a uniform pseudo-random choice" to describe this behavior. However, I see that Rob Pike changed the wording from "a uniform fair choice", which is the earliest wording AFAICT, in revision 5798. I'd be curious to hear what his thinking was in dropping the word "uniform" and keeping the word "fair".

The difference between a "fair" choice and a "uniform" choice is whether the following program is guaranteed to terminate or is only highly likely to terminate:

func writer(out chan<- int, quit <-chan bool, done chan<- bool) {

defer close(out)

defer close(done)

for {

select {

case out <- 0:  // Loop case

case <-quit: return  // Cancellation

}

}

}

func reader(in <-chan int) {

for _ = range in {}

}

func main() {

c, q, d := make(chan int), make(chan bool), make(chan bool)

go writer(c, q, d)

go reader(c)  // Repeatedly enables the loop case of writer

close(q)  // Enables the cancellation case of writer

<-d  // Blocked until writer exits

}

I believe that program is not just highly likely to terminate, but will terminate with probability 1. It seems that you are concerned with the difference between "fair" and "fair with probability 1." Why is that distinction important?

[Rob 'Commander' Pike]

Would you be happy if the phrase

pseudo-random fair choice

was replaced with

uniform pseudo-random choice

?

To me, the definition is operational rather than formal, but I want it to be clear and correct.

-rob

[Chris Conway]

On Fri, Jan 13, 2012 at 4:10 PM, Rob 'Commander' Pike <r...@google.com> wrote:

Would you be happy if the phrase

       pseudo-random fair choice

was replaced with

       uniform pseudo-random choice

?

Sure. That's the wording I suggested up-thread.

 

To me, the definition is operational rather than formal, but I want it to be clear and correct.

Understood. I feel like an alien from Planet Dijkstra here. :-)

Thanks,

Chris

[Chris Conway]

How so? If I understand correctly, the program terminates with a probability that converges on 1. This is not the same as provably terminating in a finite number of steps.

 

It seems that you are concerned with the difference between "fair" and "fair with probability 1." Why is that distinction important?

It's not important operationally. But it affects your termination arguments, if you're in the habit of formulating them (and I am).

-Chris

[Christopher Hundt]

[ bcc others since I think the issue has been resolved so this is now purely academic ]

On Fri, Jan 13, 2012 at 1:37 PM, Chris Conway <clco...@google.com> wrote:

On Fri, Jan 13, 2012 at 4:02 PM, Christopher Hundt <hu...@google.com> wrote:

On Fri, Jan 13, 2012 at 11:51 AM, Chris Conway <clco...@google.com> wrote:

The difference between a "fair" choice and a "uniform" choice is whether the following program is guaranteed to terminate or is only highly likely to terminate:

func writer(out chan<- int, quit <-chan bool, done chan<- bool) {

defer close(out)

defer close(done)

for {

select {

case out <- 0:  // Loop case

case <-quit: return  // Cancellation

}

}

}

func reader(in <-chan int) {

for _ = range in {}

}

func main() {

c, q, d := make(chan int), make(chan bool), make(chan bool)

go writer(c, q, d)

go reader(c)  // Repeatedly enables the loop case of writer

close(q)  // Enables the cancellation case of writer

<-d  // Blocked until writer exits

}

I believe that program is not just highly likely to terminate, but will terminate with probability 1.

How so? If I understand correctly, the program terminates with a probability that converges on 1. This is not the same as provably terminating in a finite number of steps.

Well, the probability that it will go on forever without terminating is 0. Therefore the probability that it will terminate is 1.

 

 

It seems that you are concerned with the difference between "fair" and "fair with probability 1." Why is that distinction important?

It's not important operationally. But it affects your termination arguments, if you're in the habit of formulating them (and I am).

I guess I had naively guessed that proving termination with probability 1 should be just as useful as proving termination using the more tradition arguments, even in constructing further arguments. Is it not?

[Jonathan Wills]

On Fri, Jan 13, 2012 at 1:37 PM, Chris Conway <clco...@google.com> wrote:

On Fri, Jan 13, 2012 at 4:02 PM, Christopher Hundt <hu...@google.com> wrote:

On Fri, Jan 13, 2012 at 11:51 AM, Chris Conway <clco...@google.com> wrote:

The difference between a "fair" choice and a "uniform" choice is whether the following program is guaranteed to terminate or is only highly likely to terminate:

func writer(out chan<- int, quit <-chan bool, done chan<- bool) {

defer close(out)

defer close(done)

for {

select {

case out <- 0:  // Loop case

case <-quit: return  // Cancellation

}

}

}

func reader(in <-chan int) {

for _ = range in {}

}

func main() {

c, q, d := make(chan int), make(chan bool), make(chan bool)

go writer(c, q, d)

go reader(c)  // Repeatedly enables the loop case of writer

close(q)  // Enables the cancellation case of writer

<-d  // Blocked until writer exits

}

I believe that program is not just highly likely to terminate, but will terminate with probability 1.

How so? If I understand correctly, the program terminates with a probability that converges on 1. This is not the same as provably terminating in a finite number of steps.

 

I believe that since the select statement explicitly uses a pseudo-random number generator it is guaranteed to terminate.

[⚛]

On Jan 13, 8:51 pm, Chris Conway <clcon...@google.com> wrote:
> The difference between a "fair" choice and a "uniform" choice is whether
> the following program is guaranteed to terminate or is only highly likely
> to terminate:

Uniform pseudo-random choice is one way of how to implement fairness.

In addition, whether all such Go programs are guaranteed to terminate
also depends on the scheduler (how to choose a goroutine for execution
from the set of all goroutines that aren't blocked).

[si guy]

Woah, wait, the select statement is not actually fair? I was operating under the assumption that if I had a loop over a select(2 cases) and both were always ready(buffered for example) that they would alternate because that was the "fairest" way to do it.... Something like randomness compensation in a video game.(e.g.: preventing a string of 6s on a d6 dice roll). In hindsight this was probably a naive assumption.

If I wanted this to be the case, for managing a worker pool across a cloud of machines for example where load balancing is critical, would anyone know of an implementation that is not raw? i.e. an implementation that only modifies select _slightly_, i'm pretty sure I could figure out a fair algorithm using counters and a state machine, but that would mean rewriting a lot of my code...

Thanks.

-Simon Watt

[si guy]

Ok, so here is a naive implementation of what I'm talking about using container/list in weekly (go playground links aren't working for me atm, sorry)

Any thoughts? I think this is safe. Unfortunately it is also non-blocking by necessity.

package main

import (

"fmt"

"container/list"

)

type T string

func main() {

channels := list.New()

// Create the fake channels

c1 := make(chan T,10)

c2 := make(chan T,10)

c3 := make(chan T,10)

// Insert the channels into the list

channels.PushBack(c1)

channels.PushBack(c2)

channels.PushBack(c3)

// Put some data into the channels

for x := 0; x < 10; x ++ {

c1 <- T(fmt.Sprint("c1 ",x))

c2 <- T(fmt.Sprint("c2 ",x))

c3 <- T(fmt.Sprint("c3 ",x))

}

// Now select in a fair way

outer: for {

c := channels.Front()

select {

case out := <-c.Value.(chan T):

fmt.Println(out)

channels.MoveToBack(c)

default:

c = c.Next()

select {

case out := <-c.Value.(chan T):

fmt.Println(out)

channels.MoveToBack(c)

default:

c = c.Next()

select {

case out := <-c.Value.(chan T):

fmt.Println(out)

channels.MoveToBack(c)

default:

// Nothing is ready, break the for loop in this case

break outer

}

}

}

}

}

This Prints:

c1 0
c2 0
c3 0
c1 1
c2 1
c3 1
c1 2
c2 2
c3 2
c1 3
c2 3
c3 3
c1 4
c2 4
c3 4
c1 5
c2 5
c3 5
c1 6
c2 6
c3 6
c1 7
c2 7
c3 7
c1 8
c2 8
c3 8
c1 9
c2 9
c3 9

[Kyle Lemons]

No, it has the behavior you want.  See the example I pasted earlier.  It randomly chooses "1" or "0".

http://play.golang.org/p/0BSYLlNOyF

[Chris Conway]

Rob,

I'm not sure if the purpose of the specification is to describe the current implementation or to provide requirements for all implementations, but it occurs to me that the "random choice" language excludes a "load balancing" implementation like the following. I wonder if this is intentional?

// Forgive some pseudo-code magic. I hope the intention is clear...

var pending PriorityQueue

// Chooses the case that is currently enabled that has been passed over the most previous times.

// Chooses nondeterministically if there is a tie.

func chooseCase(s selectStmt) selectCase {

  var enabled PriorityQueue

  for c := range s {

    if c.CanProceed() {

      pending.IncrementWeight(c)  // adds c with weight 0, if not present

      enabled.Insert(c, pending.Weight(c))

    }

  }
  c := enabled.RemoveMax()

  pending.Remove(c)

  return c

}

This seems to me a reasonable implementation policy (though clearly not the most efficient one). For a select statement with n cases, it guarantees that no case will wait more than n iterations to execute.

-Chris

On Fri, Jan 13, 2012 at 4:10 PM, Rob 'Commander' Pike <r...@google.com> wrote:

[Ian Lance Taylor]

Chris Conway <clco...@google.com> writes:

> I'm not sure if the purpose of the specification is to describe the current
> implementation or to provide requirements for all implementations, but it
> occurs to me that the "random choice" language excludes a "load balancing"
> implementation like the following. I wonder if this is intentional?
>
> // Forgive some pseudo-code magic. I hope the intention is clear...
> var pending PriorityQueue
>
> // Chooses the case that is currently enabled that has been passed over the
> most previous times.
> // Chooses nondeterministically if there is a tie.
> func chooseCase(s selectStmt) selectCase {
> var enabled PriorityQueue
> for c := range s {
> if c.CanProceed() {
> pending.IncrementWeight(c) // adds c with weight 0, if not present
> enabled.Insert(c, pending.Weight(c))
> }
> }
> c := enabled.RemoveMax()
> pending.Remove(c)
> return c
> }
>
> This seems to me a reasonable implementation policy (though clearly not the
> most efficient one). For a select statement with n cases, it guarantees
> that no case will wait more than n iterations to execute.

The select statement is intended to be random, becaues that is very
efficient and gives a good result for common use cases. A load
balancing implementation would be less efficient for all cases and only
sometimes useful. A program that needs a load balancer can write a load
balancer using the existing semantics.

Ian

[⚛]

On Jan 17, 4:44 pm, Chris Conway <clcon...@google.com> wrote:
> Rob,
>
> I'm not sure if the purpose of the specification is to describe the current
> implementation or to provide requirements for all implementations, but it
> occurs to me that the "random choice" language excludes a "load balancing"
> implementation like the following. I wonder if this is intentional?

In my opinion, the specification is not forbidding a load-balancing
implementation.

[Chris Conway]

The specification calls for a "pseudo-random fair choice" (or alternatively "uniform pseudo-random choice"). The choice in my example is not "random" in any way, and certainly not "uniform."

-Chris

[⚛]

On Jan 17, 7:13 pm, Chris Conway <clcon...@google.com> wrote:

... in a way, all fair scheduling policies are "pseudo-random".

And if you are planning to implement your own fair scheduling policy,
the Go specification cannot stop you.