Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-04-09
2002-10-01
Corrielus, Jean M. (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C709S220000
Reexamination Certificate
active
06460051
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates generally to synchronization of data—that is, the process of taking two or more separate collections of data (“datasets”), identifying differences among them, and applying changes to one or more of the datasets to make the datasets identical or equivalent.
With each passing day, there is ever increasing need for synchronization solutions for connected information devices. Here, information devices include for example general- or special-purpose computers of all types and sizes, Internet or intranet access devices, cellular phones, pagers, and other hand-held devices including, for example, REX PRO™, PalmPilot and Microsoft “Windows CE” devices, and the like.
(REX™ and REX PRO™ are trademarks of Franklin Electronic Publishers of Burlington, N.J. REX and REX PRO organizers include licensed technology from Starfish Software, Inc. (“Starfish”), the present assignee. PalmPilot organizers are produced by Palm Computing, Inc., a subsidiary of 3Com Corp. of Santa Clara, Calif. The Windows CE device operating system and other Microsoft software are produced by Microsoft Corporation of Redmond, Wash.)
As the use of information devices is ever growing, users often have their data in more than one device, or in more than one software application. Consider, for instance, a user who has his or her appointments and contacts on a desktop personal computer (PC) at work and also has appointments or contacts on a notebook computer at home and on a battery-powered, hand-held device for use in the field. The user is free to alter the information on any one of these devices independently of one another. What the user really wants is the information in each device to remain synchronized with corresponding information in other devices in a convenient, transparent manner. Still further, some devices are connected at least occasionally to a server computer (for example, an Internet server) which stores information for the user. The user would of course like the information on the server computer to participate in synchronization, so that the server computer also remains synchronized.
An early approach to maintaining consistency between datasets was simply to import or copy one dataset on top of another. This simple approach, one which overwrites a target dataset without any attempt at reconciling any differences, is inadequate for all but the simplest of applications. Expectedly, more sophisticated synchronization techniques were developed. In particular, a synchronization technique was developed, in which exactly two datasets are synchronized by a PC-based synchronization system that is specific to a particular other device (e.g., PalmPilot organizer). The synchronization is conducted in a single, intensive session via a direct local connection (e.g., serial cable or short infrared link) that is maintained during the entire synchronization. Thus, the prior synchronization technique is a session-based, connection-based technique.
The prior, PC-based synchronization system functions as follows. First, it directly requests and receives (i.e., reads) one record at a time from the other device's dataset via the local connection to obtain changes that have been made to that dataset since a previous synchronization. Then, the system similarly obtains changes that have been made to the PC's dataset since the previous synchronization. The system next resolves any identified conflicts involving these changes, for example, by asking the user to choose a winner from two changes that conflict. Finally, the system directly propagates (e.g., writes) the conflict-resolved changes from each of the datasets into the other dataset, to leave the two datasets in identical or equivalent states. During the synchronization, which typically lasts several minutes or less, both datasets are “locked” to prevent the user from modifying the datasets.
The prior synchronization techniques have their uses. However, as more and more types of devices are introduced that include datasets to be synchronized, a need has arisen for improved synchronization schemes to take advantage of (or compensate for) the particular characteristics of these new devices and datasets. Consider, for example, the fact that many modern devices such as pagers and cellular phones are now capable of distant wireless communication or Internet-based communication. It would be desirable to efficiently synchronize user information in such devices using such distant communication mediums. Further, because many of the modern devices are capable of conducting message-based or connectionless communication (e.g., electronic mail (e-mail) or wireless paging) as opposed to connection-based communication (e.g., direct serial connection), it would be desirable to efficiently synchronize the user information in such devices using message-based communication techniques, especially automated techniques that require little to no user intervention besides initiating synchronization. Unfortunately, the prior synchronization technique, which is designed for use over a direct local serial connection, is not well-adapted to the characteristics commonly associated with distant and/or message-based communication, especially if errors occur during communication, as will be described.
Consider for instance the characteristic of high communication latency, which is unavoidable for certain popular communication technologies such as paging or e-mail. Paging or e-mail messages can take minutes, hours, or sometimes even longer (e.g., days) to be delivered, when the messages are not lost outright. Clearly, the prior synchronization scheme, which requires numerous sequential communication exchanges (e.g., one request-response cycle per data record), will be intolerably slow to finish if directly applied to synchronize datasets across such high-latency communication mediums.
Further, if a synchronization might take a long time to finish (e.g., more than thirty minutes), due for example to high latency, the user would want to use (e.g., modify) his or her data during the synchronization. The prior synchronization system cannot accommodate such a user because the system locks the datasets against modifications during every synchronization. The prior synchronization system cannot be rescued simply by modifying it to leave the datasets unlocked during synchronization because then the modified system would not guarantee data integrity. In particular, suppose the prior system, during a synchronization, reads a handheld device's data record “Bill Smith, version A” at time
1
, and updates it with a PC's updated corresponding data record “Bill Smith, version B” at time
3
. If the prior system were modified to allow the user to hand-modify the record at time
2
into “Bill Smith, version C” in the middle of the synchronization, then the just-made modification (“version C”) would be overwritten at time
3
as a part of the synchronization without any attempt to determine whether the just-made modification (“version C”) is in fact the one that should be retained—i.e, without any conflict resolution. In short, the user's desired information (when “version C” is the desired information) may be erroneously overwritten if the prior synchronization system is simply modified not to lock the datasets during synchronization.
In addition to high latency, communication environments (e.g., wireless, message-based, or Internet-based environments) may also have other characteristics such as low or intermittent reliability and availability, low or expensive bandwidth, inability to guarantee FIFO (first-in-first-out) delivery order, and the like. Each of these other characteristics introduces additional problems to the synchronization task. Furthermore, combinations of such communication characteristics makes the problems especially difficult to solve. To take just one example, consider the task of synchronizing over a communication medium that cannot guarantee FIFO delivery order for transmissions and is susceptible to high latency (e.
Dube Bryan
LaRue Chris
Yu Chiahua George
Corrielus Jean M.
Smith Darryl A.
Starfish Software, Inc.
Yu C. George
LandOfFree
System and methods for synchronizing datasets in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and methods for synchronizing datasets in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and methods for synchronizing datasets in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2987532