Poor enqueueing performance was discovered when a priority queue with a ring queue policy had a large message backlog. Performance degraded quickly when messages of mixed priority were inserted into a queue with a large (more than 100,000) message backlog. The fix ensures disordered messages acquired by a consumer as part of a cluster update, but not yet acknowledged at the time a new member joins the cluster, are reordered. During normal operation, new messages are appended directly to the back of the priority queues because the order of arrival is known. Enqueueing performance is improved for priority ring queues containing large numbers of messages with mixed priorities.