The invention provides a method and system for operating multiple communicating caches. Between caches, unnecessary transmission of repeated information is substantially reduced. Each cache maintains information to improve the collective operation of the system of multiple communicating caches. This can include information about the likely contents of each other cache, or about the behavior of client devices or server devices coupled to other caches in the system. Pairs of communicating caches substantially compress transmitted information. This includes both reliable compression, in which the receiving cache can reliably identify the compressed information in response to the message, and unreliable compression, in which the receiving cache will sometimes be unable to identify the compressed information. A first cache refrains from unnecessarily transmitting the same information to a second cache when each already has a copy. This includes both maintaining a record at a first cache of information likely to be stored at a second cache, and transmitting a relatively short identifier for that information in place of the information itself. A set of caches are disposed in a directed graph structure, with a set of root caches disposed for coupling to server devices and a set of leaf caches disposed for coupling to client devices. Both root caches and leaf caches maintain non-cacheable objects beyond their initial use, along with digests of the non-cacheable objects. When a server device returns identical information to a root cache, root caches can transmit only associated digests to leaf caches, avoiding re-transmitting the entire non-cacheable object.