What does it mean that an algorithm is sequential? This usually means that
the algorithm has the following two features. First, time is sequential.
The algorithm proceeds from some initial state to a state
, then
to a state
, etc., and the steps are atomic. Second, only a
bounded amount of work is done at each step. In principle, a single agent
is able to move the algorithm from
to
, then to
, etc..
In this section, we are interested in one-agent algorithms where the agent may perform a substantial amount of work at one step. We use variables to formalize such algorithms. It is intended that non-Reserve variables range over finite (better yet, feasible) domains, though exceptions are possible.
We do not assume any particular sequential order of executing one step of the algorithm. It is possible that this work involves plenty of parallelism and is implemented by a number of auxiliary agents. But on the natural level of abstraction of the given algorithm, those auxiliary agents are invisible, and in principle a single agent may execute the algorithm.