A study is made of the stability of steady states of probabilistic cellular automata defined on countable graphs. An important class of states are the quasi-deterministic states in which the "error sets" are confined to small isolated sets in the graph. In particular, quasi-deterministic states of majority vote systems defined on trees are discussed and criteria for their existence and stability are obtained.