A state store having state information therein is stored on a computing device. Information at least nearly unique to the computing device is obtained, and a number of locations at which at least a portion of the state store is to be stored at is determined. Pseudo-random file names and corresponding paths are generated based at least in part on the obtained information, whereby the generated file names and corresponding paths are likewise at least nearly unique to the computing device, and the generated file names and path are paired to form the locations. Thereafter, the state store is stored according to the generated locations.