The Impact of Reversibility on Parallel Pebbling

ePrint Report: The Impact of Reversibility on Parallel Pebbling

Jeremiah Blocki, Blake Holman, Seunghoon Lee

The (parallel) classical black pebbling game is a helpful abstraction which allows us to analyze the resources (time, space, space-time, cumulative space) necessary to evaluate a function $f$ with a static data-dependency graph $G$ on a (parallel) computer. In particular, the parallel black pebbling game has been used as a tool to quantify the (in)security of Data-Independent Memory-Hard Functions (iMHFs). Recently Blocki et al. (TCC …

abstraction computer data dependency eprint report function game graph impact lee parallel report resources space