  It is widely accepted that every system should be robust in that ``small''
violations of environment assumptions should lead to ``small'' violations of
system guarantees, but it is less clear how to make this intuition
mathematically precise. While significant efforts have been devoted to
providing notions of robustness for Linear Temporal Logic (LTL), branching-time
logics, such as Computation Tree Logic (CTL) and CTL*, have received less
attention in this regard. To address this shortcoming, we develop ``robust''
extensions of CTL and CTL*, which we name robust CTL (rCTL) and robust CTL*
(rCTL*). Both extensions are syntactically similar to their parent logics but
employ multi-valued semantics to distinguish between ``large'' and ``small''
violations of the specification. We show that the multi-valued semantics of
rCTL make it more expressive than CTL, while rCTL* is as expressive as CTL*.
Moreover, we show that the model checking problem, the satisfiability problem,
and the synthesis problem for rCTL and rCTL* have the same asymptotic
complexity as their non-robust counterparts, implying that robustness can be
added to branching-time logics for free.
