  A canonical formalism and constraint analysis for discrete systems subject to
a variational action principle are devised. The formalism is equivalent to the
covariant formulation, encompasses global and local discrete time evolution
moves and naturally incorporates both constant and evolving phase spaces, the
latter of which is necessary for a time varying discretization. The different
roles of constraints in the discrete and the conditions under which they are
first or second class and/or symmetry generators are clarified. The (non-)
preservation of constraints and the symplectic structure is discussed; on
evolving phase spaces the number of constraints at a fixed time step depends on
the initial and final time step of evolution. Moreover, the definition of
observables and a reduced phase space is provided; again, on evolving phase
spaces the notion of an observable as a propagating degree of freedom requires
specification of an initial and final step and crucially depends on this
choice, in contrast to the continuum. However, upon restriction to translation
invariant systems, one regains the usual time step independence of canonical
concepts. This analysis applies, e.g., to discrete mechanics, lattice field
theory, quantum gravity models and numerical analysis.
