This disclosure is directed to a fast and scalable concurrent queuing system. A device may comprise, for example, at least a memory module and a processing module. The memory module may be to store a queue comprising at least a head and a tail. The processing module may be to execute at least one thread desiring to enqueue at least one new node to the queue, enqueue the at least one new node to the queue, a first state being observed based on information in the tail identifying a predecessor node when the at least one new node is enqueued, observe a second state based on the predecessor node, determine if the predecessor node has changed based on comparing the first state to the second state, and set ordering in the queue based on the determination.