United States Patent
`[19]
`[11] Patent Number:
`5,974,238
`
`Chase, Jr.
`[45] Date of Patent:
`Oct. 26, 1999
`
`U8005974238A
`
`[54] AUTOMATIC DATA SYNCHRONIZATION
`BETWEEN A HANDHELD AND A HOST
`COMPUTER USING PSEUDO CACHE
`INCLUDING TAGS AND LOGICAL DATA
`ELEMENTS
`
`[75]
`
`Inventor: Charlie David Chase, Jr., Spring, Tex.
`
`[73] Assignee: Compaq Computer Corporation,
`Houston, TeX.
`
`[21] Appl. No.: 08/689,304
`
`[22]
`
`Filed:
`
`Aug. 7, 1996
`
`[51]
`
`Int. Cl.6 .............................. G06F 1/00; G06F 15/00;
`G06F 17/30; GO6F 15/62
`395/200.78; 395/200.76;
`[52] US. Cl.
`395/821; 395/892; 395/893; 707/200; 707/203;
`707/204
`[58] Field of Search ......................... 395/200.78, 200.76,
`395/821, 892, 893; 707/200, 203, 204
`
`[56]
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`4,897,781
`5,337,044
`5,392,390
`
`1/1990 Chang et al.
`........................... 364/200
`
`8/1994 Folger et al.
`.. 340/825.44
`2/1995 Crozier .................................... 395/161
`OTHER PUBLICATIONS
`
`Personal Air Communications Technology Brochure No.
`32956.
`
`Inc.) Brochure
`(Pacific Communication Sciences,
`PSCI
`entitled pACT: An Advanced Two—Way Messaging and
`Paging Protocol.
`PCSI News Release dated Jun. 5, 1996, announcing Chip Set
`for pACT Two—Way Paging and Messaging Services.
`Vendetti, Don, Wireless Tutorial—Narrowband PCS:
`Two—Way Messaging, Wireless for the Corporate User
`(1996).
`PSCI, Product Brochure for PC18101F—01 Control Proces-
`sor for AT&T pACT NPCS System, Dec. 1, 1995.
`PSCI, Product Brochure for PC11503T Modem IC for
`AT&T pACT NPCS System, Dec. 1, 1995.
`
`PSCI, Product Brochure for PC11504T Modem Processor
`for AT&T pACT NPCS System, Dec. 8, 1995.
`PSCI, Product Brochure for PC11605M Radio Transceiver
`for AT&T pACT NPCS System, Dec. 1, 1995.
`Thryft, Ann R., pACT Adds Sophistication to Two Way
`Paging Services, EBN, Jun. 17, 1996, 1996, p. 22.
`Moore, Mark, “Pegasus to lack key functions”, PC Week,
`Jun. 24, 1996, p.8.
`Matzkin, Jonathan, “The New PDAIIand—held devices head
`online”, PC Magazine, Jun. 25, 1996, p. 31.
`Yoshida, Junko, “WebTV pulls Sony, Philips into the Net,”
`Electronic Engineering Times, Jul. 15, 1996, p. 16.
`Wirbel, Loring, “Alliance to spin a wireless Web”, Elec-
`tronic Engineering Times, Jul. 15, 1996, pp. 1,8.
`Moore, Mark, “Users of Pegasus will get choice of wireless
`carriers”, PC Week, Jul. 22,1996, pp. 9,40.
`
`(List continued on next page.)
`
`Primary Examiner—Zarni Maung
`Assistant Examiner—William D. Thomson
`Attorney, Agent, or Firm—Akin, Gump, Strauss, Hauer &
`Fcld, LLP
`
`[57]
`
`ABSTRACT
`
`An apparatus is disclosed for performing dynamic synchro-
`nization between data stored in a handheld computer and a
`host computer, each having a plurality of data sets including
`at least one common data set, each computer having a copy
`of the common data set. The handheld computer has a
`processor, a communication port, and a data synchronization
`engine. The data synchronization engine has a pseudo-cache
`and one or more tags connected to the pseudo cache. Data
`is synchronized whenever data is written to main memory
`and/or when the associated pseudo-cache tag is invalidated.
`By strict adherence to a set of protocols, data coherency is
`achieved because the system always knows who owns the
`data, who has a copy of the data, and who has modified the
`data. The data synchronization engine resolves any differ-
`ences in the copies and allows the storage of identical copies
`of the common data set in the host computer and in the
`handheld computer.
`
`25 Claims, 25 Drawing Sheets
`
`216
`
`T44
`
`112
`
`BAEK-
`
`25
`
`[Cl]
`
`T10
`
` 102
`
`PSEUDD—CADHE I
`
`MIERUPRUEESSDR
`
`CUMBINAIIDM
`CHIP
`
`m
`
`
`
`43
`1 51
`—|:P
`
`
`
`
`
`
`
`.3 I116
`
`WIRELESS
`CIRCUIIRV
`
`120
`
`PCMEIA
`SLUHSI
`
`130
`38
`
`
`
`118
`
`+3.3,+5.
`PDWER
`50?er +1140
`
`50
`
`FANDANGO EXHIBIT 1074
`
`FANDANGO EXHIBIT 1074
`
`

`

`5,974,238
`Page 2
`
`OTHER PUBLICATIONS
`
`Grace, Elden, “RF Filter Technology for Wireless Commu-
`
`Wolfe, Alexander, “Microsoft poses PC specs”, Electronic
`Engineering Times, Aug. 8, 1996, Issue 909, pp. 1, 8.
`Gardner, W. David, “Microsoft eyes one—way paging to
`jump—start handhelds”, Electronic Engineering Times, Aug.
`8, 1996, Issue 909, pp. 10, 16.
`
`nications”, ereless Des1gn & Development, p. 8.
`
`Sharp Model ZR—5700/ZR—5800 Keyboard Enhanced Per-
`sonal Digital Assistant—Zaurus Operational Manual, pp.
`1—61.
`
`

`

`US. Patent
`
`Oct. 26, 1999
`
`Sheet 1 0f 25
`
`5,974,238
`
`
`
`

`

`US. Patent
`
`Oct. 26, 1999
`
`Sheet 2 0f 25
`
`5,974,238
`
`FIG.1C
`
`

`

`5,974,238
`
`FIG.1D
`
`
`
`

`

`5,974,238
`
`
`
`FIG.1E
`
`

`

`"2.GE
`
`

`

`US. Patent
`
`Oct. 26, 1999
`
`Sheet 6 0f 25
`
`5,974,238
`
`
`
`FIG. 3
`
`

`

`5,974,238
`
`vGE
`
`55a5.32:
`
`.m+_m.m+$32
`
`
`
`822+2.5m
`
`cm
`
`92
`
`US. Patent
`
`9991
`
`mw
`
`amoI.25-22:25—28
`6,582;:$352.35.:aI:Iwe
`
`
`
`Fmm2s:mEF
`
`:5:-5255H.5:was832Ia:
`m2:
`
`1"-
`
`
`
`cm35:2wasE85.v::2:wm:E5252%mass;
`
`
`

`

`US. Patent
`
`Oct. 26, 1999
`
`Sheet 8 0f 25
`
`5,974,238
`
`200
`
`CREATE
`.
`
`EXCLUSIVE
`
`PRIVATE
`
`__________UPD_ATE_
`
`MODIFY
`——————————— ->
`
`DIRTY
`SHARED
`
`206
`
`
`
`CLEAN
`SHARED
`
`INVALIDATE
`
`RESTORE
`
`DELETED
`
`240
`
`24 7 SIGNATURE
`242
`TABLE
`243
`
`TABLE
`
`FIELD MAPPING
`FIELD MAPPING
`FIELD MAPPING
`
`HELD / 220
`250
`251 MAPPING
`252
`
`FIG. 7
`
`

`

`US. Patent
`
`Oct. 26, 1999
`
`Sheet 9 0f 25
`
`5,974,238
`
`[:1
`Dun
`
`HANDHELD
`
`SYNCHRONIZATIDN SOFTWARE
`2 1 4
`
`_
`210
`
`COHERENCY
`DATA
`PROTOCOL
`SYNCHRDNIZATIUN
`ENGINE
`ENGINE
`
`SCHEDULER
`91M
`
`[ 224
`226
`
`
`scIIEOIILER
`”I
`I
`—:_ DATA ENEIELJ
`
`
`_ _ _ _ 42181
`230
`
`
`
`
`I
`_:
`PHONELIST
`PHONELIST
`PIM 234
`LQA_TAE_N§||\_1E_ 1
`
`
`
`FJ-
`
`"I
`ALTA ENGINE 1
`
`TRAVELAGENT
`PIM
`
`DESKTOP APPS
`
`229
`
`233
`
`225
`
`TRAVELAGENT
`PIM
`
`
`
`OOIIEIIENGII PROTOCOL
`ENGINE
`
`211
`
`213
`
`
`
`
`
`
`
`FIG. 6B
`
`

`

`US. Patent
`
`Oct. 26, 1999
`
`Sheet 10 0f 25
`
`5,974,238
`
`HTD CREATE HANDHELD
`
`2
`
`99
`
`N
`
`WHITE TD RAM
`
`300
`
`
`WHITE T0
`PREDETERMINED
`RANGquN RAM
`
`
`Y
`
`302
`
`HIT 0N
`RECD7RD ID
`
`N
`
`303
`
`CREATE HANDHELD TAG
`
`
`SET EXCLUSIVE BIT IN
`HANDHELD TAG
`
`
`
`310
`
`31 1
`
`312
`
`314
`
`318
`
`SLEEP
`
`
`
`
`CONSTRUCT CREATE PACKET
`
`
`
`
`DJESKTDP
`ACKN WLEDGMENT
`
`PACKET
`RECE’IVED
`
`
`
`CLEAR EXCLUSIVE BIT
`IN HANDHELD TAG
`
`
`Y
`
`320
`
`

`

`US. Patent
`
`Oct. 26, 1999
`
`Sheet 11 0f 25
`
`5,974,238
`
`324
`
`HTD CREATE DESKTOP
`
`IVE
`REC
`CREATE PACKET
`?
`
`
`
`
`
`
`
`'-<
`
`WAKE UP DATA
`SYNCHRONIZER
`
`326
`
`328
`
`PARSE CREATE PACKET TO
`EXTRACT HANDHELD RECORD ID
`81 FIELD INDICES
`
`330
`
`332
`
`334
`
`336
`
`337
`
`338
`
`CREATE DESKTOP TAG
`
`SET EXCLUSIVE BIT
`IN DESKTOP TAG
`
`ACCESS PIM
`APPLICATION DATA SET
`81 ADD NEW ENTRY
`
`UPDATE DESKTOP TAG
`SIGNATURE
`(SIG)
`
`CLEAR EXCLUSIVE BIT
`IN DESKTOP TAG
`
`SEND ACKNOWLEDGMENT
`PACKAGE TO HANDHELD
`
`EXIT
`
`FIG. 9
`
`

`

`US. Patent
`
`Oct. 26, 1999
`
`Sheet 12 0f 25
`
`5,974,238
`
`HTD MODIFY HANDHELD
`
`339
`
`WRITE TO RAM
`
`
`
`
`
`
`340
`
`
`
`
`
`WRITE TO
`PREDETERMINED
`RANGE IN RAM
`
`?
`
`N
`
`
`
`
`
`
`
`
`v
`
`34
`
`HIT 0N
`RECQFDID
`Y
`
`HIT RECORD
`MARKED FOR
`SHAglNG
`
`344
`
`Y
`
`350
`
`SET HANDHELD
`MODIFIED BIT
`
`352
`
`CONSTRUCT OR
`MODIFY PACKET
`
`354
`
`
`
`[Haw
`
`SEND MODIFY PACKET
`TO DESKTOP
`
`ACKNOWLEDGMENT
`‘CKET RECEIVEI
`7
`
`358
`
`
`
`SLEEP
`
`Y
`
`
`
`
`CONSTRUCT UPDATE
`PACKET
`
`361
`
`UPDATE
`
`
`
`
`
`360
`
`FIG. 10
`
`

`

`US. Patent
`
`Oct. 26, 1999
`
`Sheet 13 0f 25
`
`5,974,238
`
`HTD MODIFY DESKTOP
`
`
`RECEIVE
`
`MODIFY
`PACKET
`
`?
`
`364
`
`SLEEP
`
`Y
`
`366
`
`WAKE up DATA
`SYNCHRUNIZER
`
`368
`
`PARSE MODIFY PACKET T0
`EXTRACT HID & FIELD INDICES
`
`37o
`
`MATCH
`DETECTED ON
`HID
`:2
`
`N
`
`
`
`
`
`
`EXTRACT
`CORRESPONDING DID
`
`SET DESKTOP TAG
`MODIFY BIT
`
`SEND ACKNOWLEDGMENT
`PACKET TO HANDHELD
`
`

`

`US. Patent
`
`Oct. 26, 1999
`
`Sheet 14 0f 25
`
`5,974,238
`
`HTD UPDATE HANDHELD
`
`378
`
`380
`
`CDNSTRUCT
`UPDATE PACKET
`
`SEND UPDATE PACKET
`TD DESKTDP
`
`
`
`
`
`384
`
`
`RECEIVED
`
`Y
`
`DESKTDP
`ACKNOWLEDGMENT
`PACKET
`
`
`
`
`
`386
`
`MODIFY BIT
`
`FIG. 12
`
`

`

`US. Patent
`
`Oct. 26, 1999
`
`Sheet 15 0f 25
`
`5,974,238
`
`HTD UPDATE DESKTOP
`
`
`
`
`UFO“
`392
`
`PACKET
`
`RECEIVED
`
`
`396
`
`
`
`
`PARSE UPDATE PACKET
`
`
`TO EXTRACT RECORD ID
`& FIELD INDICES
`
`
`
`
`
`FIND
`MATCH ON HID IN
`DESKTOP TAG
`
`
`
`
` Y
`
`
`EXTRACT
`CORRESPONDING DID
`
`
`
`
`ACCESS PIM
`
`
`APPLICATION DATA SET
`81 PERFORM UPDATE
`
`
`UPDATE DESKTOP TAG
`SIGNATURE
`ISIGI
`
`
`
`CLEAR DESKTOP TAG
`MODIFIED BIT
`
`
`
`
`
`
`SEND ACKNOWLEDGMENT
`PACKET TO HANDHELD
`DEVICE
`
`
`
`

`

`US. Patent
`
`Oct. 26, 1999
`
`Sheet 16 0f 25
`
`5,974,238
`
`
`
`HTD INVALIDATE HANDHELD
`
`WRITE TO RAM
`
`
`
`
`
`40
`
`9
`
`
`
`410
`
`
`WRITE
`TO RAM WITHIN
`
`PROGRAMMED
`
`RANGE
`
`
`HIT ON
`RECORD ID
`?
`
`Y
`
`RECORD ID
`
`MARKED FOR
`
`SHARING
`
`
`Y
`
`
`
`SET HANDHELD TAG
`DELETE 8| MODIFY BITS
`
`INTERRUPT HANDHELD
`PROCESSOR
`
`
`
`
`CONSTRUCT
`INVALIDATE PACKET
`
`SEND INVALIDATE
`PACKET TO DESKTOP
`
`
`
`RECEIVE
`ACKNOWLEDGE
`PACKET TO
`HANDIHELD
`Y
`
`CLEAR HANDHELD
`TAG MODIFY BIT
`
`FIG. 14
`
`
`
`
`
`
`
`
`
`
`
`

`

`US. Patent
`
`Oct. 26, 1999
`
`Sheet 17 0f 25
`
`5,974,238
`
`HTD INVALIDATE DESKTOP
`
` RECEIVE
`INVALIDATE
`PACKET
`?
`
`
`
`Y
`
`PARSE INVALIDATE PACKET
`TO EXTRACT RECORD ID
`AND FIELD INDICES
`
`EXTRACT MATCH IN
`DESKTOP TAG AND DID
`
`SET DESKTOP TAG
`MODIFY BIT
`
`ACCESS PIM
`APPLICATION DATA SET
`AND PERFORM DELETION
`
`SET DESKTOP TAG
`DELETED BIT
`
`CLEAR DESKTOP TAG
`MODIFY BIT
`
`SEND ACKNOWLEDGMENT
`PACKET TD HANDHELD
`
`EXIT
`
`432
`
`434
`
`436
`
`438
`
`44
`
`0
`
`442
`
`446
`
`448
`
`

`

`US. Patent
`
`Oct. 26, 1999
`
`Sheet 18 0f 25
`
`5,974,238
`
`DTH CREATE DESKTOP
`
`
`
`450
`
`
`NEW
`RECORD IN PIM
`
`DATA, SET
`
`
`
`
`Y
`
`CREATE DESKTOP TAG
`ID & SET MODIFIED BIT
`
`CONSTRUCT
`CREATE PACKET
`
`
`
`
`
`
`
`
`SEND CREATE PACKET
`TO HANDHELD
`
`
`
`
`RECEIVE
`ACKNOWLEDGE
`PACKET FROM
`HANDHELD
`?
`
`Y
`
`ADD HANDHELD ID TO
`DESKTOP TAG
`
`CLEAR DESKTOP
`MODIFIED BIT
`
`
`
`

`

`US. Patent
`
`Oct. 26, 1999
`
`Sheet 19 0f 25
`
`5,974,238
`
`DTH HANDHELD CREATE
`
`472
`
`474
`
`476
`
`4
`
`78
`
`480
`
`
`
`RECEIVE
`CREATE
`PACKET
`?
`
`
`
`
`Y
`
`PARSE CREATE PACKET TD
`EXTRACT RECORD ID
`AND FIELD INDICES
`
`ADD PIM DATA TD HANDHELD
`
`CREATE HANDHELD TAG
`USING CORRESPONDING HID
`
`SEND ACKNOWLEDGE
`PACKET TO DESKTOP
`WITH HID
`
`FIG. 17
`
`

`

`US. Patent
`
`Oct. 26, 1999
`
`Sheet 20 0f 25
`
`5,974,238
`
`DTH DESKTOP MODIFY
`
`
`
`482
`
`
`SIGNATUR
`DIFFERENCE FDR
`
`RECORD
`
`
` Y
`
`SET DESKTOP TAG
`MODIFIED BIT
`
`
`CONSTRUCT
`MODIFY PACKET
`
`
`
`
`
`
`RECEIVE
`
`
`ACKNOWLEDGMENT
`PACKET FROM
`
`HAND’HELD
`
`
`
`
`SEND MODIFY PACKET
`TO HANDHELD
`
`
`
`Y
`
`SLEEP
`
`
`CONSTRU CT
`UPDATE PACKET
`
`
`
`

`

`US. Patent
`
`Oct. 26, 1999
`
`Sheet 21 0f 25
`
`5,974,238
`
`DTH HANDHELD MODIFY
`
`
`RECEIVE
`MODIFY
`PAC7KET
`
`
`
`
`
`
`498
`
`SLEEP
`
`Y
`
`500
`
`PARSE MODIFY PACKET
`TO EXTRACT RECORD ID
`AND FIELD INDICES
`
`502
`
`
`
`HANDHELD
`
`TAG MATCHES
`
`AN7H|D
`
`Y
`
`SET HANDHELD TAG
`MODIFIED BIT
`
`SEND ACKNOWLEDGMENT
`PACKET TO DESKTOP
`
`
`
`
`

`

`US. Patent
`
`Oct. 26, 1999
`
`Sheet 22 of 25
`
`5,974,238
`
`
`
`
`
`
`
`DTH UPDATE DESKTOP
`
`CONSTRUCT UPDATE PACKET
`& SEND TO HANDHELD
`
`
`
`510
`
`516
`
`
`
` 514
`
`
`
`
`
`RECEIVE
`ACKNOWLEDGE
`PACKET
`?
`
`Y
`
`CLEAR DESKTOP TAG
`MODIFIED BIT
`
`

`

`US. Patent
`
`Oct. 26, 1999
`
`Sheet 23 0f 25
`
`5,974,238
`
`DTH UPDATE HANDHELD
`
`
`
`
`RECEIVE
`UPDATE
`
`
`
`
`522
`
`SLEEP
`
`Y
`
`524
`
`PARSE UPDATE PACKET
`TO EXTRACT RECORD ID
`AND FIELD INDICES
`
`EXTRACT MATCHING
`HANDHELD TAG AND
`CORRESPONDING HID
`
`ACCESS HANDHELD PIM
`APPLICATION DATA AND
`PERFORM UPDATE
`
`CLEAR HANDHELD TAG
`MODIFY BIT
`
`SEND ACKNOWLEDGE
`PACKET TO DESKTOP
`
`EXIT
`
`526
`
`528
`
`530
`
`532
`
`

`

`US. Patent
`
`Oct. 26, 1999
`
`Sheet 24 0f 25
`
`5,974,238
`
`DTH INVALIDATE DESKTOP
`
`
`
`CHECK
`EXISTENCE DF
`
`
`
`
`
`RECvDRD
`
`SET DESKTOP TAG MODIFY
`AND DELETED BITS
`
`
`7
`
`
`
`
`
`RECEIVE
`ACKNOWLEDGE
`PACKET
`
`
` Y
`
`CLEAR DESKTOP
`MDDIFIED BIT
`
`

`

`US. Patent
`
`Oct. 26, 1999
`
`Sheet 25 0f 25
`
`5,974,238
`
`DTH DELETE HANDHELD
`
`
`
`
`PACr’KET
`
`Y
`
`PARSE DELETE PACKET
`TD EXTRACT RECDRD ID
`AND FIELD INDICES
`
`SET HANDHELD DELETED BIT
`
`PACKET TD DESKTOP
`
`_SLEEP
`
`554
`
`5
`
`56
`
`5
`
`58
`
`FIG. 23
`
`

`

`5,974,238
`
`1
`AUTOMATIC DATA SYNCHRONIZATION
`BETWEEN A HANDHELD AND A HOST
`COMPUTER USING PSEUDO CACHE
`INCLUDING TAGS AND LOGICAL DATA
`ELEMENTS
`
`BACKGROUND OF THE INVENTION
`
`1. Field of the Invention
`
`The invention relates to portable computing, and more
`specifically to the sharing of data between handheld com-
`puter systems and desktop and/or portable computer sys-
`tems.
`
`2. Description of the Related Art
`The rapid acceptance of computer technology by corpo-
`rations as well as consumers has led to the widespread use
`of computers. Further abetting this process is the continual
`reduction in size and cost of personal computers. Originally,
`personal computers were large items best suited for floor
`standing or desktop use. Eventually, they became smaller so
`that desktop use became the standard. Improvements in
`processor, memory and data storage capabilities have
`resulted in light weight, powerful mobile computers such as
`portables, luggables, laptops, notebooks, palm top and per—
`sonal digital assistants. These computers can provide suffi-
`cient processing capability for audio visual applications,
`such as computer aided design, three dimensional animation,
`and multimedia presentation, even when used at remote
`locations.
`
`As the use of personal computers increased, so did the
`desire to use computers remotely to support and increase the
`efficiency of mobile users. However, in most cases, note-
`book computers were effectively just small versions of
`full-function desktop computers and so were relatively
`expensive. Further,
`they were also relatively heavy and
`conspicuous to use. The unfavorable attributes of size,
`expense, and operating period limited the usefulness of
`notebook computers in certain applications, namely those
`that required on-the-spot data proessing with inconspicuous
`and transparent computing capability.
`One variant of small factor notebook computers is
`referred to as notepad or touchpad computers. These com—
`puters were essentially notebook computers with the key-
`board removed and a digitizer applied to the display so that
`a pen or other suitable pointing devices could be used as an
`input device. The use of a pen freed up one aspect of the
`computer size requirement, namely the requirement for
`keyboards of certain given dimensions. However, because
`the handwriting recognizers in these palmtop or handheld
`computers were not always 100% accurate, these pen-based
`notepad computers had to be geared to specific applications
`which utilized special hardware or operating programs such
`as inventory control and others where simple check-offs
`could be utilized or somewhat constrained input patterns
`could be entered. These limitations hampered the usage of
`the palmtops to only specific applications. Further, most of
`the original notepad units were based directly on a notebook
`computer form factor and as such came in sizes of approxi-
`mately 81/zx11 inches and 1 inch thick, and weighed 5 to 6
`pounds. Thus, these notepad units were quite heavy and
`inconvenient, in that they could not be carried for extended
`periods. Further, the performance of these portable devices
`was dramatically reduced to achieve the necessary minimum
`power consumption.
`Recently, a new class of portable computers called palm-
`top or handheld units has emerged. Some of these units offer
`very limited functionality and are typically restricted to
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`being personal organizers. These watered-down computers
`are not compatible with programs on larger desktop and
`notebook computers, but rely on proprietary operating sys-
`tems and programs to ensure small memory footprint and
`quick response time, even on low-power microprocessors.
`These restrictions limited the usefulness of the personal
`organizers, as they operate stand alone and cannot readily
`share data with other computers. Additionally, some units
`were also developed which did offer common functionality
`with the desktop computers, but were generally keyboard
`based and the use of tiny keyboards made them relatively
`unusable to a large segment of the population. Exemplary
`palmtop or handheld devices with miniature keyboards
`include the HP-ZOOLX, available from Hewlett-Packard
`Corporation. Furthermore, palmtop or handheld devices
`with pen interfaces have appeared. These devices include the
`Newton and the Pilot available from Apple Computer Cor-
`poration and US. Robotics Corporation,
`respectively.
`Further, palmtop computers with both a keyboard and a pen
`have also appeared, including the Zaurus ZR-5700/5800,
`available from Sharp Corporation.
`To balance between the ease of reading and editing files
`on a desktop computer and the convenience of collecting
`information and operating the palmtop or handheld when the
`user travelled, the user typically purchased both the desktop
`computer and the palmtop computer. The two platforms
`were linked Via one or more communication paths, including
`paths through a modem, a parallel port, a serial port, or a
`cradle assembly connected to the host computer. Further,
`various wireless communication techniques, such as radio or
`infrared communication may be used. In the event that a
`cradle was used, when the handheld computer was in the
`cradle and actively connected to the host computer,
`the
`handheld computer typically entered a mode to update data
`in the host computer and itself.
`A major problem exists in the current methods of syn-
`chronizing data between the desktop computer and the
`palmtop or handheld computer. For instance, certain data
`such as calendar information, appointment information, and
`notes, among others, would generally be kept on a desktop
`computer which may be networked so that other worksta-
`tions may remotely update the calendar information,
`appointment information, and notes. The same information
`was also kept on the palmtop or handheld computer for the
`user to review and update when mobile. However, if the user
`was traveling and information was entered on the desktop
`computer or on a remote station on a network server
`machine while the user was not at his or her office, or if the
`user entered information on the local version of the data in
`
`the information con-
`the palmtop or handheld computer,
`tained in the desktop computer and the palmtop or handheld
`computer would become non-coherent, leading to undesir-
`able problems such as meeting conflicts and miscommuni-
`cations.
`
`The prior resolutions of the data synchronization problem
`were generally very time consuming and tedious and there-
`fore reduced the effectiveness of the palmtop/desktop com-
`bination. One solution was to limit the accessibility of files
`such that only files physically residing with the user were the
`master. However,
`this solution dictated that no changes
`could be made to the other system without the danger of
`losing those changes. Thus, while the palmtop/desktop com-
`bination of computers existed, the use of the combination
`was not popular due to the requirement that the user had to
`manually synchronize the data on both platforms. Therefore,
`the problem of synchronization limited the potential of the
`palmtop or handheld computer market.
`
`

`

`5,974,238
`
`3
`One problem encountered by the current generation of
`handheld devices and their add-on connectivity solutions is
`that the connectivity solutions rely on batch mode rather
`than real-time oriented approaches to data coherency.
`Because the desktop and the handheld device typically
`became disconnected and incommunicado when the user
`
`the data synchronization problem becomes
`goes mobile,
`intractable. During the mobile period,
`the creation,
`the
`deletion and the modification of data causes incoherency
`that often results in conflicts reconcilable only through
`manual intervention by the user. These conflicts would arise
`because the desktop and handheld device were unable to
`communicate changes in their data until they were recon—
`nected using a serial, parallel or modem connection.
`Because data coherency is a real time problem, a real time
`solution that avoids data conflicts by shortening the time
`between synchronization events is needed. Therefore, it is
`desirable to have a small handheld computer system capable
`of operating certain personal
`information type software,
`such as calendars, telephone directories and to do lists, as
`well as simplified versions of desktop application software,
`and sharing data with a desktop computer, with all the data
`utilized by all of the programs being dynamically synchro-
`nized to alleviate the data coherency problem.
`SUMMARY OF THE INVENTION
`
`An apparatus is disclosed for performing dynamic syn-
`chronization between data stored in a handheld computer
`and a host computer, each having a plurality of data sets
`including at
`least one common data set, each computer
`having a shared copy of the common data set. The handheld
`computer has a processor, a communication port, and a data
`synchronization engine. The data synchronization engine
`exists on both the handheld and host computer and has a
`pseudo-cache and one or more tags connected to the pseudo-
`cache which can be implemented in either hardware or
`software. Data is synchronized when a write to system
`memory results in the creation, modification or deletion of
`data on either the handheld or host computer. By strict
`adherence to a set of protocols, data coherency is achieved
`because the system always knows who owns the data, who
`has a copy of the data, and who has modified the data. The
`data synchronization engine resolves any differences in the
`shared data set and facilitates the storage of the shared data
`set in the host computer and in the handheld computer. Data
`synchronization may occur using either wireless or wireline
`communications transports. In the wireless case the trans-
`ports could be two-way paging systems, cellular networks
`and wireless LANS such as ARDIS and RAM, as well as
`infrared-based LANs. In the wireline case the communica-
`tion transports could be serial, parallel, POTs and LANs and
`WANs.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`A better understanding of the present invention can be
`obtained when the following detailed description of the
`preferred embodiment is considered in conjunction with the
`following drawings, in which:
`FIGS. 1A and 1B are perspective views of a handheld
`computer according to the present invention;
`FIG. 1C is a perspective View of an embodiment having
`both pen and keyboard input devices of the handheld com-
`puter of the present invention;
`FIG. 1D is a perspective view of the handheld computer
`of FIGS 1A and 1B communicating wirelessly with a host
`computer;
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`FIG. 1E is a perspective view of the handheld computer
`of FIGS 1A and 1B communicating with a host computer via
`Internet;
`FIG. 1F is a perspective view of the handheld computer
`of FIGS. 1A and 1B located in a cradle and directly
`connected to a host computer;
`FIG. 2 is an exploded perspective view of the internal
`components of the handheld computer of FIGS 1A and 1B;
`FIG. 3 is a top layout view of the components of FIG. 2
`without the display;
`FIG. 4 is a schematic diagram of the handheld computer
`of FIGS 1A and 1B;
`FIG. 5 is a state machine of the data synchronizing states
`of the data synchronization engine executing on the hand-
`held computer of FIG. 4;
`FIG. 6A is a diagram of the data synchronization modules
`and data structure stored in the read only memory and
`random access memory present in the desktop computer
`system of FIGS. 1D—1F;
`FIG. 6B is a diagram of the data synchronization modules
`and data structure stored in the read only memory and
`random access memory present in the handheld computer
`system of FIG. 4;
`FIG. 7 is a diagram of the data structure of tags used by
`FIGS. 6A and 6B;
`FIG. 8 is a flow chart of the process of the handheld to
`desktop create process executing on the handheld computer
`of FIG. 4;
`FIG. 9 is a flow chart of the process of the handheld to
`desktop create process executing on the desktop computer of
`FIGS 1C—1F;
`FIG. 10 is a flow chart of the process of the handheld to
`desktop modify process executing on the handheld computer
`of FIG. 4;
`FIG. 11 is a flow chart of the process of the handheld to
`desktop modify process executing on the desktop computer
`of FIGS 1C—1F;
`FIG. 12 is a flow chart of the process of the handheld to
`desktop update process executing on the handheld computer
`of FIG. 4;
`FIG. 13 is a flow chart of the process of the handheld to
`desktop update process executing on the desktop computer
`of FIGS 1C—1F;
`FIG. 14 is a flow chart of the process of the handheld to
`desktop invalidate process executing on the handheld com-
`puter of FIG. 4;
`FIG. 15 is a flow chart of the process of the handheld to
`desktop invalidate process executing on the desktop com-
`puter of FIGS. 1C—1F;
`FIG. 16 is a flow chart of the process of the desktop to
`handheld create process executing on the desktop computer
`of FIGS 1C—1F;
`FIG. 17 is a flow chart of the process of the desktop to
`handheld create process executing on the handheld computer
`of FIG. 4;
`FIG. 18 is a flow chart of the process of the desktop to
`handheld modify process executing on the desktop computer
`of FIGS 1C—1F;
`FIG. 19 is a flow chart of the process of the desktop to
`handheld modify process executing on the handheld com-
`puter of FIG. 4;
`FIG. 20 is a flow chart of the process of the desktop to
`handheld update process executing on the desktop computer
`of FIGS. 1C—1F;
`
`

`

`5,974,238
`
`5
`FIG. 21 is a flow chart of the process of the desktop to
`handheld update process executing on the handheld com-
`puter of FIG. 4;
`FIG. 22 is a flow chart of the process of the desktop to
`handheld invalidate process executing on the desktop com-
`puter of FIGS 1C71F; and
`FIG. 23 is a flow chart of the process of the desktop to
`handheld invalidate process executing on the handheld com-
`puter of FIG. 4.
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENT
`
`Referring now to FIGS. 1A and 1B, two alternate views
`of a handheld computer, generally referred to by the letter H,
`according to the present invention are shown. The handheld
`computer H includes an outer housing 20 in which the
`components are contained. The top 22 of the housing 20
`preferably contains a rectangular opening 24 to allow vis-
`ibility of an LCD panel display 26 or other suitable Video
`display which also contains a digitizcr 110 FIG. 4) and a
`backlight 112. Apen 28 is used to interface with the digitizer
`110 and the display 26 to provide input. Preferably on the
`left side 30 of the housing 20 a hole 32 is present to allow
`the insertion of an AC adapter or DC power source providing
`battery charging energy to the computer H. At a bottom end
`34 of the housing 20 is a hinged door 36 which when pivoted
`down provides access to a cage 38 containing slots for
`receiving two PCMCIA cards 40 and for providing access to
`a battery cartridge 42 in which rechargeable batteries such as
`Ni-Cads or Nr s or conventional alkaline batteries are
`located. Preferably AA size batteries are utilized, though a
`camcorder or other standard, small battery could be utilized
`with a slight component rearrangement as necessary.
`Alternatively, the door 36 could be slidably engaged with the
`bottom end 34. The PCMCIA cards are readily interchange-
`able with the door open 36 and the battery cartridge 42 is
`readily removable to allow exchange of battery cartridges 42
`if desired.
`
`In FIG. IE it is shown that a top 44 of the housing 20
`contains two receptacles 46 and 48. Preferably the receptacle
`46 is an RJ—11 type receptacle for receiving a telephone
`connection, while the receptacle 48 is a similar spring clip
`type receptacle for receiving a special adapter cable as will
`be described below. A right side 45 of the housing 20
`contains an opening 47 to allow an internal speaker 61 a
`port. Additionally, the right side 45 includes an opening 41
`for allowing access to a keyboard port 43. Preferably the
`handheld computer H is approximately 4 inches wide, 6
`inches tall and 1 inch thick.
`
`Turning now to FIG. 1C, another embodiment of the
`handheld computer H of the present invention is shown. The
`processing electronics as well as the display 26A is housed
`by a base B. The body B also houses an ON/OFF switch 21.
`The display 26A of FIG. 1C is preferably 3"><5" in size, with
`a 480x240 pixel
`resolution.
`In FIG. 1C,
`the handheld
`computer H has pen input, as provided by the pen 28A, and
`a keyboard input, as provided by a keyboard 23. The
`keyboard 23 is preferably a QWERTY type keyboard which
`is connected to the processor via a keyboard cable 25.
`Further, the pen 28A has a pop-up housing 29 located on the
`keyboard 23 for accepting the pen 28A during periods where
`the handheld computer H is opened and ready for operation.
`Further,
`the handheld computer H has a receptacle 27
`located on the body B for accepting the pen 28A during
`periods of non-use. In such event,
`the pen 28A can be
`inserted into the rcccptaclc 27 and the keyboard 23 can be
`
`6
`interlocked with the body B such that the handheld computer
`H can be shipped. In general, pens 28 and 28A, as well as
`displays 26 and 26A are interchangeable and the pen 28A
`may be referred to generically as the pen 28. Similarly, the
`display 26A may be referred to generically as the display 26.
`Preferably, the handheld computer H of FIG. 1C operates
`with a Pegasus operating system which is a kernel of the
`Windows 95 API set, available from Microsoft Corporation
`in Redmond, Wash.
`Although the embodiment of FIG. 1C shows the keyboard
`23 being separated from the body B during operation, the
`invention also contemplates that a clamshell design can be
`used where the keyboard and the display are integrated into
`one article, with the display hingedly connected to the body
`and keyboard and adapted to be opened as one piece.
`In FIG. 1D the handheld computer H is shown as being
`wirelessly connected to the host computer C Via a wireless
`carrier. The wireless carrier may be based on the global
`system for mobile communications (GSM) standard, which
`is a digital cellular standard or other cellular technologies
`such as circuit switches or CDPD. Alternatively, the wireless
`carrier may be based on a two-way paging standard such as
`the personal Air Communications Technology (pACT).
`pACT is a narrowband, 900 Mz range personal communi-
`cations system (PCS) available from PCSI—Cirrus Logic
`
`Inc. and AT&T Wireless Services Inc. Further, a ReFLEX
`paging protocol, currently in use with SkyTel Mtel, Inc.,
`from Motorola Inc. of Schaumburg, Ill. can be used as well.
`The present invention contemplates that equivalent wire-
`less transmissions include all forms of radio frequency as
`well as infrared communication as discussed in the Infra-
`
`Red Data Association (IRDA) standard. The IRDA specifi-
`cations provide guidelines for link access, link management
`and for the physical transfer of data bits. The link access
`mechanism provides guidelines for the software which looks
`for other machines to connect or to sniff, to discover other
`machines, to resolve addressing conflicts, and to initiate a
`connection, to transfer data, and to cleanly disconnect. The
`link access standard specifies a frame and byte structure of
`the infrared packets as well as the error detection method-
`ology for the infrared communication. The IRDA specifica-
`tions for operating distance, viewing angle, optical power,
`data read, and noise immunity enable physical interconnec-
`tivity between various brands and type of equipment, such
`as the desktop computer C and the handheld computer H.
`Turning now to FIG. 1E, another communication link
`between the desktop computer C and the handheld computer
`H is shown. FIG. 1E shows the wireline technology—
`Internet combination to augment
`the wireless networks
`which may lack a ubiquitous infrastructure. FIG. IE is
`similar to FIG. 1D, with the addition that an Internet link is
`interposed between the desktop computer C and the wireless
`carrier. In FIG. 1E, the wireless carrier communicates with
`an Internet service provider via a suitable protocol such as
`TCP/IP protocol. Originally developed as a reliable com-
`puter network for connecting research institutions and mili-
`tary sites, the Internet has become the world’s most widely
`used computing network, where information is quickly and
`easily shared. Typically, data transmitted via the Internet via
`the World Wide Web still resembles that of the wireless
`
`packets, as the typical Web message size is small. Thus, in
`addition to wireless carriers, the handheld computer of the
`present invention can communicate with the desktop com-
`puter C Via land lines, via wireless lines, or other means,
`including the Internet and variants thereo,
`including
`“intranets”, or intra-corporation networks. These communi-
`cation mcdia mcld computing power with network and
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`

`

`5,974,238
`
`7
`wireless access, offering users significant leaps in produc-
`tivity and accessibility.
`In FIG. 1F the handheld computer H is shown installed in
`a cradle 49, which is directly connected to the host computer
`C. The cradle 49 connection and operation are known in the
`art. Exemplary cradle/handheld operation is disclosed in
`U.S. patent application Ser. No. 07/984,464, entitled
`“HANDHELD COMPUTER WITH AUTOMATIC DATA
`SYNCHRONIZATION WITH HOST COMPUTER”,
`assigned to the assignee of the present invention, which is
`hereby incorporated by