I assume that you mean parallelizability of decoding and not of encoding. JPEG's decoding is poorly parallelizable: the entropy decoding is necessarily serial;

I assume that you mean parallelizability of decoding and not of encoding. JPEG's decoding is poorly parallelizable: the entropy decoding is necessarily serial; only inverse FFTs can be parallelized. Sharing the data about boundaries need not hamper parallelizability in its most simple meaning: imagine a format where we first encode some data for each boundary, and then we encode all the blocks that can only be decoded when provided the data for all its four boundaries. However, what often matters is the total number of non-cacheable memory roundtrips that each pixel/block of the image has to take part in: a large cost during decoding is memory access time. If we assume that a single row of blocks across the whole image is larger than the cache, then any approaches similar to the one I described in the previous paragraph add one roundtrip. Another consideration is that a single block is often too small to be a unit of parallelization -- parallelizing entropy decoding usually has additional costs in filesize (e.g. for indices), and any parallelization has startup costs for each task. The end-result is that a reasonably useful approach to parallelization is to split the image into "large blocks" that are large enough to be units of parallelization on their own, and encode _those_ independently.