The ReplicationQueue has an exposure to distributing items out of order. The ReplicationQueue may flush items in either of 2 ways. One way is the background thread provided by a ThreadPoolExecutor flushing on a timer. The other is via the current thread that does a put (which calls ReplicationQueue.add). In the case of the call to add if it hits the max size (set in the config by replQueueMaxElements) then items may get flushed to other nodes out of order. This is not evident when a test case only includes puts (new items or updated items in a cache). Your test must include removals to expose this concern.