Model variant proposed by Papp, Sobczyk, and Yzelman [1].

In this model variant, computations can be executed in parts, where partial results can be stored in the main memory, and updated again in later steps.

Any graph with arbitrarily large in-degrees can be pebbled with as few as two red pebbles!

For more details see the description below, and the corresponding publication [1].

[1] Papp, Pál András, Aleksandros Sobczyk, and Albert-Jan N. Yzelman. "The Impact of Partial Computations on the Red-Blue Pebble Game." Proceedings of the 37th ACM Symposium on Parallelism in Algorithms and Architectures. 2025.

Acknowledgements: Special thanks to Pál András Papp, Toni Böhnlein, Anastasios Zouzias, for improvement suggestions!
Code development assisted by DeepSeek AI https://deepseek.com

Blue (Slow Memory)
Light Red (Fast Memory, unmodified value)
Dark Red (Fast Memory, value is modified)
Empty Node
Moves: 0
Click "Generate Layered DAG" to start!

Game Rules:

  1. Generate DAG: Creates a directed acyclic graph with nodes in layers
  2. Moves:
    • Place Blue & L. Red (SAVE): Place a Blue and a Light-Red pebble on any node that has a Dark-Red pebble. Cost: 1 move
    • Place Light-Red (LOAD): Place a Light-Red pebble on a node that has a Blue pebble. Cost: 1 move
    • Place Dark-Red (COMPUTE): Place a Dark-Red pebble on a vertex that has at least one predecessor with a Red Pebble (Light or Dark) Cost: 0 moves
    • Remove Red (DELETE): Remove a Light-Red pebble from any node, or a Dark-Red pebble from a node where all of its outgoing edges are marked. Cost: 0 moves
  3. Marking Edges: An unmarked edge (u,v) is automatically marked when both u and v have Red pebbles (Light or Dark). All the pebbles on v are replaced with a Dark-Red pebble.
  4. Initial State: Source nodes (no incoming edges) start with blue pebbles
  5. Memory Limits: Red pebbles limited, Blue pebbles unlimited
  6. Goal: Cover all output nodes with Blue pebbles, and mark all edges in the graph, using minimal number of moves