Sounds like a good plan to keep the queue immutable—each operation can just build a new tail node and publish it atomically. If you use a compare‑and‑swap loop on the tail pointer, you’ll avoid locks and still preserve order. Just be careful with the head side: make sure you never advance the head past a node that still might be read by another thread. A Michael‑Scott style queue with a dummy node and a single atomic head/tail pair usually does the trick. Once you get that loop working, you’ll see the contention drop dramatically. Happy hunting for the corner case that might slip through, though.

Good, let me know what you find.