Bibliography

1

C. E. Perkins, Ad hoc Networking.
Addison-Wesley, first ed., 2000.

2

``3COM Palm Inc..'' http://www.palm.com.

3

P. Mochapetris, ``DNS: The Domain Name System,'' RFC 1034, Network Working Group, ISI, November 1987.

4

P. Vixie, S. thomson, Y.Rekhter, and J. Bound, ``Dynamic Updates in the Domain Name System (DNS UPDATE),'' RFC 2136, Network Working Group, ISI, April 1997.

5

M. Ohta, ``RFC 1995: Incremental Zone Transfer in DNS,'' internet-draft, Tokyo Institute of Technology, August 1996.

6

J. Kangasharju and K. W. Ross, ``A Replicated Architecture for the Domain Name System,'' in INFOCOM (2), pp. 660-669, 2000.

7

A. Tridgell and P. Mackerras, ``The Rsync Algorithm,'' Tech. Rep. TR-CS-96-05, Australian National University, 1996.

8

J. J. Kistler and M. Satyanarayanan, ``Disconnected Operation in the Coda File System,'' in Thirteenth ACM Symposium on Operating Systems Principles, (Asilomar Conference Center, Pacific Grove, U.S.), pp. 213-225, ACM Press, 1991.

9

M. Satyanarayanan, ``Coda: A Highly Available File System for a Distributed Workstation Environment,'' in Proceedings of the Second IEEE Workshop on Workstation Operating Systems, (Pacific Grove, CA), September 1989.

10

M. Harchol-Balter, T. Leighton, and D. Lewin, ``Resource Discovery in Distributed Networks,'' in 18th Annual ACM-SIGACT/SIGOPS Symposium on Principles of Distributed Computing, (Atlanta, GA), May 1999.

11

K. Guo, M. Hayden, R. v. Renesse, W. Vogels, and K. P. Birman, ``GSGC: An Efficient Gossip-Style Garbage Collection Scheme for Scalable Reliable Multicast,'' tech. rep., Cornell University, December 1997.

12

S. Agarwal, D. Starobinski, and A. Trachtenberg, ``On the scalability of data synchronization protocols for pdas and mobile devices,'' Special Issue of IEEE Networks on Scalability in Communication Networks, 2002.
to appear.

13

A. Trachtenberg, D. Starobinski, and S. Agarwal, ``Fast PDA Synchronization Using Characteristic Polynomial Interpolation,'' in Proceedings of the IEEE Infocom, 2002.
To appear.

14

Y. Minsky, A. Trachtenberg, and R. Zippel, ``Set Reconciliation with Nearly Optimal Communication Complexity,'' Tech. Rep. TR2000-1813, Cornell University, 2000.

15

A. Yaar, D. Starobinski, and A. Trachtenberg, ``Engineering Scalable Data Synchronization For A Personal Digital Assistant.'' in preparation, 2002.

16

A. Silberschatz, H. F. Korth, and S. Sudarshan, Datbase System Concepts.
McGraw Hill, third ed., 1997.

17

``IEEE 1394.'' http://computer.org/multimedia/articles/firewire.htm.

18

``Universal Serial Bus.'' http://www.usb.org.

19

``Intellisync.'' http://www.pumatech.com.

20

M. Denny and C. Wells, ``EDISON: Enhanced Data Interchange Services Over Networks,'' May 2000.
class project, UC Berkeley.

21

D. B. Terry, M. M. Theimer, K. Petersen, A. J. Demers, M. J. Spreitzer, and C. H. Hauser, ``Managing Update Conflicts in Bayou, a Weakly Connected Replicated Storage System,'' ACM Operating System Review, pp. 172-182, December 1995.

22

U. Cetintemel, P. Keleher, and M. Franklin, ``Support for Speculative Update Propagation and Mobility in Deno,'' 1999.

23

D. Ratner, P. L. Reiher, G. J. Popek, and R. G. Guy, ``Peer Replication with Selective Control,'' in Proceedings of the International Conference on Mobile Data Access, pp. 169-181, 1999.

24

``SyncML Standard.'' http://www.syncml.org.

25

M. Rabinovich, N. H. Gehani, and A. Kononov, ``Scalable Update Propagation in Epidemic Replicated Databases,'' in Extending Database Technology, pp. 207-222, 1996.

26

A. Trachtenberg, D. Starobinbki, and S. Agarwal, ``Fast PDA Synchronization Using Characteristic Polynomial Interpolation,'' Tech. Rep. TR2001-03, Boston University, 2001.

27

``Avantgo Mobile Internet Service.'' http://avantgo.com/products/ individuals/basic.html.

28

``Infrared Data Association.'' http://www.irda.org.

29

``Motorola Seminconductor Products Sector.'' http://e-www.motorola.com/.

30

A. Silberschatz, H. F. Korth, and S. Sudarshan, Database System Concepts.
McGraw-Hill, third ed., 1999.

31

``Pilot PRC-Tools.'' http://sourceforge.net/projects/prc-tools/.

32

N. Rhodes and J. McKeehan, Palm Programming: The Developer's Guide.
O'Reilly, first ed., 1999.

33

S. Weisberg, Applied Linear Regression.
John Wiley and Sons, Inc., 1985.

34

B. S. Davie and L. L. Peterson, Computer Networks: A Systems Approach.
Morgan Kaufman Publishers, second ed., 2000.

35

A. S. Tanenbaum, Computer Networks.
Prentice-Hall Inc., 3 ed., 1995.

36

A. Demers, D. H. Greene, C. Hause, W. Irish, and J. Larson, ``Epidemic Algorithms for Replicated Database Maintenance,'' in Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, (Vancouver, British Columbia, Canada), pp. 1-12, ACM, August 1987.

37

G. Apostolopoulos, R. Guerin, S. Kamat, and S. K. Tripathi, ``Quality of Service Based Routing: A Performance Perspective,'' in SIGCOMM, pp. 17-28, 1998.

38

A. Shaikh, J. Rexford, and K. G. Shin, ``Evaluating the impact of stale link state on quality-of-service routing,'' IEEEACM Transactions on Networking, vol. 9, pp. 162-176, April 2001.

39

T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction To Algorithms.
MIT Press and McGraw-Hill Book Company, 6th ed., 1990.

40

Y. Minsky and A. Trachtenberg, ``Practical Set Reconciliation.'' in preparation, 2002.

Curriculum Vitae

Sachin Agarwal was born in the small south Indian town of Tumkur, on February 11, 1979, son of Rashmi Agarwal and Arun Kumar Agarwal. In 2000 he graduated with distinction from the Regional Engineering College, Warangal, India with a Bachelor of Technology degree in Electronics and Communication Engineering. At college, he was a recipient of the college merit scholarship. He entered the graduate program in Computer Engineering offered by Boston University's College of Engineering in Fall 2000, where he also worked as a graduate research assistant in the Networking and Information Systems Laboratory. While working there, he was the co-author of the following publications

• A. Trachtenberg, D. Starobinski, and S. Agarwal, ``Fast PDA Synchronization Using Characteristic Polynomial Interpolation", in the Proceedings of the IEEE INFOCOM 2002.
• S. Agarwal, D. Starobinski, and A. Trachtenberg, ``On the Scalability of Data Synchronization Protocols for PDAs and Mobile Devices", special issue of the IEEE Network Magazine: Scalability in Communication Networks, July/August 2002.

He was awarded the NSF/Corporate travel award for the IEEE INFOCOM 2002 conference. This thesis marks the end of his master's trek - uphill, but with an understanding advisor Dr. Ari Trachtenberg who offered exciting research and generous financial support, he has fond memories of all the times spent getting there. So much so that he continues to work towards his doctoral degree at Boston University, on the banks of the Charles river in Boston, Massachusetts.