System and methods for synchronizing datasets in a communication environment having high-latency or other adverse characteristics6460051Abstract A system and methods for synchronizing information in datasets via a communication medium are provided that are suitable for synchronizing even across communication mediums that are susceptible to high latency, non-FIFO (non-First-In-First-Out) delivery order, or other adverse characteristics. According to an aspect of the invention, in an information processing system, a method for synchronizing a first dataset with at least a second dataset via a communication medium includes a step of storing information that is indicative of a first version of user data of the first dataset, wherein the first version has been involved in prior use for synchronizing with the second dataset. The method further includes steps of identifying a change in the second dataset that is new relative to the first version of the user data of the first dataset; via the communication medium, communicating the change in the second dataset and indicating the first version based on the stored information; determining whether user data currently in the first dataset has changed relative to the first version that was indicated in the communicating and indicating step; deciding whether to commit the communicated change to the first dataset based at least in part on the determining step; and committing the communicated change to the first dataset if the communicated change is decided to be committed in the deciding step. Claims What is claimed is: Description BACKGROUND OF THE INVENTION
Time 1: The server sends changes A1 and B1 reflecting current
server records A and B, respectively.
Time 2: Record B is modified in the server.
Time 3: The server then sends a new change B3 reflecting the
current server record B.
If the client receives the change B3 before changes A1 and B1 (i.e., in non-FIFO order), the client should commit the change B3 (e.g., immediately) such that the corresponding client record also reflects the server record of Times 2 and 3. When the client later receives the changes A1 and B1 (i.e., in non-FIFO order), the client should still commit the change A1 (e.g., immediately), but should ignore the change B1. 2. The Preferred Solution: Use Change, But Refrain If Harmful FIG. 4A is a flowchart that shows a method 400 for transferring and handling dataset changes during synchronization to handle non-FIFO delivery. The method 400 embodies the above-introduced preferred solution for ordinarily using changes received out of FIFO order, unless they were received out of FIFO order versus later-sent changes involving the same record, in which case they are specially handled (e.g., discarded). The method 400 includes a step 410, in which the sender (e.g., the server) sends a change R1 that involves a record R in the sender and includes in the sending an indicator S1 of the version of the record R that is reflected in the change R1, e.g., an indicator S1 of send order. Preferably, the version indicator S1 is the change send time of the change R1 according to the sender's clock. Later, in a step 415, the sender sends a change R2 involving the same record R in the sender's dataset, and includes in the sending an indicator (e.g., send time) S2 of the version of the record R reflected in the change R2. Between the steps 410 and 415, the GUD record R may or may not have changed; i.e., the sent change R1 and R2 may or may not be different changes. A single send time may be sent as the version indicator for a group of changes that are considered to be sent at the same time. In an alternative embodiment, the modification time according to the sender's clock of each record is, used as the record's version indicator, instead of the send time. At some time after step 410 or step 415 or both, in a step 420, the recipient (e.g., client) receives a change (e.g., R1 or R2) along with a send version indicator (e.g., S1 or S2) for the received change. The received change corresponds to a record RR in the recipient's dataset. Next, in a step 425, the recipient compares the received send version indicator (e.g., R1 or R2) with a previously-received send version indicator (e.g., the other of R1 or R2) that the recipient has previously stored as a part of the status of the recipient record RR. If the received version indicator indicates a version that is no later than the previously-received version, then the received change is obsolete, and is subject to special handling in a step 430. Otherwise, the received change is not obsolete, and is subject to ordinary handling in a step 435. Special handling in the step 430 preferably means that the recipient discards the received change, and will not acknowledge its correct receipt to the sender (e.g., if requested). Under ordinary handling in the step 435, the recipient stores the received sender version indicator as the recipient record RR's stored latest sender version indicator (for the particular sender) and, if the recipient finds no further reason to discard or otherwise specially handle the received change from the sender, then the recipient acknowledges receipt of the received change (e.g., when asked to acknowledge by the sender) and propagates the received change to the recipient's dataset in the ordinary way. Additional details underlying the steps of the method 400 will be discussed in later section(s). 3. Illustration of the Preferred Solution in a Synchronization Method FIGS. 4B and 4C together are a flowchart that shows a synchronization method 450 according to the preferred embodiment. The method 450 is essentially the synchronization method of FIG. 3 (which handles received changes that affect fresh records, e.g., under high communication latency) supplemented and combined with the method of FIG. 4A (which handles dataset changes that may be delivered in non-FIFO order). It's worth noting that the method 300 of FIG. 3 and the method 400 of FIG. 4A each uses for its own purpose version indicators associated with sent changes. The method 450 of FIGS. 4B and 4C preferably uses the same type of version indicator (namely, send times) both for the purpose of the method 300 and for the purpose of the method 400, as shown in FIGS. 4B and 4C, but is not restricted to using the same type of version indicator for both purposes. As with the method 300 of FIG. 3, the method 450 that starts at FIG. 4B includes a step 310, in which the client identifies client record changes that are fresh versus the server. The step 310 is followed by a step 315A, in which the client sends these fresh client record changes and their client version indicator(s) (preferably, their send time(s)) to the server. In the step 315A, the client version indicator(s) are being sent both for the purpose of the method 300 and also for the purpose of the method 400. The step 315A is essentially the step 315 from FIG. 3, in the preferred embodiment. The server receives and processes these client changes in the step 320A. The step 320A is essentially the step 320 from FIG. 3, supplemented and combined with the steps 425, 430, and 435 from FIG. 4A to handle client changes received in non-FIFO order. The step 320A includes sub-steps 455, 425A, 430A, and 435A. In the step 455, the server receives the client changes and their client version indicator(s). For each received client change, the server in a step 425A compares the received client version indicator with a highest previously-received version indicator from this client that the server has previously stored as a part of the status of the corresponding GUD record. If the received version indicator indicates a version that is no later than the previously-received version, then the received change is obsolete, and is subject to special handling in the step 430A. Otherwise, the received change is not obsolete, and is subject to ordinary handling in the step 435A. Special handling in the step 430A preferably means that the server discards the received change, and will not acknowledge its correct receipt to the client (e.g., if requested). Under ordinary handling in the step 435A, the server acknowledges receipt of the client changes to the client (e.g., if asked) if no errors are encountered; performs conflict resolution on the received changes versus any changes in the GUD; propagates the client changes that survive conflict-resolution into the GUD; and stores in the GUD, for the GUD record corresponding to the client change, the version indicator of the client change, against which the GUD record is now conflict-free (e.g., conflict-resolved). Note that the conflict resolution performed by the server in the step 435A preferably includes automatic, timestamp-based conflict resolution (e.g., latest change always wins) that involves comparison of timestamps from different clocks. If such conflict resolution were guaranteed to be always possible (e.g., all timestamps from all datasets are guaranteed to be convertible into a common time for correct, meaningful comparison), then the step 320A may optionally be replaced with the step 320 of the method 300 of FIG. 3. In general, the methods 900 and 950 may be operated, without requiring comparison of timestamps from different clocks and without requiring user input, independently of whatever conflict-resolution method is used. In particular, the version indicators stored in the steps 435, 435A, and 435B for a record are maintained, in anticipation of a next reception of a change for the record from the sender dataset, even after the record in the recipient dataset gets overwritten by values from a dataset other than the sender dataset, should such an overwriting occur. The method 450 continues at FIG. 4C. After the server has received and processed the client changes in the step 320A, it identifies GUD changes that are fresh versus the client in a step 323. The server sends the fresh GUD changes to the client in a step 325A and includes in the sending, for each GUD record, the client version indicator (similarly to the step 325 of the method 300) and also the server version indicator (similarly to the step 410 or 415 of the method 400). The step 325A essentially corresponds to the step 325 of the method 300 combined with the step 410 or 415 of the method 400. In a step 330A, the client receives the GUD changes including the client version-indicator(s) of the GUD changes' last-known corresponding client records (similarly to the step 330 of the method 300) and also including the server version indicator (similarly to the step 420 of the method 400). The step 330A essentially corresponds to the step 330 of the method 300 combined with the step 420 of the method 400. The client handles each received GUD change via some or all of steps 425B, 335, 430B, and 435B. In the step 425B, the client compares the received server version indicator for the each GUD change with a latest server version indicator that was previously received and stored by the client. If the received version indicator indicates a version that is no later than the latest server version previously received, then the received GUD change is obsolete, and is subject to special handling in the step 430B. Otherwise, the received GUD change is not made obsolete by a later-sent but earlier-received change from the server, and the client proceeds to the step 335. In the step 335, the client determines, from the client version indicator for the received GUD change, whether the GUD change is conflict-free from the server with respect to the current version, or an earlier version, of the corresponding client record. For example, if the corresponding client record has changed since the version indicated by the received version indicator, then the GUD change is conflict-free with respect to an earlier version of the client record. If this is the determination, then the GUD change is suspect and in the step 430B is subject to special handling. If not, then the GUD change is conflict-free (e.g., conflict-resolved) with respect to the current version of the client record, and the GUD change in the step 435B is subject to normal handling. For simplicity, special handling in the step 430B preferably means that the client discards the GUD change, and will not acknowledge its correct receipt to the server (e.g., if asked). Under normal handling in the step 435B, if the client finds no further reason to discard or otherwise specially handle the received GUD change, then the client acknowledges receipt of the GUD change (e.g., if asked to), stores the received server version indicator as the latest server version indicator that has been received in connection with the GUD change's corresponding client record, and propagates the GUD change to the client dataset in its ordinary way. The step 430B essentially corresponds to the step 340 of the method 300 and also the step 430 of the method 400. The step 435B essentially corresponds to the step 345 of the method 300 combined with the step 435 of the method 400. Additional details underlying the steps of the method 450 will be discussed in later section(s). C. Problem: Chatty Protocols Unfit for High-Latency Synchronization 1. Introduction: Characterizing Chattiness Using Concept of "Ply" As has been discussed, chatty protocols, i.e., protocols that require numerous sequential communication exchanges, are unsuitable for use in synchronizing across communication environments. To discuss the chattiness of synchronization protocols, the term "ply" will be used. The concept of "ply", as introduced in this document, is used to characterize the chattiness of any conversation or exchange of messages between two parties. For example, consider a scripted dramatic dialog between two actors in which only one actor speaks at a time. Each uninterrupted set of utterances by one actor forms a "ply", and the script for the dialog can be characterized as an "N-ply" script. For another example, consider an exchange of letters between two parties, Albert and Betty, by mail. Suppose Albert and Betty each has an agenda, or algorithm, for the overall exchange of letters. For example, Albert's algorithm might be: A1) I will send a letter describing my vacation and asking about Betty's vacation; A2) I will send a letter describing my favorite food; and A3) If Betty replies that her vacation was spent in California, then I will send a letter describing my childhood spent in California. Betty's algorithm might be: B1) I will await a query from Albert and send a letter replying to that query; and B2) I will send a letter describing my first automobile. The algorithms for Albert and Betty can completely "finish" most quickly if the letters of A1, A2 and B2 are sent immediately, to constitute a first ply; the letter of B1 is sent after receipt of the letter of A1, to constitute a second ply; and the letter of A3 is sent after receipt of the letter of B1, to constitute a third ply (assuming that Betty's vacation was spent in California). Thus, the letter-writing algorithm for Albert and Betty is a three-ply algorithm. Speaking more generally, the set of synchronization messages needed to conduct a synchronization according to a synchronization protocol/algorithm may be grouped into a sequence of plies. Each ply is a group of messages having the following defined property: once all messages in a ply in the sequence have been fully received and processed, then (assuming there are no errors) there is no further restriction that prevents any message of the immediately next ply in the sequence from being sent. Thus, if all synchronization messages in a ply of an N-ply protocol are modeled as being sent simultaneously and processed by the communication network simultaneously, then the communication network contributes only about N transmission latencies of delay to the synchronization (one respective transmission latency per ply), assuming that no errors occur. 2. Constant-Ply Solution Reduces Chattiness And Maintains Reliability Prior synchronization schemes that requires each record to be individually requested and sent via a communication network can require an unlimited number of plies, e.g., more than thousands or tens of thousands of plies, depending on the number of records being synchronized. In contrast, synchronization methods of the present invention do not require numerous sequential communication exchanges--i.e., do not require numerous plies. Generally, synchronization methods of the present invention allow merely a constant number of plies to be used for synchronization for any amount of data to be synchronized, assuming no errors. In any event, the number of plies needed for synchronization according to the present invention needs not grow linearly with the number of data records being synchronized, in contrast to synchronization methods that requires each record to be individually requested/transmitted in sequence across a communication medium. Significantly, even if errors (e.g., communication errors) do occur, synchronization methods of the present invention can still maintain proper state, avoid loss of data, recover, and determine and optionally convey to the user the current state of synchronization. 3. The Six-Ply Solution FIG. 5A is a diagram that depicts the communication between a client and the server for a six-ply synchronization method 500 according to the present invention. The six-ply synchronization method 500 includes six plies (groups) 501-506 of synchronization communications in sequence. Each of the six sequential plies 501-506 is shown in FIG. 5A with an arrow (from which the labels "501"-"506" extend) that represents the transmission of a set of messages for the ply (and therefore represents transmission latency for the ply). In one embodiment, each ply of communications is sent as a single (perhaps large) message (e.g., e-mail or pager message). In such an embodiment, each ply is not sent until the entire previous ply is received. If one side of the synchronization sends a ply of communications that requires a reply, but does not receive a responding ply of communications, then the side would re-send its entire ply. In another, preferred embodiment, the communications within each ply are sent individually, and preferably in order (top to bottom in FIG. 5A). Ideally, all such communications arrive at the intended recipient and in FIFO order, and the recipient processes communications, in order, as soon as they are received. However, the beauty of the present invention is that, in part because of the robustness and flexibility of the synchronization protocol (further described in later sections) according to the present invention, even if some communications get lost or arrive out of FIFO-order, the communications that do arrive are processed, if possible, and all sides (e.g., both sides) of the synchronization maintain proper state without permanently losing data. Sending communications of a ply individually has advantages, such as the advantage that small messages are less susceptible than large messages to transmission failure in wireless paging and other communication mediums. In the first ply 501, the client sends 520A client record change(s) (e.g., additions, modifications, deletions) to the server. The client also sends 524A request(s) for acknowledgment of receipt of the sent client record change(s). The server receives (521A, 525A, respectively) the client record change(s) and the request(s) for acknowledgment of the client record change(s). In the second ply 502, the server responds by sending 528A acknowledgment(s) of received client record change(s) to the server. The client receives 529A the acknowledgment(s). In the third ply 503, the client sends 532A a request for the server's (GUD's) fresh record change(s) to the server. The server receives 533A the request. In the fourth ply 504, the server responds by sending 536A GUD record change(s) (e.g., additions, modifications, deletes) to the client. The server also sends 540A request(s) for acknowledgment of receipt of the sent GUD record change(s). The client receives (537A, 541A, respectively) the GUD record change(s) and the request(s) for acknowledgment of the GUD record change(s). In the fifth ply 505, the client responds by sending 544A acknowledgment(s) of received GUD record change(s) to the server. If the received GUD record change(s) include record addition(s), the sent acknowledgment(s) would include new record mapping(s), e.g., client record ID(s), for client record(s) that were newly added in response to the received GUD addition(s). If the acknowledgment(s) include new record mapping(s), the client sends 548A request(s) for acknowledgment of receipt of the sent new record mapping(s). The server receives (545A, 549A, respectively) the acknowledgment(s), including any new record mapping(s), and any request(s) for acknowledgment of the new record mapping(s). In the sixth ply 506, the server responds by sending 552A acknowledgment(s) of received new record mapping(s) to the server. The client receives 553A the acknowledgment(s). 4. The Four-Ply Solution FIG. 5B is a diagram that depicts the communication between a client and the server for a four-ply synchronization method 570, according to the present invention, that includes four plies 571-574 of synchronization communications. The four-ply synchronization method 570 resembles the six-ply synchronization method 500 of FIG. 5A, and the steps of FIG. 5B are numbered similarly to similar steps in FIG. 5B. As with the six-ply method 500 of FIG. 5A each ply of communications may be sent as a single (perhaps large) message (e.g., e-mail or pager message), or the communications within each ply are sent individually, and preferably in order (top to bottom in FIG. 5B). The four-ply method 570 performs a full synchronization using only four plies of communications. In the first ply 571, the client sends 520B client record change(s) (e.g., additions, modifications, deletes) to the server. The client also sends 524B request(s) for acknowledgment of receipt of the sent client record change(s). The client also sends 532B a request for the server's (GUD's) fresh record change(s) to the server. The server receives (521B, 525B, and 533B, respectively) the client record change(s), the request(s) for acknowledgment of the client record change(s), and the request for the server's fresh record change(s). In the second ply 572, the server responds to the request of the step 524B by sending 528B acknowledgment(s) of received client record change(s) to the server. The server also responds to the request of step 533B by sending 536B GUD record change(s) (e.g., additions, modifications, deletes) to the client. The server also sends 540B request(s) for acknowledgment of receipt of the sent GUD record change(s). The client receives (529B, 537B, and 541B, respectively) the acknowledgment(s) of received client change(s), the GUD record change(s), and the request(s) for acknowledgment of the GUD record change(s). The third and fourth plies 573 and 574 resemble the fife and sixth plies 505 and 506 of the method 500 of FIG. 5A and need not be laboriously described again. 5. The Nominally-Two-Ply Solution FIG. 5C is a diagram that depicts the communication between a client and the server for a nominally two-ply synchronization method 580 according to the present invention. The nominally two-ply synchronization method 580 includes two plies 581 and 582 of synchronization communications in sequence. The two-ply synchronization method 580 resembles the four-ply synchronization method 570 of FIG. 5B, and the steps of the two-ply method of FIG. 5C are numbered similarly to similar steps in FIG. 5B. The nominally two-ply synchronization method 580 differs from the four-ply synchronization method 570 in that the last two plies 573 and 574 of one synchronization are combined with the first two plies 571 and 572, respectively, of a next synchronization, to form the nominally two-ply synchronization method 580. This is a form of pipelining the four-ply synchronization method 570 to provide higher synchronization throughput. Put another way, this is a way of starting a new synchronization before the previous synchronization has fully ended, i.e., before all exchanged records of the previous synchronization have been fully mapped to each other in the server's internal database. The nominally two-ply synchronization method 580 can be advantageously employed to repeatedly synchronize (e.g., perpetually synchronize) a dataset that undergoes frequent changes. For example, a client may be programmed to check for fresh client changes or acknowledgment requests (e.g., requests for mappings) according to a user-settable schedule (e.g., every N minutes, where N is user-settable and defaults, e.g., to thirty), and if such fresh changes or requested acknowledgments are found, the client initiates the method 580 by sending the transmissions of the first ply 581. For another example, a client may be programmed to initiate the method 580 as soon as it detects that the server has become reachable via the communication medium, e.g., as soon as the server has come into transmission range. D. Allowing Flexible (e.g., Partial) and Asynchronous Synchronization Synchronization methods according to an embodiment of the present invention include flexibly performing synchronization transactions at will (e.g., at the user's discretion) outside the context of a full, two-phased synchronization in which dataset(s) being synchronized are locked against user changes during synchronization. For example, the user's wireless (client) device includes a simple "send changes" command (e.g., a button), that when invoked by the user, sends all fresh client changes (or only fresh changes involving a set of user-selected records) to the server, without invoking return changes from the server. (Changes in a client dataset are fresh with respect to the server if, for example, they include values or status, e.g., "deleted", that the server may not have seen before.) For another example, the client device includes a simple "get changes" command (e.g., a button) that, when invoked by the user, requests all fresh GUD changes (or only fresh changes involving a set of user-selected records) from the server, without first requiring that all fresh client changes have already been sent to the server. (Changes in the server dataset are fresh with respect to a client if, for example, they include values or status, e.g., "deleted", that the client may not have seen before.) Further, these free-form transactions are performed without needing to lock the client dataset against user modification for any user-appreciable lengths of time (; e.g., any processing delays are much shorter than the maximum possible transmission latency encountered by synchronization signals.) Still further, these free-form transactions are performed even if the client is a simple one that does not ordinarily perform conflict resolution locally but relies on the server to provide conflict resolution. These free form transactions may be controlled by user input to the synchronization system (e.g., to the server or to a client accessor) for initiating synchronization. The user input may specify transactions (e.g., "send changes", "get changes", "synchronize") either for immediate execution or for timed execution (e.g., "synchronize at 2:00 am"). Such free-form transactions may be implemented for example by freely undertaking the "plies" of transmissions in the methods 500, 570, or 580 in an asynchronous or connectionless manner. E. Sent Changes/Signals Get Lost: A Non-Chatty Solution is Provided During the synchronization process, dataset changes and other signals are sent between a client (dataset accessor) and the server (synchronizer core). As is described elsewhere in this document, these changes/signals may be sent in multiple batches. Due to the limitations of the communication system used, some batches may get lost. A solution to this problem according to the present invention involves seeking acknowledgment from the other side for sent (batches of) changes/signals. However, in a high-latency environment, it is not desirable to await acknowledgment of each batch before sending the next batch. Therefore, as will be further explained, preferred synchronization methods according to the present invention ensure robustness against lost changes/signals by using acknowledgments, but do not generally require a linear, in-sequence confirmation of each batch of communications before other synchronization communications can be sent or processed. Rather, a (less-chatty) asynchronous, pipelined communication/synchronization scheme is used, in which robustness against lost changes/signals is still maintained. The methods 500, 570, and 580 embody this design approach. F. Single Framework For Various Synchronization Styles As has been mentioned, the present invention permits and includes in its embodiments a variety of synchronization methods of various styles or modalities (e.g., partial, six-ply, four-ply, nominally-two-ply, and the like). These different methods may be chosen according to the particular circumstances and needs for a given synchronization or synchronization client. According to the present invention, a single, highly-flexible synchronization protocol framework (including, e.g., "action objects", which will be further discussed) is used to realize the various synchronization methods, as will be further described in later sections. For example, the methods of FIGS. 3, 4A-C, and 5A-C are all preferably all implemented using a same underlying synchronization protocol framework (e.g., "action objects"), as will be further described, according to the present invention. G. Hiding Complexity from Clients, As Appropriate For Clients' Capabilities The present invention is capable of largely confining complexity into the synchronization engine and away from the client's side of the communication channel under certain conditions. Such a capability is helpful if very simple client datasets are to be supported. In particular, the conflict-resolution (including duplicate-resolution) task is preferably confined if and when possible to the synchronizer core because the synchronizer core can devote substantial resources (e.g., field-based priorities, other extensive status information, processing power, and the like, etc.) to the task. Under this preferred division of labor, the client generally receives changes that are known to be conflict-resolved with respect to a previous state of the client. Depending on the capabilities, limitations, or needs of particular client datasets, however, the present invention may allow functionality such as conflict resolution to be delegated to the client's side of the communication channel, but preferably with assistance or supervision from the synchronizer core, as will be further described below. IV. A More Detailed Discussion: Re-Introduction to Synchronization A. Datasets, Records, and Synchronization Datasets are collections of data. According to the present invention, the purpose of synchronizing two, or more than two, datasets is to update them as necessary with data from one another so that they contain the same or equivalent data (generally, the latest data), at least in the portions of the datasets that the user has designated for synchronization. Each dataset may be organized into individual data records. For example, a dataset having contact information may be organized into records, including a record listing a "Bill Smith's" phone numbers and addresses and another record listing a "Ted Brown's" phone numbers and addresses. In general, if records have been added to any dataset before a synchronization, then equivalent records are added to the other datasets as a result of the synchronization. Also, generally, if modifications or deletions of records have been made to one dataset before the synchronization, then equivalent modifications and deletions of corresponding records are made to the other datasets as a result of the synchronization. (The preceding discussion of synchronization according to the present invention becomes more complicated if conflicts or duplicates are present. Conflicts and duplicates are further described in later sections.) B. Record Files, Data Types, Data Fields, etc. In synchronizing two, or more than two, datasets, a correspondence is generally established between particular records across the datasets. For example, a contact record for "Bob Smith, of Acme Widgets" may exist in every dataset (perhaps as a result of synchronization), and these records in different datasets may correspond to one another. The records in a dataset may be of various data types, for example, a time-zone type, a contact type, a calendar-entry type, a task (or "to do"-list-entry) type, a memo type, an electronic-mail type, or other types. In general, each record may include data organized into one or more data fields. For example, a contact-type record may include data for a "last name" field, a "first name" field, a "company" field, and many other fields. For many typical data types, it is not necessary for each record of the data type to have data for every possible field. For synchronization, a correspondence is typically established between particular data fields across datasets. For example, a "title" field for contact records in one dataset may correspond to a "Job Title" field for contact records in another dataset. In general, the systems and methodologies of the present invention can be adapted to work with any one type of data, or with any multiple types of data, and with arbitrarily defined or named data fields. Within a dataset, the records of a particular data type may further be organized into one or more groups that are here referred to as record files. Examples of record files include "Cardfiles" in Starfish's Sidekick.RTM. PIM or "folders" in Microsoft's Outlook PIM. A preferred embodiment of the invention allows the user to specify an arbitrary correspondence, or mapping, of particular record files of the same data type in different datasets to each other. For example, the user may specify that a record file named "Business Contacts" in a first dataset, a record file named "Contacts" in a second dataset, and a record file named "Customer List" in a third dataset be mapped to one another. Separately, the user may specify that only a record file named "Calendar" in the first dataset and a record file also named "Calendar" in the third dataset be mapped to each other. As demonstrated by the preceding example, a user-specified synchronization of multiple datasets by the preferred embodiment may include a number of separate synchronizations, each of which synchronizes a set of mutually-mapped, or corresponding, record files. Each synchronization of corresponding record files does not necessarily involve all of the multiple datasets. Each synchronization of corresponding record files also need not necessarily involve the same datasets as other synchronizations of other record files. For simplicity only, unless otherwise stated or unless context demands otherwise, discussion of synchronizing datasets may use language as if to assume that all datasets involved in the synchronization each contains exactly one record fie that is mapped to the one record file of all other datasets involved. It is to be understood that this simplification, and other simplifications made for ease of description, are not meant to limit the scope of the invention. C. Record Transformations When performing synchronization, a synchronization system transforms records from one dataset's representation into another dataset's representation. For example, the system may transform from an Internet Sidekick.RTM. cardfile for business contacts into a synchronization-system-internal representation. Typically, there is a one-to-one relationship between records in the source and target datasets. If this is not the case, however, the component of the system that interacts with a non-conforming dataset (e.g., a dataset accessor) includes logic to handle this non-conformity. D. Field Mapping Types and Field Conversion Types Record transformations are a combination of field mappings and conversions from a source record to a target record. It is often the case that there are significant differences in the number, size, type and usage of fields between two datasets in a synchronization relationship. The specification of transformations generally depends on the particular datasets involved, and may be user configurable, with the synchronization system providing defaults. In a specific embodiment, the following types of field mappings are supported.
1. Null Source field has no equivalent field in the target
dataset and is ignored during synchronization.
2. One-to-One Map exactly one field in the target to one field in
the source.
3. One-to-Many Map one field in the target to many fields in the
source, such as parse a single address line to fields
for number, direction, street, suite/apartment, or the
like.
4. Many-to-One Map several fields in the target to one field in the
source, such as reverse the address line mapping
above.
The following types of field conversions are supported.
1. Size Source field may be larger or smaller in size than
the target field.
2. Type Data types may be different, such as float/integer,
character vs. numeric dates, or the like.
3. Discrete Values A field's values may be limited to a known set.
These sets may be different from target to source
and may be user defined.
E. Conflicts and Duplicate Records In general, the user may make arbitrary changes to individual datasets and later synchronize the datasets. In general, each change made to a dataset (for example, addition, modification, or deletion of a record) by its user is propagated to other datasets as a result of a subsequent synchronization. However, it sometimes happens that two, or more than two, changes are in conflict with one another such that the changes cannot all be propagated without one change's undoing or otherwise interfering with another. Such changes give rise to a "conflict." For example, a conflict exists when a user has made a modification to a record in a first dataset, and has separately made a conflicting modification to the record's corresponding record in a second dataset. For a specific example, the user may have set a contact's (e.g., Bob Smith's) "title" field to "salesperson" in his handheld organizer device and separately set the corresponding contact's (Bob Smith's) "title" field to "Sales Manager" on the user's desktop PIM. Automatic and user-assisted methods for resolving conflicts according to the present invention are discussed in later sections. Occasionally, the user may cause the same, or matching, information to exist in different datasets without using the present invention, and then use the present invention to synchronize the datasets. For example, the user may cause records to exist for a "Bob Smith, of Acme Widgets" in multiple datasets, either by adding such records or by modifying existing records into such records. If the definition of the contact data type requires that the first name, last name, and company information for each contact be unique, then the example records would by definition match one another. In such a situation, simpleminded propagation of each added or modified record in each dataset to all other datasets would result in a duplication of records. Therefore, the present invention performs duplicate resolution to prevent such duplication. Automatic and user-assisted methods for resolving duplicates according to the present invention are discussed in later sections. Preferably, logic for performing duplicate or conflict resolution is confined as much as possible to the synchronization system's core and not at the client datasets' accessor. F. Timestamps The present invention often will make processing decisions based on comparing the time at which past events occurred. For example, the system may want to know whether a record in a dataset was modified before or after a most recent synchronization. Therefore, the time of various events should be recorded. One or more "timestamp" values in record fields are dedicated to this purpose. Typically, datasets involved in synchronization can be assumed to support a "last-modification-time" timestamp. Datasets that do not have timestamps, however, can still be synchronized using the present invention, but may require more processing by the present invention (for example, to perform exhaustive record comparisons) or more intervention by the user (for example, during conflict resolution). In conjunction with the use of timestamps to compare the relative timing of record creation, modification, synchronization, or the like, the clocks on the datasets' respective devices may themselves be kept synchronized, or assumed to be synchronized, either to the same value, or to equivalent values, or to values having a constant offset. Equivalent clock values include clock values plus clock time-zone information showing that the clock values correspond to a common time, for example a common Greenwich Mean Time (GMT). Clock values having a constant offset to one another may exist for example if devices that do not include time zone information have clocks set for different time zones. Clock values having a constant offset may also exist if two devices do not have their clocks synchronized, and the user does not wish to, or cannot, synchronize them. For example, the clocks on a server computer and a local computer may not be synchronized, and the user may be unable to reset the server clock, even though it is off by, for example, five minutes. In specific situations, the present invention will work directly with timestamps from the clock of a particular dataset's device without first converting such timestamps to a common time such as time according to the synchronization system's own clock or GMT. This is done, when possible, to minimize problems due to any relative drift in the devices' clocks, such as drifts caused by clock inaccuracies or drifts caused by the user's re-setting of a clock on a device. Comparison of timestamps is further discussed elsewhere, for example in the incorporated U.S. patent application having Ser. No. 09/136,215 and elsewhere in this document. Some information devices may be so simple as not to have real-time clocks (having time and date) at all. Datasets in some of such devices and other devices, instead, use simple counters as their (non-real-time) clocks. Such counters are incremented either continually at unspecified and possibly non-constant rates or upon the occurrence of particular activities or events. For example, the counter may be incremented whenever any record is changed in the dataset (such that the counter counts changes). Counter values may be suitable for use as timestamps (e.g., last-modification timestamps) for the dataset, especially if the counters are guaranteed to increase between one change to any record within the dataset and any subsequent change to any record within the dataset. However, such timestamps for the dataset cannot readily be converted into a real time (e.g., GMT time and date) and therefore cannot readily be compared with timestamps (e.g., real-time timestamps) from other datasets (and therefore are not globally-usable). Synchronization schemes according to embodiments of the present invention will work with even such datasets. In particular, the synchronizer, and especially the client accessor, does not need to compare timestamps from such a client dataset's clock with timestamps from another clock, such as the reference dataset's clock. For data from such datasets, however, timestamp-based automatic conflict resolution (e.g., "latest change wins") may not be possible, as will be described. Regardless, even for client datasets with real-time clocks that produce globally-usable timestamps, comparison between timestamps from different devices can be problematic due to time-drift and other issues, and when needed are preferably confined to the synchronization system's core. Preferably, all client datasets do have and use real-time clocks that provide globaly-usable timestamps (e.g., convertible into GMT). Most especially, the synchronizer core (including the reference dataset) preferably has and uses a real-time clock that provides globally-usable (e.g., convertible into GMT) timestamps for the core's records and operations. V. A More Detailed Discussion: The Synchronization System A. System Architecture FIG. 6 is a block diagram that shows the architecture of a synchronizer 600 according to an embodiment of the invention. The synchronizer 600 includes a client accessor 605 and a synchronizer core 240A which communicate with each other by exchanging messages called "action objects" 615, 617, 619, 621, 623, and 625 via a communication network 610 that is found in the environment of the synchronizer and via a communication layer 630 and input queue 632 and output queue 634. In the preferred embodiment, the synchronizer 600 includes a synchronization server, capable of wireless- and Internet-based communication, on which the synchronizer core 240A is implemented. The communication network 610 may include wireless or wireline networks for providing point-to-point, real-time connections (e.g., sockets, full- or half-duplex connections, and the like, etc.) and/or wireless or wireline networks for transferring messages (e.g., paging messages or e-mails). Examples of suitable communication networks include GSM networks (Global System for Mobile Communications), PCS networks (Personal Communication Services), TDMA (Time-Division Multiple Access) networks, CDMA (Code-Division Multiple Access) networks, wireless paging networks, AMPS (Advanced Mobile Phone System) networks, CDPD networks (Cellular Digital Packet Data), POTS networks (Plain-Old-Telephone-Service), the Internet, other IP-based (Internet-Protocol) or TCP/IP-based (Transmission Control Protocol/IP) networks, networks supporting SMS (Short Messaging Service), networks supporting WAP (Wireless Application Protocol) or HDTP (Handheld Device Transport Protocol), other cellular networks, other paging networks, other digital or analog wireless networks, other wireline networks, other circuit- or packet-based networks, and like networks. (WAP specifications are available for free download on the Internet at http://www.wapforum.com/docs/technical.htm.) The client accessor 605 handles access to information in a particular client dataset (not shown) and handles delivery and receipt of information across the communication channel 610 on the client side. The communication layer 630 handles delivery and receipt of information across the channel 610 on the synchronizer core's side. The communication layer 630 includes a listener 635 for receiving and unpackaging (e.g., de-serializing) information from the communication channel 610 into an input queue 632. The communication layer 630 also includes a writer 640 for packaging (e.g., serializing) and sending information onto the communication channel 610 from the output queue 634. The synchronizer core 240A includes a GUD 255A that stores a super-set of information from all other datasets as a central repository of information, including not only the latest, conflict-resolved values of data records but also status information, including the correspondence, or mapping, of records in the GUD to records in other datasets. The synchronizer core also includes a synchronizer engine 254A that controls and maintains the GUD and works with all client accessor(s) to collectively drive and control the synchronization process. The Synchronization engine works with client accessor(s) by receiving action objects via the input queue and sending action objects via the output queue. Preferably, the client accessor 605 exists as a software process that runs on a same device as the particular client dataset. Preferably, the listener 635 and the writer 640 exist as individual software processes that respectively replenish and withdraw action objects from the in queue and out queue, respectively, when available. The action objects 619, 621, 615, and 625 that are used by the synchronizer core 240A and the accessor 605 for mutual communicating will be further described in a later section. For now, it is sufficient to mention that action objects are a defined format for conveying dataset changes and other information between the synchronizer core and client accessors, in either direction. The action objects 615, 617, 623, and 625 are action objects that have been packaged (for example, serialized) for transport across the communication channel 610. B. The Reference Dataset (GUD) FIG. 7A is a block diagram that shows components of the Reference dataset, or GUD 255A according to a preferred embodiment. As shown, the GUD includes stored GUD records 702. These GUD records correspond to the most up-to-date, conflict-resolved records processed by the synchronizer during any synchronization since the GUD was created or last reset. The GUD records 702 include data 703 corresponding to data in client records and status information 704 about the GUD records 702. In addition, the GUD includes status information 706 about records in the clients. In particular, the client status information 706 includes information about all records last known by the synchronizer to be in the clients and to correspond to GUD records. Preferably, the client status information 706 is organized as independent "mapping tables" (for example, a mapping table 707) that each includes information relating to all records last known to be in a particular client that correspond to (e.g., are mapped to) the GUD records. 1. GUD Records, Including Their Status FIG. 7B is a table that shows the GUD records 702 (from FIG. 7A), including their data 703 and some of their status information 704. In FIG. 7B, each row 708 of the table represents a GUD record. The status information 704 preferably includes information for determining which GUD records are fresh with respect to a given client--i.e., which GUD 1t records include values or status (e.g., "deleted") that a client may not have seen before. The status information 704 also preferably includes information for resolving conflicts, automatically or with user assistance. More particularly, according to the preferred embodiment, the status information 704 includes for each GUD record a unique GUD record identifier 712 ("GUD ID"), a logical delete flag 713, GUD last-modified timestamp information 714, last-modification source-client information 715, priority information 716, and other information 718. Each GUD ID 712 uniquely identifies a GUD record within the GUD. In the preferred embodiment, each GUD ID is an integer having at least 32 bits. The logical delete flag 713 is used to indicate that a GUD record is to be considered "deleted," for example as the result of a synchronization or a user modification via the optional U.I. 245. The GUD record itself is not completely and physically deleted, and thus the "deletion" is only a "logical deletion." The GUD last-modified timestamp information 714 includes at least one timestamp that indicates when the GUD record was last modified in the GUD. Preferably, the GUD last-modified timestamp information 714 includes a separate last-modification timestamp according to the engine's (i.e., GUD's) clock for each data field of the GUD record. The timestamp for each data field of each record indicates the time that the data field of the record was modified in the GUD. The GUD last-modified timestamp information 714 can be used to determine whether the GUD record is fresh with respect to particular clients, as will be further explained. The timestamp for each data field i of a given GUD record may be referred to as gmT_Mod[i]. The last-modification source-client information 715 includes an identifier (e.g., a mapping table ID) that indicates from which dataset the last modification came. The source dataset is either a client or may be the GUD itself, if for example the changes come from the user via the GUD's user interface. Preferably, the last-modification source-client information 715 includes a separate dataset (e.g., client) identifier for each data field of the GUD record. The dataset identifier for each data field of each record indicates the dataset from which the last change to the data field of the record came. The client identifier for each data field i of a given GUD record may be referred to as C_Mod[i]. (The prefix C_is to suggest "Client".) The priority information 716 indicates the priority for the record, for use in resolving data conflicts. Preferably, the priority information 716 includes a separate priority for each data field of the GUD record. Preferably, the priority is an "original priority" timestamp that indicates the time that a record was last modified in a dataset (e.g., by a user) not due to synchronization by the synchronizer. (In general, data having later original priority time will be preferred over data having older original priority time according to the preferred conflict-resolution rules.) The original priority timestamps are preferably stored according to GMT, or at least convertible on-the-fly into GMT. The priority for each data field i of a given GUD record may be referred to as cT_Priority[i]. 2. Status with regard to the Clients' Records (Mapping Tables) FIG. 7C is a table that shows portions of the mapping table 707 (from FIG. 7A) that includes status information relating to a particular client. The mapping table 707 includes status information 719 about the client as a whole, for example its status, capabilities, limitations, and preferences as will be further described in later sections. The mapping table 707 also contains status information about each individual record last known by the synchronizer to be in the client. In FIG. 7C, each row 720 of the mapping table 707 corresponds to one particular GUD record. If a GUD record has a corresponding record in the client, then the GUD record's row in the mapping table will include both the GUD record's GUD ID and its client record's client ID 722, to thereby map the two ID's to each another. (A client ID uniquely identifies a client record within the client or client accessor.) If no record in the client corresponds to the GUD record, then the GUD record's row in the mapping table will be nonexistent or empty. The mapping table preferably includes information for determining which GUD records are fresh with respect to the client. The status information also preferably includes information for detecting whether changes received from a client are obsolete (e.g., superseded). The status information also preferably includes information for sending to the client to enable the client to determine whether changes received from the GUD are obsolete (e.g., superseded). More particularly, in the preferred embodiment, the status information for each record includes a last-sent-and-ack'd (acknowledged) timestamp 727, a last-client-sent timestamp 728, a client-send-last-processed timestamp 729, a client-send-needs-correcting code 730, and other information 731. For certain clients, the mapping table 707 also includes a CRC-type result 735. The client record ID 722 may be an integer or a descriptor (e.g., values of key data field(s)), depending on the particular client. The client record ID uniquely identifies a record within the client. The client record ID may be referred to as cR_ID. (The prefix cR_is to suggest "client record".) The last-sent-and-ack'd timestamp 727 for each GUD record indicates the time that a change for the GUD record (e.g., addition, modification, or deletion) was most recently sent to the client and also subsequently verified as received by the client. The last-sent-and-ack'd timestamp 727 is intended to be compared with modification times in the GUD for establishing relative order and determining freshness with respect to the client. The last-sent-and-ack'd timestamp 727 is preferably according to the GUD's clock. The last-sent-and-ack'd timestamp 727 for a given GUD record may be referred to as gsT_SentAckd. The last-client-sent timestamp 728 for each GUD record indicates the time (e.g., counter value) at which the client most recently sent to the GUD a change (e.g., addition, modification, deletion) from the client's corresponding record. As will be discussed, such timestamps are sent by the client to the synchronizer along with each dataset change. The last-client-sent timestamp 728 for any record is intended to be compared with other send times from the client for establishing relative order and determining obsolescence of change(s) received from the client (e.g., in a non-FIFO context). The last-client-sent timestamp 728 is preferably according to the client's clock (e.g., counter). The last-client-sent timestamp 728 for a given GUD record may be referred to as csT_ClientSent. The client-send-last-processed timestamp 729 for each GUD record indicates the time at which the synchronizer engine most recently processed (and did not discard) the last-sent change from the client's corresponding record. The client-send-last-processed timestamp 729 is intended to be compared with modification times in the GUD for establishing relative order and determining freshness with respect to the client. The client-send-last-processed timestamp 729 is preferably according to the GUD's clock. The client-send-last-processed timestamp 729 for a given GUD record may be referred to as gmT_ProcClientSent, as will be further explained later. The client-send-needs-correcting code 730 for each GUD record indicates whether, based on the last-sent change from the client's corresponding record, the client's corresponding record needs to be changed to match the GUD record. More particularly, if the last-sent change from the client's record lost a conflict resolution in at least one data field, then the client's record would need to be corrected, based on the last-sent change. The client-send-needs-correcting code 730 for a given GUD record may be referred to as bool_LostConflictClientSent. The CRC-type result 735, present for certain clients, characterizes the value of the client record as last known to the synchronizer. The CRC-type result 735 is useful for quickly determining via direct comparison whether the value of the client record has changed on the client since the previous synchronization of the client by the synchronizer. In particular, the CRC-type result is needed for this purpose if the client is of the type that does not maintain a last-modified timestamp for its records, as will be further discussed in connection with synchronization methodologies. The CRC-type result 735, in an embodiment, may include a subcomponent (e.g., relating to just a few key record fields) that is used for determining equivalence for duplicate resolution purposes. In the preferred implementation, a mapping table exists for each client. Thus, each GUD record is capable of being mapped to all possible clients that the synchronizer is capable of synchronizing. In particular, each GUD record may be mapped to records in one, two, or more than two clients (e.g., datasets). Even more particularly, the GUD may include just a single copy of a particular GUD record, and that single copy corresponds to, and may be mapped to a record from each of one, two, or more than two clients. Each mapping table has a unique mapping table ID. Because the status information in all mapping tables includes information of client records corresponding to GUD records, the status information 706 may also be considered a part of the GUD records 702--i.e., each GUD record 708 (of FIG. 7B) can be considered to include not only the GUD record's data (e.g., a pointer) and its status in the GUD, but also the status (e.g., information of row 720) of the GUD record's corresponding records in other datasets. Reference may be made to the incorporated patent applications having Ser. Nos. 09/136,215 and 09/208,815 for further details of the architecture underlying the present invention, including the means for establishing a mapping of records and record fields across datasets, to the extent that the incorporated patent applications are not contradicted (superseded) by the present document. C. Client Dataset and Accessor FIG. 8 is a table that shows client records 802, including (user) data 803 and some status information 804, that are preferably available to the client accessor. In general, different client datasets are free to and are expected to store their records in possibly different formats and using possibly different storage technologies from one another. The accessor for each client includes the client-specific knowledge for accessing client records and transferring their contents or status as necessary to the synchronizer core using action objects. In FIG. 8, each row 808 of the table represents a client record. The status information 804 preferably includes information for determining which client records are fresh with respect to the GUD; i.e., which records include values that the GUD may not have seen before. The status information 804 also preferably includes information for determining whether changes received from the GUD/server are obsolete (e.g., superseded). More particularly, according to the preferred embodiment, the status information 804 includes for each client record a unique client record identifier 812 ("client ID"), client last-modified timestamp information 814, a last-sent-and-ack'd (acknowledged) timestamp (e.g., counter) 827, a last-GUD-sent timestamp 828, a GUD-send-last-processed timestamp 829, and other information 830. Each client ID 812 uniquely identifies a client record within the client accessor. In the preferred embodiment, each client ID is an integer having at least 32 bits. The client record ID may be referred to as cR_ID. The client last-modified timestamp information 814 includes at least one timestamp that indicates when the client record was last modified in the client. Generally, for typical clients (e.g., the REX PRO.TM. organizer) the client last-modified timestamp information 814 includes just one last-modification timestamp for each client record, by the client's clock (e.g., counter). The client last-modified timestamp information 814 can be used to determine whether the client record is fresh with respect to the GUD. The last-modified timestamp for a given client record may be referred to as cmT_Mod. The last-sent-and-ack'd timestamp 827 for each client record indicates the time that a change for the client record (e.g., addition, modification, or deletion) was most recently sent to the GUD/server and also subsequently acknowledged (ack'd) as received by the GUD/server. The last-sent-and-ack'd timestamp 827 is intended to be compared with modification times in the client for establishing relative order and determining freshness with respect to the GUD. More particularly, as will be seen, the last-sent-and-ack'd timestamp 827 is used to enable the client to leave the client dataset unlocked even when (inbound) changes are expected. The last-sent-and-ack'd timestamp 827 is preferably according to the client's clock (e.g., counter) that is used for timestamping record modifications. The last-sent-and-ack'd timestamp 827 for a given client record may be referred to as csT_SentAckd. The last-GUD-sent timestamp 828 for each client record indicates the time at which the GUD/server most recently sent to the client a change (e.g., addition, modification, deletion) from the GUD's corresponding record. As will be discussed, such timestamps are sent by the server to the client along with each dataset change. The last-GUD-sent timestamp 828 for any record is intended to be compared with other send times from the GUD for establishing relative order and determining obsolescence of change(s) received from the GUD (e.g., in a non-FIFO context). The last-GUD-sent timestamp 828 is preferably according to the GUD's/server's clock (e.g., counter). The last-GUD-sent timestamp 828 for a given client record may be referred to as gsT_GudSent. The GUD-send-last-processed timestamp 829 for each client record indicates the time at which the client most recently processed (and did not discard) the last-sent change from the GUD's corresponding record. The GUD-send-last-processed timestamp 829 is intended to be compared with modification times in the client for establishing relative order and determining freshness with respect to the GUD. (The later of the GUD-send-last-processed timestamp 829 and the last-sent-and-ack'd timestamp 827 is preferably used as the "last-synchronized" time for the record.) The GUD-send-last-processed timestamp 829 is preferably according to the client's clock. If the received last-sent change from the GUD had caused a modification to the client record, the last-modified timestamp information 814 would be no later than this GUD-send-last-processed timestamp 829. The GUD-send-last-processed timestamp 829 for a given client record may be referred to as cmT_ProcGudSent, as will be further explained later. Note that most client datasets typically maintain the field cmT_Mod natively in the dataset itself. For legacy client datasets not designed with the present invention in mind, the client accessor is responsible for separately maintaining the fields csT_SentAckd, gsT_GudSent, and cmT_ProcGudSent, perhaps in the client accessor's own assigned storage area (e.g., persistent storage), for use in synchronization. This is a means of retrofitting a legacy client device to work with the present invention. Note that according to the present invention, during ordinary, non-synchronization use of the client dataset (e.g., by the user), the fields csT_SentAckd, gsT_GudSent, and cmT_ProcGudSent are not needed. Instead, these fields need only be used by the client accessor for synchronization. VI. A More Detailed Discussion: Synchronization Methodologies A. Introduction to Synchronization Messages ("Action Objects") Synchronization methods of the present invention communicate via synchronization messages called action objects. Action objects are used to communicate dataset changes and other signals. The meanings and usages of action objects according to the present invention are not limited to a chatty, single-session synchronization context. Action objects relevant to synchronization according to the present invention include the following types, which will be further described: Action Insert Record (C-Dominant Version) Action Update Record (C-Dominant, C-Untested, and (optionally) C-Conflicting Versions) Action Delete Record (C-Dominant, C-Untested, and (optionally) C-Conflicting Versions) Action Existing Record List (C-Untested Version) Action Request Ack Records Action Ack Records Action Retrieve Records Action Update Map Action Request Ack Maps Action Ack Maps Action Backup Record (Optional) Action Last Backup Sent (Optional) Action Retrieve Backup (Optional) B. Further Discussion of the Timestamps of the GUD and the Client(s) During synchronization, several types of timestamps may be encountered. In general, a timestamp is either from the client's clock, or from the server's clock. When possible, the present invention avoids directly comparing times from any client's clock with times from the server's clock or another client's clock. However, the synchronizer will perform such comparisons for timestamp-based automatic conflict resolution (e.g., "latest change wins") if the timestamps in question are known to be globally-usable (e.g., convertible into GMT). In general, a timestamp is either a record modification time or a synchronization communication time (e.g., send time). Preferably, each dataset (client or GUD) uses a same clock (e.g., a dataset-specific counter) to generate modification timestamps and timestamps of synchronization communications or activities. In this way, modification timestamps and synchronization times from the same dataset (or its accessor) can be compared. In this document, certain variables (e.g., "csT_SentAckd") are used. In these variables, the prefixes have the following meanings:
cT.sub.-- Time by client clock (and sometimes also GUD clock), if known
to be globally-usable.
cmT.sub.-- Time by client clock that is used for modifications. Without
further information, do not assume is globally-usable.
csT.sub.-- Time by client clock that is used for synchronization
communications. Without further information, do not a | ||||||