You need atomic operations at the synchronization points, but you can build arbitrary complex data structures on top of it. For example a lock free tree will stay consistent even if a process dies in the middle of an update (you might need to garbage collect orphaned unpublished nodes).