Re: Today's problem with GUB build

[Han-Wen Nienhuys]

On Wed, Jul 15, 2020 at 10:48 PM David Kastrup <dak@gnu.org> wrote:

> Well ok.  But only 1000000 random numbers are being used (there is
> another call using 10000000 instead, the choice appearing random).
> Let's assume we have 10 processes going through 138 files each.  The
> processes are going to switch to the next output file asynchronously, so
> with any change, there is a chance of the old number colliding with the
> other processes' numbers, and the new number colliding.  The probability
> that a new number is different from an existing set of 9 is
> 999991/1000000.  If we do this switch 1380 times, the probability of a
> collision during one run is 1-(999991/1000000)^1380, about 1 in 80.

I don't think this analysis is correct. In order for two numbers to
meaningfully collide, they have to be picked at the same time (since
we rename the files afterwards.). The birthday attack says you need
1000 parallel instances to get a 50% of collision.

> Now if I remember correctly, there were some changes in how
> lilypond-book worked that typically resulted in double the number of
> processes getting spawned than asked for which would give us 19 instead
> of 9 possibilities for collision.  That would raise the probability of a
> collision to about 1 in 40 runs.

I think you misremember. The command

  make -jN CPU_COUNT=N

will potentially spawn 2*N -1 processes: 1 x lilypond-book with N
children and N- 1 other processes.

-- 
Han-Wen Nienhuys - hanwenn@gmail.com - http://www.xs4all.nl/~hanwen