  Software-defined networking (SDN) is a novel paradigm that out-sources the
control of packet-forwarding switches to a set of software controllers. The
most fundamental task of these controllers is the correct implementation of the
\emph{network policy}, i.e., the intended network behavior. In essence, such a
policy specifies the rules by which packets must be forwarded across the
network.
  This paper studies a distributed SDN control plane that enables
\emph{concurrent} and \emph{robust} policy implementation. We introduce a
formal model describing the interaction between the data plane and a
distributed control plane (consisting of a collection of fault-prone
controllers). Then we formulate the problem of \emph{consistent} composition of
concurrent network policy updates (short: the \emph{CPC Problem}). To
anticipate scenarios in which some conflicting policy updates must be rejected,
we enable the composition via a natural \emph{transactional} interface with
all-or-nothing semantics.
  We show that the ability of an $f$-resilient distributed control plane to
process concurrent policy updates depends on the tag complexity, i. e., the
number of policy labels (a.k.a. \emph{tags}) available to the controllers, and
describe a CPC protocol with optimal tag complexity $f+2$.
