United States Patent [19]
`Chase, Jr.
`
`[54] AUTOMATIC DATA SYNCHRONIZATION
`BETWEEN A HANDHELD AND A HOST
`COMPUTER USING PSEUDO CACHE
`INCLUDING TAGS AND LOGICAL DATA
`ELEMENTS
`
`Inventor: Charlie David Chase, J r., Spring, TeX.
`
`Assignee: Compaq Computer Corporation,
`Houston, TeX.
`
`Appl. No.: 08/689,304
`Filed:
`Aug. 7, 1996
`
`Int. Cl.6 ............................ .. G06F 1/00; G06F 15/00;
`G06F 17/30; G06F 15/62
`US. Cl. .............................. .. 395/200.78; 395/200.76;
`395/821; 395/892; 395/893; 707/200; 707/203;
`707/204
`Field of Search ....................... .. 395/200.78, 200.76,
`395/821, 892, 893; 707/200, 203, 204
`
`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/82544
`2/1995 Crozier .................................. .. 395/161
`
`OTHER PUBLICATIONS
`
`Personal Air Communications Technology Brochure No.
`32956.
`PSCI (Paci?c Communication Sciences, Inc.) Brochure
`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.
`
`US005 97423 8A
`[11] Patent Number:
`[45] Date of Patent:
`
`5,974,238
`Oct. 26, 1999
`
`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 PDA Hand—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 &
`Feld, 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 modi?ed 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
`
`144
`
`PSEUDO-CACHE
`
`112
`BACK-
`LIGHT
`
`[Cl]
`PANEI
`
`25
`
`110
`
`DIGITIZER
`
`61
`
`+50—Ib—|
`135
`
`102
`
`Y
`
`RAM
`
`I
`
`CUMBINATIHN __—-‘:|/
`
`CHIP
`
`mummcesson
`
`1J1
`
`FAX/MODEM
`
`45
`
`100
`
`l
`
`11a" ~14
`
`l
`
`m
`MOSFET
`GATES
`
`130
`
`_
`
`_
`
`PUWER 43.3,»5.
`SUPPLV 411,40
`
`lrr
`
`wmaess
`cmcumw
`
`1"?
`
`PCMElA
`SLUTlSl
`
`38
`
`Apple, Exhibit 1056, Page 1
`
`

`
`5,974,238
`Page 2
`
`OTHER PUBLICATIONS
`
`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
`jurnp—start handhelds”, Electronic Engineering Tirnes, Aug.
`8, 1996, Issue 909, pp. 10, 16.
`
`Grace, Elden, “RF Filter Technology for Wireless Commu
`nications”, Wireless Design & Developrnent, p. 8.
`
`Sharp Model ZR—5700/ZR—5800 Keyboard Enhanced Per
`sonal Digital Assistant—Zaurus Operational Manual, pp.
`1—61.
`
`Apple, Exhibit 1056, Page 2
`
`

`
`U.S. Patent
`
`Oct.26, 1999
`
`Sheet 1 0f25
`
`5,974,238
`
`FIG. 1A
`
`FIG. 1 B
`
`Apple, Exhibit 1056, Page 3
`
`

`
`U.S. Patent
`
`Oct.26, 1999
`
`Sheet 2 0f25
`
`5,974,238
`
`Apple, Exhibit 1056, Page 4
`
`

`
`U.S. Patent
`
`Oct.26, 1999
`
`Sheet 3 0f25
`
`5,974,238
`
`Apple, Exhibit 1056, Page 5
`
`

`
`U.S. Patent
`
`Oct.26, 1999
`
`Sheet 4 0f25
`
`5,974,238
`
`FIG. 1E
`
`Apple, Exhibit 1056, Page 6
`
`

`
`U.S. Patent
`
`5,974,238
`
`n2. .QE
`
`Apple, Exhibit 1056, Page 7
`
`

`
`U.S. Patent
`
`Oct.26, 1999
`
`Sheet 6 0f25
`
`5,974,238
`
`55
`
`42
`
`56
`
`46
`
`58
`
`LC] |_J’
`
`43
`
`48-"
`
`46/
`
`58]
`
`L----------|
`_i--43
`|
`'__________
`___|
`|
`|
`|
`‘1'
`r——————————|
`I
`\J.’_43
`|_______.___J
`
`55J 154 \52
`FIG. 3
`
`Apple, Exhibit 1056, Page 8
`
`

`
`Apple, Exhibit 1056, Page 9
`
`

`
`U.S. Patent
`
`Oct.26, 1999
`
`Sheet 8 0f25
`
`5,974,238
`
`20o
`
`CREATE
`
`PRIVATE
`
`<- _ _ _ _ — _ — _ _ _ _
`
`UPDATE
`
`CLEAN
`SHARED
`
`MODIFY
`
`202
`
`— — — — — — — — — — — >
`
`INVALIDATE
`
`RESTORE
`
`204
`
`206
`
`DIRTY
`SHARED
`
`III-P216
`“"1
`
`MG
`SI
`SI
`
`240
`218
`241 SIGNATURE /
`242 TABLE
`243
`
`FIELD MAPPING -/25° HELD
`FIELD MAPPING -\
`MAPPING
`FIELD MAPPING -
`TABLE
`
`220
`
`FIG. 7
`
`Apple, Exhibit 1056, Page 10
`
`

`
`U.S. Patent
`
`Oct.26, 1999
`
`Sheet 9 0f25
`
`5,974,238
`
`210\
`COHERENCY
`PROTOCOL
`ENGINE
`
`SYNCHRONIZATIUN SOFTWARE
`r214
`DATA
`SYNCHHONIZATIUN
`ENGINE
`
`j
`
`SIGNATURES
`
`HANDHELD
`
`[224
`I
`SCHEDULER ‘I
`_{_ _[_JA_TA E_NGINE_ I
`_ _ _ _ L2_2_81
`_: PHUNELIST
`l
`LPILTAENEIHEJ
`______ _ _ _
`I TRAVELAGENT l
`
`f226
`SCHEDULER
`PIM
`
`230
`PHUNELIST
`PIM
`C 234
`TRAVELAGENT
`
`DESKTOP APPS
`
`225 \ sGIIEnuIEII
`PIN
`
`f 233
`/ 229
`PHONELIST
`TRAVELAGENT
`PIN
`PIM
`
`DATA sIINGAPI
`
`PIN DATA
`SYNC ENGINE
`
`CUHEHENCYPRUTUCOL
`ENGINE
`
`223
`
`215
`
`211
`
`213
`
`FIG. 6B
`
`Apple, Exhibit 1056, Page 11
`
`

`
`U.S. Patent
`
`Oct.26, 1999
`
`Sheet 10 0f 25
`
`5,974,238
`
`HTD CREATE HANDHELD
`
`299
`
`WRITE TD RAM
`
`WRITE TD
`PREDETERMINED
`RANGEI’IN RAM
`
`302
`
`HIT DN
`RECORD ID
`?
`
`CREATE HANDHELD TAG
`
`SET EXCLUSIVE BIT IN
`HANDHELD TAG
`
`INTERRUPT GENERATED
`
`| CUNSTRUCT CREATE PACKET
`I
`[314
`| sewn PACKET T0 DESKTOP
`
`318
`
`CLEAR EXCLUSIVE BIT
`IN HANDHELD TAG
`
`FIG. 8
`
`Apple, Exhibit 1056, Page 12
`
`

`
`U.S. Patent
`
`Oct.26, 1999
`
`Sheet 11 0f25
`
`5,974,238
`
`HTD CREATE DESKTOP
`
`322
`N
`
`RECEIVE
`CREATE?PACKET
`
`324
`
`SLEEP
`
`Y
`
`326
`
`f 328
`
`f 334
`
`WAKE UP DATA
`SYNCHRONIZER
`I
`PARSE CREATE PACKET TO
`EXTRACT HANDHELD RECORD ID
`& FIELD INDICES
`f 330
`I
`CREATE DESKTOP TAG
`L
`f 332
`SET EXCLUSIVE BIT
`IN DESKTOP TAG
`I
`ACCESS PIM
`APPLICATION DATA SET
`& ADD NEW ENTRY
`f 336
`I
`UPDATE DESKTOP TAG
`SIGNATURE
`ISIGI
`L
`
`[337
`
`CLEAR EXCLUSIVE BIT
`IN DESKTOP TAG
`f 338
`I
`SEND ACKNOWLEDGMENT
`PACKAGE TO HANDHELD
`
`i>
`
`FIG. 9
`
`Apple, Exhibit 1056, Page 13
`
`

`
`U.S. Patent
`
`Oct.26, 1999
`
`Sheet 12 0f25
`
`5,974,238
`
`WRITE TO RAM
`
`339
`
`340
`
`WRITE TO
`PREDETERMINED
`RANGE IN RAM
`
`342
`
`HIT ON
`REOO?RD ID
`
`352
`
`SET HANDHELD
`MODIFIED BIT
`I
`CDNSTRUCT OR
`MODIFY PACKET
`f 354
`I
`SEND MODIFY PACKET
`TO DESKTOP
`
`DESKTOP
`ACKNOWLEDGMENT
`
`358
`
`CONSTRUCT UPDATE
`PACKET
`
`361
`
`FIG. 10
`
`Apple, Exhibit 1056, Page 14
`
`

`
`U.S. Patent
`
`Oct.26, 1999
`
`Sheet 13 0f25
`
`5,974,238
`
`(Hm MODIFY DESKTOP )
`
`364
`
`WAKE UP DATA
`SYNCHRDNIZER
`I
`PAFISE MODIFY PACKET TO
`EXTRACT HID & FIELD INDICES
`
`f 368
`
`DETECTED ON
`
`EXTRACT
`CORRESPONDING DID
`I f 374
`SET DESKTOP TAG
`MODIFY BIT
`f 376
`I
`SEND ACKNOWLEDGMENT
`PACKET TO HANDHELD
`
`FIG. 11
`
`Apple, Exhibit 1056, Page 15
`
`

`
`U.S. Patent
`
`Oct.26, 1999
`
`Sheet 14 0f25
`
`5,974,238
`
`HTD UPDATE HANDHELD
`/ 378
`
`CDNSTRUCT
`UPDATE PACKET
`
`f 380
`SEND UPDATE PACKET
`TD DESKTDP
`
`382
`
`DESKTDP
`ACKNOWLEDGMENT
`PACKET
`RECEIIVED
`
`f 386
`CLEAR HANDHELD
`MDDIFY BIT
`
`FIG. 12
`
`384
`
`Apple, Exhibit 1056, Page 16
`
`

`
`U.S. Patent
`
`Oct. 26, 1999
`
`Sheet 15 0f 25
`
`5,974,238
`
`HTD UPDATE DESKTOP
`
`392
`
`PARSE UPDATE PACKET
`TO EXTRACT RECORD ID
`& FIELD INDICES
`
`FIND
`MATCH ON HID IN
`
`404
`
`EXTRACT
`CORRESPONDING OID
`I
`f 402
`ACCESS PIM
`APPLICATION DATA SET
`& PERFORM UPDATE
`I
`UPDATE DESKTOP TAG
`SIGNATURE
`ISIGI
`f 406
`I
`CLEAR DESKTOP TAG
`MODIFIED BIT
`f 408
`I
`SEND ACKNOWLEDGMENT
`PACKET TO HANDHELD
`DEVICE
`
`FIG. 13
`
`Apple, Exhibit 1056, Page 17
`
`

`
`U.S. Patent
`
`Oct. 26, 1999
`
`Sheet 16 0f 25
`
`5,974,238
`
`( HTD INVALIDATE HANDHELD )
`409
`
`WRITE TO RAM
`
`WRITE
`TO RAM WITHIN
`PROGRAMMED
`RANGE
`?
`
`RECORD ID
`MARKED FOR
`
`SHARING
`
`418
`
`SET HANDHELD TAG
`DELETE 8| MODIFY BITS
`I
`f 420
`INTERRUPT HANDHELD
`PROCESSOR
`I
`CONSTRUCT
`INVALIDATE PACKET
`I
`SEND INVALIDATE
`PACKET TO DESKTOP
`
`f 422
`
`f 424
`
`425
`
`RECEIVE
`ACKNOWLEDGE
`PACKET TO
`HANO’HELD
`
`CLEAR HANDHELD
`TAG MODIFY BIT
`
`/- 428
`
`FIG. 14
`
`Apple, Exhibit 1056, Page 18
`
`

`
`U.S. Patent
`
`041.26, 1999
`
`Sheet 17 0f25
`
`5,974,238
`
`(Hm INVALIDATE DESKTOP)
`
`f 440
`
`442
`
`PARSE INVALIDATE PACKET
`T0 EXTRACT RECORD ID
`AND FIELD INDICES
`I
`f 436
`EXTRACT MATCH IN
`DESKTOP TAG AND DID
`I
`f 438
`SET DESKTOP TAG
`MODIFY BIT
`I
`ACCESS PIM
`APPLICATION DATA SET
`AND PERFORM DELETION
`I
`SET DESKTOP TAG
`DELETED BIT
`f- 446
`I
`CLEAR DESKTOP TAG
`MODIFY BIT
`f- 448
`I
`SEND ACKNOWLEDGMENT
`PACKET TO HANDHELD
`
`ab
`
`FIG. 15
`
`Apple, Exhibit 1056, Page 19
`
`

`
`U.S. Patent
`
`Oct. 26, 1999
`
`Sheet 18 0f 25
`
`5,974,238
`
`(0TH CREATE DESKTOP)
`
`NEW
`RECORD IN PIM
`DAT'A7 SET
`
`Y
`
`452
`
`454
`
`CREATE DESKTOP TAG
`ID & SET MODIFIED BIT
`I
`CONSTRUCT
`CREATE PACKET
`f 456
`I
`SEND CREATE PACKET
`TO HANDHELD
`
`RECEIVE
`ACKNOWLEDGE
`PACKET FROM
`HANDHELD
`‘.7
`Y
`
`ADD HANDHELD ID TO
`DESKTOP TAG
`I
`CLEAR DESKTOP
`MODIFIED BIT
`
`462
`
`f 454
`
`FIG. 16
`
`Apple, Exhibit 1056, Page 20
`
`

`
`Apple, Exhibit 1056, Page 21
`
`

`
`Apple, Exhibit 1056, Page 22
`
`

`
`Apple, Exhibit 1056, Page 23
`
`

`
`Apple, Exhibit 1056, Page 24
`
`

`
`Apple, Exhibit 1056, Page 25
`
`

`
`Apple, Exhibit 1056, Page 26
`
`

`
`Apple, Exhibit 1056, Page 27
`
`

`
`Apple, Exhibit 1056, Page 28
`
`

`
`Apple, Exhibit 1056, Page 29
`
`

`
`Apple, Exhibit 1056, Page 30
`
`

`
`Apple, Exhibit 1056, Page 31
`
`

`
`Apple, Exhibit 1056, Page 32
`
`

`
`Apple, Exhibit 1056, Page 33
`
`

`
`Apple, Exhibit 1056, Page 34
`
`

`
`Apple, Exhibit 1056, Page 35
`
`

`
`Apple, Exhibit 1056, Page 36
`
`

`
`Apple, Exhibit 1056, Page 37
`
`

`
`Apple, Exhibit 1056, Page 38
`
`

`
`Apple, Exhibit 1056, Page 39
`
`

`
`Apple, Exhibit 1056, Page 40