1. A method for synchronizing compression histories shared between two devices, the method comprising: (a) storing, by a first device, a first compression history, the compression history comprising a plurality of portions of data previously transmitted to a second device, each portion of data having a location identifier; (b) creating, by the first device, an ordered list of location identifiers ordered by a time the first device last accessed a portion of data in a location corresponding to each identifier; (c) receiving, by the first device from the second device, information identifying a quantity of location identifiers of a corresponding second compression history on the second device; (d) determining, by the first device, the received quantity is less than a quantity of location identifiers of the first compression history by a first amount; and (e) selecting for obsolescence, from the list of location identifiers, the first amount of location identifiers at an end of the ordered list corresponding to least recently accessed portions of data.