bzip2 can exploit concurrency through pbzip2, can't it?
In practice it works, but it isn't pretty ;)
(context: I have had a situation where files created by pbzip2 on linux were not able to be decompressed with some library on .NET, but using lbzip2, they were. I never looked into the details.)