Which decompression algorithms are safe to use on attacker-supplied buffers?

I want to save network bandwidth by using compression, such as bzip2 or gzip.

Attackers, as well as normal users, may send compressed messages.

Are there sequences of bytes which will cause some decompression functions to become stuck in an infinite loop, or to use vast amounts of memory?

Is so, is this a fundamental property of those algorithms, or just an implementation bug?

I can only speak for zlib's inflate. There is no input that would result in an infinite loop or uncontrolled memory consumption.

Since the maximum compression of deflate is less than 1032:1, then inflate when working normally can expand up to almost 1032:1. You just need to be able to handle that possibility.