[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Today's problem with GUB build

From: Han-Wen Nienhuys
Subject: Re: Today's problem with GUB build
Date: Thu, 16 Jul 2020 09:36:58 +0200

On Wed, Jul 15, 2020 at 10:48 PM David Kastrup <> 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 - -

reply via email to

[Prev in Thread] Current Thread [Next in Thread]