Ok we switched back to smaller critical sections and using a PriorityBlockingQueue. We essentially have two locks in the TransactionInitPriorityQueue, but that's ok because they serve different purposes and will allow multiple threads to change the queue in different ways concurrently