This is perhaps an unnecessary clarification, but there's plenty of non-determinism that's perfectly fine. Data races are non-deterministic and bad, but "non-determinism" itself is not a scare word.

I spent a good decade of my career writing C#, which is similar enough to Java for these discussions, and the strlen issue I talked about is not limited to C -- it is also an issue for a managed language like C# or Java. I think you would do well to discuss the problem, instead of dismissing it because myself and the original post I referenced are tainted by the nasal demons of undefined behavior in C. Don't use that as an escape hatch from dealing with the general issue presented in the problem.

I know of no language in existence where even in the face of data races, there is a guarantee that all data invariants are maintained otherwise an exception is thrown. Note that Rust is not such a language, as its goal is to make data races compilation errors, but unsafe code can introduce data races that do not generate compilation errors.

I would also suggest you offer even a sketch of a fix for the String(char[]) constructor if you think that is the source of the bug. I don't think one is possible. I'm not aware of any method to unilaterally atomically copy an unbounded char[], for example. Even if there is, I suggest you go look for other functions that take other kinds of mutable objects as parameters -- I doubt that for each and every case there is a method to unilaterally atomically deep copy those objects. Such copying is just one suggestion, feel free to resolve it any way you think works.

If you don't want to sketch a solution, another experiment you can try is to use a non-thread-safe mapping type like TreeMap, and make structural modifications (add/remove elements, not just modify existing values) from multiple concurrent threads without any synchronization. Can you guarantee that in all cases where invariants are broken, that an exception will be thrown?

I think it would be prudent to do something in intern(), and one could arguably call this a bug in intern(). The string intern table is invisibly and pervasively read shared state, and relatively uncommonly mutated. It would make sense to take extra care when mutating the shared state to attempt to ensure no invalid strings are added.