Network-policy updates have to be committed in a consistent way on distributed-controller software-defined networking. Otherwise, the network may experience unexpected transitory configuration states, which compromise the performance, the security or, even, the correct operation. In this paper, we propose a scheme that provides consistent policy updates without rule conflicts and transitory states. The main contributions are: (i) a protocol that serializes policy update commitments to provide consistency; (ii) a consensus interface proposal that facilitates controller agreements about the network configuration version; and (iii) an algorithm for checking if a new policy is an update, a refinement, or if it conflicts with already installed policies. We prove that our protocol achieves a global order for all policy updates and that our algorithm correctly composes all policies. Simulation results using real network topologies show that the proposed distributed policy update scheme achieves a per-packet consistent configuration with a low control message overhead.