Algorithmic management of phase-change memory
summary
Racetrack (domain wall) memory models as many tiny Turing-machine tapes where access cost is roughly linear in distance; organizing items on one tape is provably harder than list update: there is no constant competitive online algorithm and simple move-to-front variants fail, using a treelike adversarial sequence to force long moves. A complicated offline polylog approximation is given; work stops at single-tape management. Open directions include multiple tapes and beyond-worst-case analyses.
AI-written summary · about