Publications and Technical Reports

David P. Anderson

Distributed thinking and Bossa

Westphal, A.J., et al. "Search for Contemporary Interstellar Dust in the Stardust Collector", 38th Lunar and Planetary Science Conference, March 12-16, 2007, League City, TX. p. 1457.

Volunteer Computing and BOINC

BOINC (Berkeley Open Infrastructure for Network Computing) is a software platform for volunteer computing (i.e., SETI@home-type projects).

I. Buch, M. J. Harvey, T. Giorgino, D. P. Anderson, and G. De Fabritiis. High-Throughput All-Atom Molecular Dynamics Simulations Using Distributed Computing. To appear, J. Chem. Inf. Model.

Oded Nov, Ofer Arazy, and David P. Anderson. Crowdsourcing for science: understanding and enhancing SciSourcing contribution. The Changing Dynamics of Scientific Collaborations, workshop at CSCW 2010, Savannah GA, Feb. 7 2010.

Artur Andrzejak, Derrick Kondo and David P. Anderson. "Exploiting Non-Dedicated Resources for Cloud Computing". 12th IEEE/IFIP Network Operations & Management Symposium (NOMS 2010), Osaka, Japan April 19-23, 2010.

Nagarajan Kanna, Jaspal Subhlok, Edgar Gabriel, Eshwar Rohit and David Anderson. "A Communication Framework for Fault-tolerant Parallel Execution". The 22nd International Workshop on Languages and Compilers for Parallel Computing, Newark, Delaware, Oct 8-10 2009.

Travis Desell, Anthony Waters, Malik Magdon-Ismail, Boleslaw Szymanski, Carlos Varela, Matthew Newby, Heidi Newberg, Andreas Przystawik and David Anderson. Accelerating the MilkyWay@Home volunteer computing project with GPUs. In 8th International Conference on Parallel Processing and Applied Mathematics (PPAM 2009), Wroclaw, Poland, September 2009.

Abbott, B.P. et al. Einstein@Home search for periodic gravitational waves in early S5 LIGO data. Phys. Rev. D 80, 042003 (2009).

Eric M. Heien, David P. Anderson, and Kenichi Hagihara. Computing Low Latency Batches with Unreliable Workers in Volunteer Computing Environments. To appear, Journal of Grid Computing.

Trilce Estrada, Michela Taufer, David Anderson. Performance Prediction and Analysis of BOINC Projects: An Empirical Study with EmBOINC. To appear, Journal of Grid Computing.

Bahman Javadi, Derrick Kondo, Jean-Marc Vincent, David P. Anderson. Mining for Availability Models in Large-Scale Distributed Systems:A Case Study of SETI@home. 17th Annual Meeting of the IEEE/ACM International Symposium on Modelling, Analysis and Simulation of Computer and Telecommunication Systems, Sept 21-23 2009, London.

Derrick Kondo, Bahman Javadi, Paul Malecot, Franck Cappello and David Anderson. Cost-Benefit Analysis of Cloud Computing versus Desktop Grids. 18th International Heterogeneity in Computing Workshop, May 25 2009, Rome.

Trilce Estrada, Michela Taufer, Kevin Reed, David Anderson. EmBOINC: An Emulator for Performance Analysis of BOINC Projects. 3rd Workshop on Desktop Grids and Volunteer Computing Systems (PCGrid 2009), May 29, 2009, Rome.

David P. Anderson and Kevin Reed. Celebrating Diversity in Volunteer Computing. Hawaii International Conference on System Sciences (HICSS), January 5-8, 2009. (Best Paper Award)

Artur Andrzejak, Derrick Kondo, and David P. Anderson. Ensuring Collective Availability in Volatile Resource Pools via Forecasting. 19th IFIP/IEEE International Workshop on Distributed Systems: Operations and Management (DSOM 2008), Samos Island, Greece, September 22-26, 2008.

Derrick Kondo, Artur Andrzejak, and David P. Anderson. On Correlated Availability in Internet-Distributed Systems. 9th IEEE/ACM International Conference on Grid Computing (Grid 2008), Tsukuba, Japan, Sept 29 - Oct 1 2008.

B. Abbott et al. Einstein@Home search for periodic gravitational waves in LIGO S4 data. Physical Review D, 79:022001, 2009.

D. Kondo, D.P. Anderson, and J. McLeod VII. Performance Evaluation of Scheduling Policies for Volunteer Computing. 3rd IEEE International Conference on e-Science and Grid Computing, Bangalore, India, 10-13 December 2007.

D.P. Anderson and J. McLeod VII. Local Scheduling for Volunteer Computing. Workshop on Large-Scale, Volatile Desktop Grids (PCGrid 2007) held in conjunction with the IEEE International Parallel & Distributed Processing Symposium (IPDPS), March 30, 2007, Long Beach.

T. Estrada, D. Flores, M. Taufer, P. Teller, A. Kerstens, and D. Anderson. The Effectiveness of Threshold-based Scheduling Policies. 2nd IEEE International Conference on e-Science and Grid Computing. Dec. 4-6, 2006, Netherlands.

D.P. Anderson, C. Christensen, and B. Allen. Designing a Runtime System for Volunteer Computing, Supercomputing '06 (The International Conference for High Performance Computing, Networking, Storage and Analysis), Tampa, November 2006.

D.P. Anderson and G. Fedak. The Computational and Storage Potential of Volunteer Computing, IEEE/ACM International Symposium on Cluster Computing and the Grid, Singapore, May 16-19, 2006.

D.P. Anderson, E. Korpela, and R. Walton. High-Performance Task Distribution for Volunteer Computing. 1st IEEE International Conference on e-Science and Grid Computing, Melbourne, Dec. 2005, pp. 196-203.

M. Taufer, P.J. Teller, D.P. Anderson, and C.L. Brooks III. Metrics for Effective Resource Management in Global Computing Environments. in 1st IEEE International Conference on e-Science and Grid Computing, Melbourne, Dec. 2005, pp. 204-211.

M. Taufer, D. Anderson, P. Cicotti, C.L. Brooks III. Homogeneous Redundancy: a Technique to Ensure Integrity of Molecular Simulation Results Using Public Computing. Heterogeneous Computing Workshop, International Parallel and Distributed Processing Symposium 2005, Denver, CO, April 4-8, 2005.

David P. Anderson. BOINC: A System for Public-Resource Computing and Storage. 5th IEEE/ACM International Workshop on Grid Computing, November 8, 2004, Pittsburgh, USA, pp 1-7.

D. P. Anderson and J. Kubiatowicz. The World-Wide Computer. Scientific American, March 2002.

SETI@home

SETI@home is a distributed computing project; it is currently the world's largest computation and the most powerful computer.

D. P. Anderson, J. Cobb, E. Korpela, M. Lebofsky, and D. Werthimer. SETI@home: An experiment in public-resource computing. Communications of the ACM, Nov. 2002, Vol. 45 No. 11, pp. 56-61. Available in the ACM Digital Library.

D. P. Anderson, Eric Korpela, Jeff Cobb, Bob Bancay. A general distributed computing platform for SETI. Bioastronomy 2002.

D. P. Anderson. SETI@home. A chapter in "Peer-to-Peer: Harnessing the power of disruptive technologies", edited by Andy Oram, O'Reilly and Assoc, 2001.

Korpela, E., Werthimer, D., Anderson, D., Cobb, J., and Lebofsky, M., SETI@home: Massively Distributed Computing for SETI, Computing in Science and Engineering, 3, 1, 78. Available in the ACM Digital Library.

Werthimer, D., Anderson, D., Bowyer, C. S., Cobb, J., Heien, E., Korpela, E., Lampton, M., Lebofsky, M., Marcy, G.W., McGarry, M., & Treffers, D. Berkeley radio and optical SETI programs: SETI@home, SERENDIP, and SEVENDIP, Proc. SPIE, 4273, 104, 2001.

D. P. Anderson, D. Werthimer, J. Cobb, E. Korpela, M. Lebofsky, D. Gedye, W. Sullivan III. SETI@home: Internet Distributed Computing for SETI. In Bioastronomy '99 - A New Era in Bioastronomy, ASP Conference Series 213.

W. T. Sullivan, III, D. Werthimer, S. Bowyer, J. Cobb, D. Gedye, D. Anderson. A new major SETI project based on Project SERENDIP data and 100,000 personal computers. Published in: "Astronomical and Biochemical Origins and the Search for Life in the Universe", Proc. of the Fifth Intl. Conf. on Bioastronomy. 1997.

SonicSystem/MediaNet

Papers about my work at Sonic Solutions from 1992 to 1995. The first distributed system for professional audio editing. Disk/SCSI bus/network scheduling policies. Resource reservation algorithm. High-speed transport protocol for FDDI. High-performance file system with realtime guarantees. Client caching/readahead system for high-performance remote file access.

D.P. Anderson, "Device Reservation in Audio/Video Editing Systems", ACM Transactions on Computer Systems 15(2), May 1997, pp. 111-133. Available in the ACM Digital Library.

D. P. Anderson, R. J. Doris, and J. A. Moorer, "A Distributed Computer System for Professional Audio", ACM Multimedia '94, San Francisco, Oct. 1994. Available in the ACM Digital Library.

D. P. Anderson, J. A. Moorer and J. M. Roth, "Performance Issues in Digital Audio Networks", 95th Convention of the Audio Engineering Society, New York, Oct. 7-10, 1993.

D. P. Anderson, R. Doris, J. A. Moorer, J. Reichbach, J. Roth and B. Tellegen, "High-Speed Networking for Professional Digital Audio". Audio Engineering Society UK Conference on Digital Audio Interchange, London, May 1993.

D. P. Anderson, Nimrod Megiddo, and Moni Naor. The Minimum Reservation Rate Problem in Digital Audio/Video Systems. 2nd Israel Symposium on Theory, Natanya, Israel, June 7 - 9, 1993.

Device Scheduling and Reservation for Audio/Video

A unified end-to-end approach to device scheduling for audio/video traffic, with guaranteed performance, in general-purpose distributed systems. Workload/delay model. Scheme for dividing end-to-end delay among resources based on economics. Scheduling policies for networks and CPUs.

D. P. Anderson, "Meta-Scheduling for Distributed Continuous Media", ACM Transactions on Computer Systems 11(3), Aug. 1993, 226-252. Also Technical Report No. 90/599, CS Div., EECS Dept., UC Berkeley, October 1990. Available in the ACM Digital Library.

D. P. Anderson, S. Tzou, R. Wahbe, R. Govindan and M. Andrews, "Support for Continuous Media in the DASH System", Proceedings of the 10th International Conference on Distributed Computing Systems, Paris, May 1990. Also Technical Report No. 89/537, CS Div., EECS Dept., UC Berkeley, 1989.

D. P. Anderson and R. G. Herrtwich, "Resource Management for Digital Audio and Video", IEEE Workshop on Real-Time Operating Systems and Software, Charlottesville, May 1990, 99-103.

D. P. Anderson and R. G. Herrtwich, "Resource Management in Distributed Multimedia Systems – A Solution for the Internet", IFIP/IEEE Workshop on Distributed Systems: Operations and Management, Berlin, October 1990.

D. P. Anderson, R. G. Herrtwich and C. Schaefer, "SRP: A Resource Reservation Protocol for Guaranteed–Performance Communication in the Internet", Technical Report No. 90/562, CS Div., EECS Dept., UC Berkeley, February 1990.

D. P. Anderson, "A Software Architecture for Network Communication", Proceedings of the 8th International Conference on Distributed Computing Systems, San Jose, California, June 1988. Also Technical Report No. 87/386, CS Div., EECS Dept., UC Berkeley, 1987.

File Systems for Audio/Video

Formal semantics of real-time file access taking buffer space and rate variations into account. Disk scheduling policy that accommodates realtime, non-realtime traffic, optimizes non-realtime performance subject to hard realtime guarantee.

D. P. Anderson, Y. Osawa and R. Govindan, "A File System for Continuous Media", ACM Transactions on Computer Systems, 10(4), Nov. 1992, 311-337. Also Technical Report No. 91/646, CS Div., EECS Dept., UC Berkeley, 8/91. Available in the ACM Digital Library.

D. P. Anderson, Y. Osawa and R. Govindan, "The Continuous Media File System", Proc. of the USENIX Summer 92 Conference, San Antonio.

Operating System Mechanisms for Audio/Video

Mechanisms for deadline scheduling of lightweight processes in separate address spaces with minimal kernel calls; mechanisms for flow-controlled data streams between address spaces (user and/or kernel) with minimal kernel calls, no copying. Process structure for realtime network protocols.

R. Govindan and D. P. Anderson, "Scheduling and IPC Mechanisms for Continuous Media", 13th Symposium on Operating System Principles, Pacific Grove, CA, October 1991, 68-80. Also Technical Report No. 91/622, CS Div., EECS Dept., UC Berkeley, March 1991. Available in the ACM Digital Library.

D. P. Anderson, L. Delgrossi and R. G. Herrtwich, "Process Structure and Scheduling in Real- Time Protocol Implementations", Proc. Kommunikation in Verteilten Systemen, February 1991. Also Technical Report 90-021, International Computer Science Institute, June 1990.

D. P. Anderson, "The Workstation as Global Communication Interface", IEEE Conference on Workstation Operating Systems, Monterey, Calif., April 1989.

D. P. Anderson and R. Wahbe. "A Framework for Multimedia Communication in a General-Purpose Distributed System". Technical Report No. 89/498, CS Div., EECS Dept., UC Berkeley, March 31, 1989.

Audio/Video Servers and Toolkits

A server that provides concurrent remote access to audio/video hardware, and provides mechanisms for synchronizing multiple streams of data. A C++-based toolkit for writing networked, multi-user audio/video applications such as teleconferencing with file record/playback.

D. P. Anderson and P. Chan, "Toolkit Support for Multiuser Audio/Video Applications", Computer Communications, 15(6), July/Aug. 1992, 403-408. Also presented at the 2nd International Workshop on Network and Operating System Support for Digital Audio and Video, Nov. 1991, Heidelberg, Germany.

D. P. Anderson and G. Homsy, "A Continuous Media I/O Server and its Synchronization Mechanism", IEEE Computer, October 1991. Available in the ACM Digital Library.

D. P. Anderson, R. Govindan and G. Homsy, "Abstractions for Continuous Media in a Network Window System", International Conference on Multimedia Information Systems, Singapore, Jan 1991. Also Technical Report No. 90/596, CS Div., EECS Dept., UC Berkeley, Sept. 1990.

D. P. Anderson and G. Homsy, "Synchronization Policies and Mechanisms in a Continuous Media I/O Server", Technical Report No. 91/617, CS Div., EECS Dept., UC Berkeley, February 1991.

G. Homsy, R. Govindan and D. P. Anderson, "Implementation Issues for a Network Audio/Video Server", Technical Report No. 90/597, CS Div., EECS Dept., UC Berkeley, September 1990.

D. P. Anderson, R. Govindan, G. Homsy and R. Wahbe, "Integrated Continuous Media: A Framework Based on Mach, X11, and TCP/IP", Technical Report No. 90/566, CS Div., EECS Dept., UC Berkeley, March 1990.

Computer Music

Special-purpose language uses multiple concurrent processes to generate separate voices, dynamic, tempo, articulation change; hierarchical time- deformation systems; process scheduling for precise note timing and fast interactive response. Implemented systems in Forth, C++.

D.P. Anderson and J. Bilmes, "MOOD: A Concurrent C++-Based Music Language", 1992 International Computer Music Conference, San Jose CA.

D. P. Anderson and R. J. Kuivila, "FORMULA: a Programming Language for Expressive Computer Music ", IEEE Computer , June 1991.

D. P. Anderson and J. Bilmes, "Concurrent Real-Time Music in C++", USENIX C++ Workshop, Washington D.C., April 22-25, 1991, 147-161.

D. P. Anderson and R. J. Kuivila, "A System for Computer Music Performance", ACM Transactions on Computer Systems 8, 1 (February 1990), 56-82. Also Technical Report No. 89/527, CS Div., EECS Dept., UC Berkeley, August 1989. Available in the ACM Digital Library.

D. P. Anderson and R. J. Kuivila, "Continuous Abstractions for Discrete Event Languages", Computer Music Journal 13 , 3 (Fall 1989), 11-23.

D. P. Anderson and R. J. Kuivila, "Accurately Timed Generation of Discrete Musical Events", Computer Music Journal 10, 3 (Fall 1986), 48-56.

D. P. Anderson and R. J. Kuivila, "Programming Language Constructs for Parallel Musical Computations", 1989 International Computer Music Conference, Columbus, Ohio, Nov. 1989.

D. P. Anderson, "Synthesizer Management Based on Note Priorities", Proceedings of the 1987 International Computer Music Conference, Urbana-Champaign, 1987, 230-237.

R. J. Kuivila and D. P. Anderson, "Timing Accuracy and Response Time in Interactive Systems", Proceedings of the 1986 International Computer Music Conference, The Hague, 1986.

D. P. Anderson and R. J. Kuivila, "A Model of Real-Time Computation for Computer Music", Proceedings of the 1986 International Computer Music Conference, The Hague, 1986, 35-42.

D. P. Anderson, "A FORTH Computer Music Programming Environment Design", Proceedings of the 4th Annual Forth Applications Conference, Rochester NY, June 5-9, 1984.

Computer Graphics

Computational geometry algorithms to solve various problems in computer graphics. Voronoi diagram on sphere to find optimal viewing direction; quadtree for fast travelling-salesman approximation.

D. P. Anderson, "Efficient Algorithms for Automatic Viewer Orientation", Computers and Graphics 9, 4 (1985), 407-413.

D. P. Anderson, "Techniques for Reducing Pen Plotting Time", ACM Transactions on Graphics 2 (1983), 197- 212. Available in PDF format in the ACM Digital Library.

D. P. Anderson, "An Orientation Method for Central Projection Programs", Computers and Graphics 6 (1982), 35-38.

D. P. Anderson, "Hidden Line Elimination in Projected Grid Surfaces", ACM Transactions on Graphics 1 (1982), 274-288. Available in the ACM Digital Library.

Distributed Parallel Programming

Systems for fault-tolerant distributed parallel computation on networks of workstations.

S. E. Lucco and D. P. Anderson, "Tarmac: A Language System Substrate Based on Mobile Memory", Proceedings of the 10th International Conference on Distributed Computing Systems, Paris, May 1990. Also Technical Report No. 89/525, CS Div., EECS Dept., UC Berkeley, November 1989.

M. Sullivan and D. P. Anderson, "Marionette: a System for Parallel Distributed Programming using a Master/Slave Model", Proc. 9th International Conference on Distributed Systems, June 1989. Also Technical Report No. 88/460, CS Div., EECS Dept., UC Berkeley, 1988.

DASH Overviews

DASH: an operating system kernel and a communication protocol hierarchy with an ambitious set of research goals, most notably support for realtime workloads such as audio/video, global scalability, and efficient security (papers in these areas are listed below). DASH was written in C++ and ran on the Sun 3 and Sequent Symmetry.

D. P. Anderson and D. Ferrari, "The DASH Project", ACM SIGOPS Workshop on Distributed Systems, Amsterdam, September 1986.

D. P. Anderson and R. Wahbe, "The DASH Network Communication Architecture", Technical Report No. 88/462, CS Div., EECS Dept., UC Berkeley, November 1988.

D. P. Anderson and S. Tzou, "The DASH Local Kernel Structure", Technical Report No. 88/463, CS Div., EECS Dept., UC Berkeley, November 1988.

D. P. Anderson and D. Ferrari, "The DASH Project: An Overview", Technical Report No. 88/405, CS Div., EECS Dept., UC Berkeley, February 1988.

D. P. Anderson, D. Ferrari, P. V. Rangan and S. Tzou, "The DASH Project: Issues in the Design of Very Large Distributed Systems", Technical Report No. 87/338, CS Div., EECS Dept., UC Berkeley, January 1987.

Virtual Memory and Interprocess Communication

Local IPC mechanisms that use virtual memory remapping to avoid software copying. Also, mechanisms for dealing efficiently with TLB inconsistency in shared-memory multiprocessors.

S. Tzou and D. P. Anderson, "The Performance of Message-Passing Using Restricted Virtual Memory Remapping", Software – Practice & Experience 21, 3 (March 1991).

S. Tzou and D. P. Anderson, "A Performance Evaluation of the DASH Message-Passing System", Technical Report No. 88/452, CS Div., EECS Dept., UC Berkeley, November 1988.

D. P. Anderson, S. Tzou and G. S. Graham, "The DASH Virtual Memory System", Technical Report No. 88/461, CS Div., EECS Dept., UC Berkeley, November 1988.

S. Tzou, D. P. Anderson and G. S. Graham, "Efficient Local Data Movement in Shared-Memory Multiprocessor Systems", Technical Report No. 87/385, CS Div., EECS Dept., UC Berkeley, December 1987.

Secure Network Communication

Kernel-level mechanisms for security; caching of authentication; exploit security properties of underlying network.

D. P. Anderson, D. Ferrari, P. V. Rangan and B. Sartirana, "A Protocol for Secure Communication and its Performance", Proceedings of the 7th International Conference on Distributed Computing Systems, Berlin, September 1987.

D. P. Anderson and P. V. Rangan, "High-Performance Interface Architectures for Cryptographic Hardware", Eurocrypt '87, Amsterdam, April 1987.

D. P. Anderson, D. Ferrari, P. V. Rangan and B. Sartirana, "The Empirical Evaluation of a Security- Oriented Datagram Protocol", IFIP Performance '87, Brussels, December 1987. Also Technical Report No. 87/350, CS Div., EECS Dept., UC Berkeley, 1987.

D. P. Anderson and P. V. Rangan, "A Basis for Secure Communication in Large Distributed Systems", IEEE Symposium on Security and Privacy, April 1987.

D. P. Anderson, D. Ferrari and P. V. Rangan, "Subtransport Level: The Right Place for End-to- End Security Mechanisms", Technical Report No. 87/346, CS Div., EECS Dept., UC Berkeley, March 1987.

Communication Protocol Specification

Attribute grammars used to specify complex communication protocols (such as TCP and TP4). Grammars are augmented with mechanisms for parallelism and real-time constraints. Tools for automatically generating efficient implementations from specifications.

D. Hernek and D. P. Anderson, "Efficient Automated Protocol Implementation Using RTAG", Software - Practice & Experience 20, 9 (September 1990), 869- 885. Also Technical Report No. 89/526, CS Div., EECS Dept., UC Berkeley, August 1989.

D. P. Anderson, "Automated Protocol Implementation with RTAG", IEEE Transactions on Software Engineering 14, 3 (March 1988), 291-300.

D. P. Anderson and L. H. Landweber, "A Grammar-Based Methodology for Protocol Specification and Implementation", Proceedings of the Ninth Data Communications Symposium, September 1985, 63-70. Also University of Wisconsin CS Technical Report No. 605, 1985.

D. P. Anderson and L. H. Landweber, "Protocol Specification by Real-Time Attribute Grammars", Proceedings of the IFIPS Fourth International Workshop on Protocol Specification, Testing, and Verification, Skytop, Pennsylvania, June 11-14, 1984.

Miscellaneous

Workload model for a hypothetical global network file system.

S. Keshav and D. P. Anderson, "A Workload Model for Large Distributed File Systems.", 19th Annual Pittsburgh Conference on Modeling and Simulation, Pittsburgh PA, May 5-6, 1988.