Gas is trapped in polar ice at depths of ~50--120 m and is therefore significantly younger than the ice in which it is embedded. The age difference is not well constrained for slowly accumulating ice on the East Antarctic Plateau, introducing a significant uncertainty into chronologies of the oldest deep ice cores (Vostok, Dome Fuji, and Dome C). We recorrelate the gas records of Vostok and Greenland Ice Sheet Project 2 (GISP2) cores in part on the basis of new CH4 data and use these records to construct six Vostok chronologies that use different assumptions to calculate gas age--ice age differences. We then evaluate these chronologies by comparing times of climate events at Vostok with correlative events in the well-dated Byrd ice core (West Antarctica). From this evaluation we identify two leading chronologies for the Vostok core that are based on recent models of firn temperature, firn densification, and thinning of upstream ice. One chronology involves calculating gas age--ice age differences from these models. The second, new, approach involves calculating ice depths in the core that are contemporaneous with depths in the same ice core whose gas ages are well constrained. This latter approach circumvents problems associated with highly uncertain accumulation rates in the Vostok core. The uncertainty in Vostok chronologies derived by correlating into the GISP2 gas record remains about ¿1 kyr, and high-precision correlations continue to be difficult.