A key use of software-defined networking is to enable scale-out of network data plane elements. Existing replication techniques, however, can cause incorrect behavior. For example, we show that an IDS system which operates correctly as a single network element can erroneously and permanently block hosts when it is replicated. In this paper, we provide a system, COCONUT, for seamless scale-out of network forwarding elements; that is, an SDN application programmer can program to what functionally appears to be a single forwarding element, but which can be replicated behind the scenes. To do this, we identify the key problem with existing replication methods, causality violation, and tackle it through a practical and scalable implementation of vector clocks. We define a new notion of correctness that focuses on the network behavior observable by its users and prove the correctness of our algorithms, i.e., the user-perceived behavior of any COCONUT element implemented with a distributed set of concurrent replicas is provably indistinguishable from its singleton implementation. Finally, we build a prototype of COCONUT and experimentally demonstrate its correct behavior. We also show that its abstraction enables a more efficient implementation of network elements compared to a naive baseline.