Using physical clocks for replication in MANETs

Abstract

When update-anywhere data replication is performed in a MANET, operations on replicated data are often executed concurrently. To achieve a global total ordering of all operations, we propose a hybrid timestamp mechanism that combines physical clocks and logical timestamps. Our approach overcomes the ordering problem that arises from imprecisely synchronized physical clocks. We overlay the timestamps of operations with a grid of time-slots. To order the operations, we use physical clocks for operations in different time-slots and logical clocks for operations within the same time-slot. We prove that our method guarantees a total ordering when using an appropriate grid width.