Mailing-List: contact dev-help@flink.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@flink.apache.org
Date: Tue, 31 May 2016 14:02:13 +0000 (UTC)
From: "Greg Hogan (JIRA)" <jira@apache.org>
To: dev@flink.apache.org
Message-ID: <JIRA.12974229.1464703317000.337420.1464703333030@Atlassian.JIRA>
In-Reply-To: <JIRA.12974229.1464703317000@Atlassian.JIRA>
References: <JIRA.12974229.1464703317000@Atlassian.JIRA> <JIRA.12974229.1464703317695@arcas>
Subject: [jira] [Created] (FLINK-3997) PRNG Skip-ahead
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit
archived-at: Tue, 31 May 2016 14:02:15 -0000

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)