We argue for the development of efficient methods to update the data plane state of an SDN, while maintaining desired consistency properties (e.g., no packet should be dropped). We highlight the inherent trade-off between the strength of the consistency property and dependencies it imposes among rules at different switches; these dependencies fundamentally limit how quickly data plane can be updated. For one basic consistency property–no packet should loop–we develop an update algorithm that has provably minimal dependency structure. We also sketch a general architecture for consistent updates that separates the twin concerns of consistency and efficiency.