Come seminare srand () per evitare la collisione su un gran numero di macchine?

Question

In genere, la semina di SRAND () è fatta da:

srand(time(NULL));

.

Nel mio caso, utilizzo i numeri casuali per generare un identificatore per il mio processo client in fase di esecuzione sulla rete. Il processo a volte riavvia e genera un nuovo identificatore. Poiché il numero di clienti aumenta, c'è una buona possibilità che due clienti chiamino srand(time(NULL)) all'interno dello stesso secondo, che crea due identificatori identici o una collisione vista dal lato server. Alcune persone hanno suggerito una risoluzione più fine :

srand((time.tv_sec * 1000) + (time.tv_usec / 1000));

.

Ma il problema qui è che il seme ripeterà ogni 24 giorni circa, e quando il numero di macchine è abbastanza grande, c'è ancora una possibilità di collisione. C'è un'altra soluzione :

srand(time.tv_usec * time.tv_sec);

.

Ma questo mi sembra problematico anche perché il modulo di questo prodotto (il sovraccarico di bit più alto e diventare abbandonato) non è distribuito uniformemente nell'ambito del valore del seme unsigned int. Ad esempio, per ogni secondo, time.tv_usec == 0 porta allo stesso seme.

Così c'è un modo per seminare srand () nel mio caso?

Modifica: il client funziona su Linux, Windows, Android e IOS, così /dev/random o /dev/urandom non è sempre disponibile.

P.S. Sono consapevole dell'approccio GUID / UUID, ma mi piacerebbe sapere se è possibile semplicemente seme SRAND () correttamente in questo caso.

Answer 1

Hai due domini: clienti e processi.Pertanto hai bisogno di un identificatore univoco per ognuno.I processi ovviamente possono essere eseguiti con il processo-ID.Per i clienti, suggerisco di utilizzare l'indirizzo MAC, che deve essere unico per ogni interfaccia di rete.Credo che tutte le piattaforme elenchi prese di supporto, quindi si può supportare il SIOCGIFHWADDR IOCTL.

L'unico problema è che gli indirizzi MAC sono 48 bit e PID sono in genere 32 bit, quindi è necessario scegliere i bit di entropia più elevati dei due valori da utilizzare per il tuo seme SRAND.Suggerisco i 16 bit inferiori del PID e i 16 bit più bassi dell'indirizzo MAC.

Answer 2

srand e rand non sono semplicemente appropriati se si dispone di molti processi o discussioni che devono avere pseudo-casualità che è indipendente tra loro.

On POSIX Systems è possibile utilizzare la famiglia rand48 di funzioni come jrand48 che hanno conosciuto le dimensioni dello stato.Se dipendi dal processo, dall'indipendenza della macchina e della macchina, è necessario utilizzare bit significativi dall'ID processo, dall'ID del thread, l'indirizzo IP e il tempo per inizializzare lo stato.jrand[48] prende (e modifica) uno stato di tre short, quindi dovrebbe essere relativamente semplice seminali con i diversi quantities.

Tutto tranne uno dei sistemi che elenco è POSIX, quindi questo dovrebbe funzionare lì.Quale sarebbe un adeguato fallback per i sistemi Windows, non lo so.

Answer 3

Se due generatori di numeri casuali non hanno mai collisioni, non sono casuali.Sarebbe come giocare 'Snap' ma non ottenere mai una partita.

Allora, ciò che vuoi è peggio, piuttosto che un generatore di numeri casuali migliore.L'utilizzo dei GUID è effettivamente un approccio che dovrebbe rimuovere interamente il problema per te.

Ma, se sei felice di riducendo la possibilità di collisioni, piuttosto che eliminarle interamente è possibile utilizzare l'indirizzo IP della macchina (o il numero di serie del processore o somesuch) come parte del seme.

Answer 4

Se stai scrivendo per la piattaforma Linux, utilizzare /dev/random e /dev/urandom per ottenere numeri casuali.A differenza del srand(), /dev/random e /dev/urandom utilizza il rumore generato dalle periferiche hardware per generare numeri casuali.srand() utilizza sementi forniti come argomento per generare un numero casuale.

Answer 5

Penso che sarai interessato alla carta "numeri casuali paralleli: facili come 1, 2, 3".

Citando dall'astratto: "Tutti i nostri PRNGs passano rigorosi test statistici (incluso il bigcrush di Testu01) e producono almeno 264 flussi paralleli unici di numeri casuali, ciascuno con periodo 2128 o più"