> What happens when two threads are trying to generate a new shared state?

Then you get to synchronize them.

All immutability guarantees is that the variable you're reading from isn't in some half-way state when read. If you have two threads trying to read and update, you can't guarantee the order those 4 operation happen in without some synchronization mechanism. Assuming the value/reference is atomic, it _also_ guarantees that the _last_ update wins and does not corrupt data. 

But if you need two threads to increment an immutable value by two, you need synchronization.