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 ? 
Parallel Dynamic Search
ds.algorithms;ds.data structures;dc.parallel comp;concurrency;dynamic algorithms
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.