Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2001-01-25
2003-07-29
Metjahic, Safet (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06601076
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the field of synchronizing multiple copies of one or more databases in a network environment including electronic devices.
2. Related Art
As the components required to build a computer system have reduced in size, new categories of computer systems have emerged. One of the new categories of computer systems is the “palmtop” computer system. A palmtop computer system is a computer that is small enough to be held in the hand of a user and can therefore be “palm-sized.” As a result, palmtops are readily carried about in a briefcase or purse, and some palmtops are compact enough to fit into a person's pocket. By virtue of their size, palmtop computer systems are also lightweight and so are exceptionally portable and convenient.
Most palmtop computer systems are used to implement various personal information management (PIM) applications such as an address book, a daily organizer, scheduling calendar, and electronic notepads, to name a few. Palmtop computers with PIM software have been known as Personal Digital Assistants (hereinafter referred to as “PDAs”).
Further development of PDAs has enabled their use for portable, and even wireless, access to computer networks. The portability and convenience, and, most importantly, the ready ability to synchronize a palmtop device with other computers and data sources, makes such devices ideal for use in networks that serve the workplace as well as the home.
Synchronization is a process that provides the ability to coordinate the databases maintained on a PDA with copies, or versions, of the same database maintained on a desktop or other computer, or other electronic device, such as a cell phone. Not only is the access to data generally more readily available on a desktop, but desktops or other networked devices have ready access to printers and communication with other devices in the network and the internet on a continuing basis.
Typically, in a network having a PDA, a 2-way synchronization is accomplished with the PDA communicating with a desktop through a cradle device. Synchronization is initiated at either the desktop or PDA and the user can generally select whether the PDA's database is to be written over (one-way), or the desktop's database is to be written over (one-way the other way), or all modifications on each are to be incorporated in the other (two-way).
Historically, however, as the number of copies of a database grows, the number of required synchronizations grows exponentially. Each additional copy of each database needs to be synchronized with all the other copies, resulting in a growth of time required on the order of 2
n
, where “n” is the number of database copies to be synchronized. This number “n” is increased for each database maintained.
In a complex network, with a dynamic set of databases, the time devoted to necessary synchronizations could begin to drag down system performance with even a modest number of databases and their respective copies. More importantly, if synchronization takes too long, users will begin to initiate synchronization less frequently than necessary, or worse, avoid it entirely.
What is required, therefore, is a mechanism for rapidly and reliably synchronizing multiple copies of one or more databases in a network environment. The need further exists to allow the expansion of the number of copies of a database that are synchronized without unnecessary limit and without an exponential increase in the amount of time required to accomplish the synchronization process.
SUMMARY OF THE INVENTION
The present invention discloses a method and system for rapidly and reliably synchronizing multiple copies of one or more databases in a network environment. The present invention also discloses a method and system for increasing the number of database copies without a corresponding exponential increase in the amount of time required to accomplish the synchronization process.
Specifically, the present invention discloses a method and system for a coordinated “n-way” synchronization of multiple database copies where “n”, the number of copies synchronized, is essentially any number more than two. In one embodiment of the present invention, each database copy has its own customized set of synchronization rules. Further, each database copy is assigned to a priority level that defines the order of synchronization priority.
Upon synchronization of the n-database copies, one embodiment of the present invention dynamically creates a non-conflicting rule set at each synchronization priority level. Thereafter, rule-based synchronization of the n-database copies is performed by identifying a focus copy of the database located at the present priority level and comparing the data records of the focus copy against the same records in other copies of the database. The proper action such as deletion, modification, addition, retention, and addition of new record identifiers at the appropriate database copy is then performed for synchronization. The record modifications described above are done accordingly to rules as defined in the non-conflicting rule-set for the given priority level.
The process then identifies another focus copy of the database located at the present priority level, or if none are found at the present priority level, then at the next highest priority level until all copies of the database have been synchronized.
This focus selection process is repeated at each priority level for each copy of the database classified with that priority level, starting at the level with the highest priority and proceeding to the next highest priority level, until synchronization of all copies of the database is complete. In terms of synchronizing database copies between participation levels, higher order participation levels have priority over lower order levels. The method and system enabled by the present invention allows the speedy maintenance of multiple, synchronized databases without the inadvertent loss of any data record.
REFERENCES:
patent: 5696799 (1997-12-01), Kainulainen
patent: 5878095 (1999-03-01), Kainulainen
patent: 6141664 (2000-10-01), Boothby
patent: 6487560 (2002-11-01), LaRue et al.
Baruch Awerbuch, Shay Kutten, Yishay Mansour, Boaz Patt-Shamir, and George Varghese (1993), Time Optimal Self-Stabilizing Synchronization, pp. 652-661.*
Gruia-Catalin Roman and Mark S. Day (1984), Multifaceted distributed systems specification using processes and event synchronization, pp. 44-55.*
Hisaaki, Katagiri, Keiichi Yasumoto, Akira Kitajima, Teruo Higashino, and Kenichi Taniguchi (2000), Hardware Implementation of Communication Protocols modeled by Concurrent EFSMs with Multi-way Synchronization, pp. 762-767.*
Anoop Gupta (1989), High-Speed Implementations of Rule-Based Systems, pp. 119-146.*
T. V. Lakshman and Dipak Ghosal (1991), Performance Evaluation of an Efficient Multiple Copy Update Algorithm, pp. 488-495.*
Louise Lamont, Lian Li, Renaud Brimont, and Nicolas D. Georganas(1996), Synchronization of Multimedia Data for a Multimedia News-on-Demand Application, pp. 264-278.*
Ragunathan Rajkumar (1990), Real-Time Synchronization Protocols for Shared Memory Multiprocessors, pp. 116-123.*
Herng-Yow Chen and Ja-Ling Wu (1996), MultiSync: A Synchronization Model for Multimedia Systems, pp. 238-248.
Duggaraju Ravi
Goeppinger Cole
Jarvinen Brad
McCaw Kelly
Metjahic Safet
Nguyen Merilyn
Palm Source, Inc.
Wagner , Murabito & Hao LLP
LandOfFree
Method and apparatus for coordinated N-way synchronization... 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 coordinated N-way synchronization..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for coordinated N-way synchronization... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3068976