© 2001 by British Computer Society
| ||||||||||||||||||||||||||||||||||||||||||||||||||
Consensus-based Timestamps in Distributed Temporal Databases
1 Department of Information Systems, Wroc
aw University of Technology, Wyb. St. Wyspianskiego 27, 50-370 Wrocaw, Poland Email: thanh@pwr.wroc.pl
Distributed temporal databases play a very important role in representing and processing data. Because of the independence (autonomy) of the system sites, it often happens that different versions of data, which refer to the same subject, can be generated and stored in these sites. Thus we say that a data conflict takes place. In this paper we deal with solving conflicts of temporal data which represent the timestamps of occurrence of real-world events. We assume that the occurrence timestamp of an event is a moment of time and it is given in an indeterminate way in the sense that certain time interval, to which this timestamp belongs, is defined. A data conflict is then defined as a situation in which for the same event the system sites give different intervals containing its occurrence timestamp. The problem is how to determine the proper interval to which this timestamp should belong. We propose to solve this problem by determining a consensus timestamp of given timestamps for this event. With this aim we define three distance functions between time intervals. Next we generate five postulates for consensus choice and present their analysis, owing to which one can understand the dependence of a postulate from others and decide what postulate should be the criterion for consensus choice. As shown, the Kemeny's function is the best for time intervals' consensus choice. Finally, we present three algorithms for determining consensus satisfying Kemeny's postulate and give their proofs.
Received 15 October, 1999. Revised 17 April, 2001.