flink-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Greg Hogan (JIRA)" <j...@apache.org>
Subject [jira] [Created] (FLINK-3997) PRNG Skip-ahead
Date Tue, 31 May 2016 14:02:13 GMT
Greg Hogan created FLINK-3997:
---------------------------------

             Summary: PRNG Skip-ahead
                 Key: FLINK-3997
                 URL: https://issues.apache.org/jira/browse/FLINK-3997
             Project: Flink
          Issue Type: Improvement
          Components: Gelly
    Affects Versions: 1.1.0
            Reporter: Greg Hogan
            Assignee: Greg Hogan


The current sources of randomness for Gelly Graph Generators use fixed-size blocks of work
which include an initial seed. There are two issues with this approach. First, the size of
the collection of blocks can exceed the Akka limit and cause the job to silently fail. Second,
as the block seeds are randomly chosen, the likelihood of blocks overlapping and producing
the same sequence increases with the size of the graph.

The random generators will be reimplemented using {{SplittableIterator}} and PRNGs supporting
skip-ahead.

This ticket will implement skip-ahead with LCGs [0]. Future work may add support for xorshift
generators ([1], section 5 "Jumping Ahead").

[0] https://mit-crpg.github.io/openmc/methods/random_numbers.html#skip-ahead-capability
[1] https://arxiv.org/pdf/1404.0390.pdf



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)

Mime
View raw message