Pseudo code for distributed Game of Life

distributed-gol.txt

data
    for every worker
        owned chunks, those chunks that must be computed for each generation
        neighbors, chunks that must be received to proceed to next generation
        needed chunks = owned chunks + neighbors
    for this generation on every worker
        transmitted chunks
    for the prior, current, and next generation on this worker
        needed chunks, a snapshot of owned chunks and neighbor chunks for this worker, less any completed chunks
        needed owned chunks, a snapshot of owned chunks for this worker, less any completed chunks
        completed chunks, includes both owned and non-owned chunks once they have been completed
        transmitting chunks, (chunk, worker) pairs waiting to be transmitted

on ring change

    recompute owned chunks for every worker
    recompute owned neighbors for every worker

    withdraw to prior generation, retaining the partially completed next generation
    prior, current, next = null, prior, current

    # for the older generation
    leave needed owned chunks empty
    populate needed chunks with a snapshot of owned chunks and neighbor chunks for this worker, less any completed chunks
    populate transmitting chunks with (chunk, worker) for all completed chunks for every worker that owns each chunk, except for the same chunk
    # note that the older generation's parent generation does not need to be retained since the owned chunks collection is empty
    # the loss of every replica of any chunk will cause the game to stall permanently
    # recovery strategies for this case are out of scope

    # for the newer generation
    recapture needed chunks for this worker, removing completed chunks
    recapture needed owned chunks for this worker, removing completed chunks
    check for generation completion

on tick, where the delay between ticks is controlled to prevent pathalogical event loop lag
    for the current generation
        pick random chunk from needed owned chunks
        compute the new chunk using the prior generation's neighboring chunks
        add the chunk to completed chunks
        remove the chunk from needed chunks
        remove the chunk from needed owned chunks
        for each worker that needs the chunk
            add the chunk to the transmitting chunks collection
        check for generation completion

for some concurrency while transmitting chunks is non-empty
    take a random chunk from the transmitting collection and send it to the corresponding worker
    check for generation completion

on generation completed (transmitting chunks is empty, needed chunks is empty)
    advance to the next generation
    prior, current, next = current, next, prior
    initialize the new next generation (recycled prior generation)
        set the needed chunks to a snapshot of owned chunks
        set the owned chunks to a snapshot of the owned chunks and neighbor chunks for this worker
        clear the completed chunks
        clear the transmitting chunks