Computing a matching in a graph is one of ``the hardest simple problems'' in computer science. It is simple since most variants of matching can be solved in polynomial time, yet hard because the running times are high and the algorithms are sophisticated. It is even more challenging to design parallel algorithms for matching, since many algorithms rely on searching for long paths in a graph, or implicitly communicate information along long paths, and thus have little concurrency. 

We describe new approximation algorithms for variant matching problems and the related edge cover problem. For b-Matching, we obtain a ½-approximation algorithm; and for b-edge cover, we describe a 3/2-approximation algorithm. Both algorithms have been implemented on multicore machines, and we report results from thousands of cores. We also show how to solve data privacy problems using these algorithms.