A centralized synchronization system synchronizes data stored in multiple devices distributed over a relatively unreliable network, to provide automatic recovery from synchronization failures. The synchronization system maintains a truth database indicating the true state of the data and action tables indicating actions to be performed on each of the devices during a next update of the data. Data is retrieved from the devices over the network, and actual states of the data are determined from the action tables and the retrieved data. The truth database and action tables are updated accordingly. An effective action table is then generated to account for any of the devices which were offline during the most-recent synchronization. The truth database and effective action tables are saved to a central database in an atomic transaction. The effective action tables are then used to update the data on the devices over the network.