Available data show that eolian dust accumulation rates on desert alluvial fan terraces are often inversely proportional to the square root of the terrace age for a given area. This temporal scaling is similar to that observed in fluvial and marine stratigraphic sequences in which a fractal distribution of hiatuses occurs (i.e., a Cantor set). Eolian dust accumulation on alluvial fan terraces is controlled by regional climatic influences on dust deposition (e.g., dessication of pluvial lakes in the early Holocene) and local surface characteristics (e.g., vegetation and pavement coverage) that control dust preservation. In order to interpret the observed scaling in terms of these relative influences I consider two end-member models: (1) a deterministic model in which dust deposition is controlled by cyclical climatic changes (i.e., glacial-interglacial cycles) and in which no erosion occurs, and (2) a stochastic model in which erosion and deposition take place with equal probability and magnitude during each time step (i.e., a bounded random walk). The observed temporal scaling is most consistent with the bounded random walk model, suggesting that long-term eolian dust accumulation is predominantly controlled by episodic changes in vegetation and pavement coverage over time and that eolian dust deposits are strongly punctuated by episodes of erosional reworking at a wide range of temporal scales.