This is pure just for interest question, any sort of questions are welcome.

So is it possible to create thread-safe collections without any locks? By locks I mean any thread synchronization mechanisms, including Mutex, Semaphore, and even Interlocked, all of them. Is it possible at user level, without calling system functions? Ok, may be implementation is not effective, i am interested in theoretical possibility. If not what is the minimum means to do it?

EDIT: Why immutable collections don't work.

This of class Stack with methods Add that returns another Stack.

Now here is program:

Stack stack = new ...;

ThreadedMethod()
{
   loop
   {
      //Do the loop
      stack = stack.Add(element);
   }
}

this expression stack = stack.Add(element) is not atomic, and you can overwrite new stack from other thread.

Thanks, Andrey