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 first compression history comprising a plurality of portions of data previously transmitted to a second device, each portion of data having a location identifier, the first compression history maintaining a first quantity of location identifiers; (b) creating, by the first device, an ordered list of location identifiers ordered by a time the first device last used a portion of data in a location corresponding to each location identifier to compress data streams transmitted to the second device, the first device placing at a front of the ordered list location identifiers to newly used portions of the compression history as the newly used portions are used to compress data streams transmitted to the second device; (c) receiving, by the first device from the second device, information identifying a second quantity of location identifiers stored on the second device's compression history that correspond to the first compression history of the first device; (d) determining, by the first device, the second quantity is less than the first 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 used portions of data for compression between the first device and the second device.