Description of problem:
Since lbzip2 performs sooooo much better on multi-core machines and given the prevalence of multi-core machines, it would be nice if lbzip2 could be installed *instead* of bzip2. I.e. satisfy the RPM dependency for bzip2.
Personally I agree, however this change proposal  was rejected  by engineering steering committee.
Is it time to re-propose the change? 5 years have passed since that last discussion. lbzip2 is 5 year more mature.
Has a library interface been implemented?
The original bzip2 was released 1996 I think, that's level of maturity lbzip2 can't achieve so the argument will be still quite relevant. However I would like to propose something different - can we implement "alternatives" for bzip2/lbzip2? I am not sure if this is the right term, but I mean /usr/sbin/alternatives for being able to switch between the two. Don't see this as a half-baked solution, it allows many people to try to switch and see if it works fine under various workloads. This change would probably require changes for both bzip2 and lbzip2 packages, I haven't implemented alternatives yet myself.
Using alternatives was actually the original proposal that was shot down.
Well, not really. It was proposed to "set higher priority for lbzip2 in alternatives" however what I think would be a good step forward would be only to provide alternatives and lbzip2 as opt-in.