Parallel Dynamic Search Is there a natural parallel analog to red-black trees with similar or even not-terribly-worse properties for updates while being reasonably work-efficient ? 

More generally, what's the best we can do for parallel search with updates ?
From what I can tell, strategies involve relaxing balance conditions, then performing rebalancing updates in bursts.  Here is a paper from Hanke et al., 1997 [PDF], which I think focuses on their technique of aggregating and resolving update operations so that they can be performed concurrently.