A network element includes multiple ports, a memory, multiple processors and cache-flushing circuitry. The multiple ports are configured to serve as ingress and egress ports for receiving and transmitting packets from and to a network. The memory is configured to store a forwarding table including rules that specify forwarding of the packets from the ingress ports to the egress ports. The multiple processors are configured to process the packets in accordance with the rules. The two or more cache memories are each configured to cache a respective copy of one or more of the rules, for use by the multiple processors. The cache-flushing circuitry is configured to trigger flushing operations of copies of rules in the cache memories in response to changes in the forwarding table, and to reduce a likelihood of simultaneous accesses to the forwarding table for updating multiple cache memories, by de-correlating or diluting the flushing operations.