Parallel Dynamic Search
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.