  We propose an interacting many-body space-time-discrete Markov chain model,
which is composed of an integrable deterministic and reversible cellular
automaton (the rule 54 of [Bobenko et al, CMP 158, 127 (1993)]) on a finite
one-dimensional lattice Z_2^n, and local stochastic Markov chains at the two
lattice boundaries which provide chemical baths for absorbing or emitting the
solitons. Ergodicity and mixing of this many-body Markov chain is proven for
generic values of bath parameters, implying existence of a unique
non-equilibrium steady state. The latter is constructed exactly and explicitly
in terms of a particularly simple form of matrix product ansatz which is termed
a patch ansatz. This gives rise to an explicit computation of observables and
$k$-point correlations in the steady state as well as the construction of a
nontrivial set of local conservation laws. Feasibility of an exact solution for
the full spectrum and eigenvectors (decay modes) of the Markov matrix is
suggested as well. We conjecture that our ideas can pave the road towards a
theory of integrability of boundary driven classical deterministic lattice
systems.
