While all the results above assumes the system without storage, sublogarithmic-memory
graph exploration algorithms assuming storage has been proposed, for a variety of storage models.
For example, the rotor-router model [1]}, which is also known as a technique of de-randomizing random walks, guides the agent by the pointer managed by each node. This model attains the graph exploration with zero-bit memory and \(O(\log \Delta )\) -bit storage, where \(\Delta \)  is the maximum degree of the network. Yet another example is the
the pebble-based algorithm proposed by Disser et al. [2]}, which is a graph exploration algorithm using \(O(\log \log n)\)  distinct pebbles. The \(k\) -pebble model
is one of the restricted versions of the standard storage model, where each
agent has \(k\)  distinguished pebbles, and can put and pick-up each pebble on
any node for leaving some information there. The conceptual idea of this algorithm
is very close to our result. The algorithm simulates a log-space Turing machine
in a distributed manner using \(O(\log \log n)\)  pebbles, and runs the Reingold's algorithm
on the simulated Turing machine. Since this model is incomparable to our \(O(1)\) -bit storage model, the technical contribution
of our result is definitely independent of this algorithm. In
addition, the simulation overhead of the algorithm by Disser et al. is unfortunately super-polynomial, while our result only
incurs the polynomial-time overhead. The polynomial-time graph exploration using \(O(1)\) -bit memory and \(O(1)\) -bit storage
has been shown to be solvable by Cohen et al.[3]}. The exploration algorithm
presented in that paper is actually the breadth-first search (BFS) by the agent.
Our DFS algorithm complements another side of very standard graph search algorithms.
Note that it is certainly possible to use the exploration algorithm by Cohen et al. as the building block of our
simulation algorithm for node serialization, instead of our lex-DFS algorithm. However, no general simulation technique
as our result is addressed there. The paper by Cohen et al.[3]} also presents the impossibility
of graph exploration by zero-bit memory agents if the storage size is \(o(\log \Delta )\)  bits, which is the basis of
the proof of Theorem REF .
A variety of
the exploration algorithms attaining different memory/storage complexities are also
presented in [5]}, but no algorithm there attains the complexity of
\(O(1)\) -bit memory and \(O(1)\) -bit storage.
