Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-11-16
2002-01-29
Homere, Jean R. (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06343299
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates in general to memory updating and more specifically to update synchronization among multiple computing devices. In particular, devices which are temporarily connected to the network are update synchronized with other devices which reside on the network.
BACKGROUND OF THE INVENTION
With the rapid advancement of semiconductor, storage and display technologies, hand held or mobile devices have become increasing versatile and popular. A user may simultaneously posses several of these devices, such as Palm Pilot (which is a trademark of IBM Corporation, Armonk, N.Y.), mobile phone, laptop PC, home PC, office workstation, etc. A single database, file or document may be multiply replicated over several of these computing devices.
A critical issue in this environment is that these multiple replicas on the various devices may be updated independently. Furthermore, the update synchronization can occur between any pair of devices. Since many of these devices are mobile or hand held, they are only occasionally connected either to the network or directly to another device. Any centralized scheduling on update synchronization will not work in this envirornent. Neither will the client-server model where each client machine will always perform synchronization with a pre-assigned server. Here the appropriate model is the any-to-any synchronization model, where any pair of devices can perform synchronization with each other at any time. For example, assume an individual has four devices: Palm Pilot, Thinkpad (which is a trademark of IBM Corporation, Armonk, N.Y.), office workstation and desktop PC at home. The individual may want to replicate his calendar over all of these devices. On a business trip, he may bring the Palm Pilot and Thinkpad with him. He can leave the Thinkpad in the hotel and only carry the Palm Pilot to his business meeting. When returning to the hotel, he can synchronize the Thinkpad with the Palm Pilot which contains the update he had made during the day. The individual can then use the Thinkpad to dial up to the office workstation to synchronize with the update made by his secretary on the workstation copy. His wife at home can synchronize the copy on the home PC with the office workstation so she can let him know the weekend schedule.
This update synchronization issue is different from the conventional database update issue among multiple replica where most of the devices are always connected. The standard transactional approach is to propagate every update to all replica before a transaction can commit. This is described, for example, in P. A. Berstein, et al., “Concurrency Control and Recovery in Database Systems”, Addision-Wesley, Reading, Mass. 1987. This update or write-all approach can use any serializable concurrency control to synchronize access to the multiple copies. A variation is to allow for only updating a majority of the replica or quorum consensus. Another variation is the lazy propagation approach where only one replica is updated by the transaction itself, as for example, Y. Breitbart, et al., “Replication and Consistency: Being Lazy Helps Sometimes”, Proc. ACM Symposium on Principles of Database Systems, 1997, pp. 173-184. In this approach, a separate transaction runs on behalf of the original transaction at each replication site at which update propagation is required. Consistency can be ensured by directing all updates to a primary copy and employing appropriate concurrency control.
The issue considered is also different from that in a client server environment. In a client server environment, although the client can stay mostly unconnected, it always has a specific server to synchronize to. See for example, in L. Kawell, et al., “Replicated Document Management in a Group Communication System”, in Groupware: Software for Computer-supported Cooperative Work, pp. 226-235, IEEE Computer Society, 1992, and K. Moore, “The Lotus Notes Storage System”, Proc. ACM SIGMOD 95 conference, pp. 427-428 on the replication approach in Lotus Notes. In this approach, the time of last modification is kept with each record (or document) of a replica. Only the records modified since the last synchronization are exchanged during the synchronization. Another approach as used by Palm Pilot is to maintain a dirty bit on each modified record. When a record is modified, the dirty bit is turned on. During synchronization, all modified records are exchanged and the dirty bits are reset to zero. For example, R. Riggs, “MNCRS Data Synchronization Architecture Document”, www.oadg.or.jp/activity/mncrs/dsync/arch/datasyncarch.html, specifies a framework for data synchronization between mobile network computers, such as Palm Pilot, and its servers or peers.
In the environment considered here, a device can request sync with any other device. There is no designated sync server for a device. A straightforward approach to do any-to-any sync is to maintain a local time-stamp on update by each device on each record, e.g., device
1
updates record
1
at 9:50 am, Jun. 23, 1997 and device
2
updates the same record at 10:50 am, Jun. 25, 1997. Since the update time is based on local device time, no global time synchronization would be required. The problem with this time-stamp approach is that the number of bits required to represent the time-stamp is sizable. For example, a time stamp with year/month/date/time can require more than 32 bits. As the number of records and devices increases, it will cause considerable delay to perform the synchronization, especially in a low bandwidth environment such as a phone line.
An alternative approach is the local counter approach that maintains a local counter on each device, where every time a record of a database (or file) is updated (or inserted/deleted) by a device, the local counter for the device which performed the update is incremented by one, and assigned to that file as a version number. For example, D. S. Parker, et al., “Detection of Mutual Inconsistency in Distributed Systems”, in IEEE Trans. On Software Engineering, Vol. SE-9, No. 3, May, 1983, pp. 240-247, provides a means to detect version conflict through maintaining the version numbers from each system or device to a file. This version number can still become an arbitrarily large number.
SUMMARY OF THE INVENTION
A computing device has a database replica comprised of a plurality of records. A synchronization request is provided to a further computing device having a further database replica which is comprised of a further plurality of records. A version table maintains version numbers for each of the plurality of records. The version numbers each have a maximum size. The maximum size is selectable. The plurality of records may be synchronized with the further plurality of records based upon the version numbers.
REFERENCES:
patent: 4714992 (1987-12-01), Gladney et al.
patent: 4714996 (1987-12-01), Gladney et al.
patent: 5261094 (1993-11-01), Everson et al.
patent: 5280612 (1994-01-01), Lorie
patent: 5404508 (1995-04-01), Konrad et al.
patent: 5434994 (1995-07-01), Shaheen et al.
patent: 5560005 (1996-09-01), Hoover et al.
patent: 5581754 (1996-12-01), Terry et al.
patent: 5649195 (1997-07-01), Scott et al.
patent: 5671407 (1997-09-01), Demers et al.
patent: 5684984 (1997-11-01), Jones et al.
patent: 5737601 (1998-04-01), Jain et al.
patent: 5765171 (1998-06-01), Gehani
patent: 5787247 (1998-07-01), Norin et al.
patent: 5787262 (1998-07-01), Shakib et al.
patent: 5832489 (1998-11-01), Kucala
patent: 5999947 (1999-12-01), Zollinger
patent: 6041123 (2000-03-01), Colvin
patent: 226734 (1987-07-01), None
patent: 765062 (1997-03-01), None
patent: WO-950880 (1995-03-01), None
patent: WO-9704389 (1997-02-01), None
Huang Yun-Wu
Yu Philip Shi-Lung
F. Chau & Associates LLP
Homere Jean R.
Robinson Greta L.
LandOfFree
Method and apparatus for random update synchronization among... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for random update synchronization among..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for random update synchronization among... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2826586