The winner is determined by serialization. Redis is single-threaded. It processes commands one by one from a queue.
Even if two requests leave the users' devices at the exact same time, physical constraints (network routing, switch buffers, OS kernel interrupts) ensure they arrive at the Redis "door" in a single file line. Redis never executes two commands in parallel.
Packets travel over wires. Physics dictates they cannot occupy the exact same space on the wire/port. The OS network stack puts them in a receive buffer.
Redis reads from the OS buffer. The first readable command goes into the execution slot. The second must wait, even if it's just for 0.0001ms.
Because they are processed sequentially, the first one executes SET NX and succeeds. By the time the second one runs, the key exists.
Visualize the single-threaded event loop in slow motion.