Although originally described in terms of symmetric Turing machines, that equivalent formulation is very complex, and the reducibility definition is what is used in practice.
They defined the symmetric Turing machine, used it to define SL, showed that USTCON was complete for SL, and proved that where L is the more well-known class of problems solvable by an ordinary deterministic Turing machine in logarithmic space, and NL is the class of problems solvable by nondeterministic Turing machines in logarithmic space.
Many more interesting complete problems were found, most by reducing directly or indirectly from USTCON, and a compendium of them was made by Àlvarez and Greenlaw.
The first nontrivial result for SL, however, was Savitch's theorem, proved in 1970, which provided an algorithm that solves USTCON in log2 n space.
Unlike depth-first search, however, this algorithm is impractical for most applications because of its potentially superpolynomial running time.
Although there were no (uniform) deterministic space improvements on Savitch's algorithm for 22 years, a highly practical probabilistic log-space algorithm was found in 1979 by Aleliunas et al.: simply start at one vertex and perform a random walk until you find the other one (then accept) or until |V|3 time has passed (then reject).
[4] False rejections are made with a small bounded probability that shrinks exponentially the longer the random walk is continued.
By replacing the random walk by a universal traversal sequence, Aleliunas et al. also showed that SL is contained in L/poly, a non-uniform complexity class of the problems solvable deterministically in logarithmic space with polynomial advice.
In 1989, Borodin et al. strengthened this result by showing that the complement of USTCON, determining whether two vertices are in different connected components, is also in RLP.
In 1992, Nisan, Szemerédi, and Wigderson finally found a new deterministic algorithm to solve USTCON using only log1.5 n space.
A few weeks later, graduate student Vladimir Trifonov showed that USTCON could be solved deterministically using
It is explicit in his paper (and those leading up to it) that they are primarily concerned with asymptotics; as a result, the algorithm he describes would actually take
Most obviously, all SL-complete problems are now in L, and can be gainfully employed in the design of deterministic log-space and polylogarithmic-space algorithms.