Reading List for the MA Depth Qualifying Exam

Spring 2002

The MA Depth Qualifying Exam covers both analytic modeling techniques and state-of-the-art application of analytic modeling techniques to computer/communication system design issues. In depth understanding of the material below, as well as the ability to apply the techniques to new design questions, is tested on the exam.

Some of the papers below are available in the ACM Digital Library, which UW students can access from the UW library web page for electronic journals.

Modeling Techniques

• A. O. Allen, Probability, Statistics, and Queueing Theory with Computer Science Applications, Second Edition, Academic Press, 1990. (Chapters 1-6)

• Baskett, F., K. M. Chandy, R. R. Muntz, and F. G. Palacios, "Open, Closed, and Mixed Networks of Queues with Different Classes of Customers", Journal of the ACM, Vol. 22, No. 2, April 1975, pp. 248-260.

• Buzen, J. P., "Computational Algorighms for Closed Queueing Networks with Exponential Servers", Comm. of the ACM, Vol. 16, 1973, pp. 527-531.

• Eager, D. L., and J. N. Lipscomb, "The AMVA Priority Approximation", Performance Evaluation, No. 8, Vol. 3, June 1988, pp. 173-193.

• Eager, D. L., D. J. Sorin, and M. K. Vernon, "AMVA Techniques for High Service Time Variability", Proc. ACM SIGMETRICS 2000 Int'l. Conf. on Measurement and Modeling of Computer Systems, Santa Clara, CA, June 2000, pp. 217-228.

• Frank, M. I., A. Agarwal, and M. K. Vernon, "LoPC: Modeling Contention in Parallel Algorithms", Proc. PPoPP '97, Las Vegas, June 1997, pp. 276-287.

• Gordon, W. J., and G. F. Newell, "Closed Queueing Systems with Exponential Servers" Operations Research, Vol. 15, 1967, pp. 254-265.

• Heidelberger, P., and K.S. Trivedi "Queueing Network Models for Parallel Processing with Asynchronous Tasks", IEEE Transactions on Computers, Vol. C-31, No. 11, November 1982, pp. 1099

• Heidelberger, P. and K. S. Trivedi "Analytic Queueing Models for Programs with Internal Concurrency", IEEE Transactions on Computers, Vol. C-32, No. 1, January 1983, pp. 73-82

• Jackson, J. R., "Networks of Waiting Lines", Operations Research, Vol. 5, 1957, pp. 518-521.

• Kleinrock, L., Queueing Systems Volume I: Theory, Wiley Interscience, 1975. (Chapters 1-3, 5)

• Lazowska, E. D., J. Zahorjan, G. S. Graham, and K. C. Sevcik, Quantitative System Performance, Prentice Hall, 1984. (Chapters 1-11, 18-20)

• Sevcik, K. C. and I. Mitrani, "The Distribution of Queueing Network States at Input and Output Instants", J. of the ACM Vol. 28, No. 2, April 1981, pp. 358-371.

• Smith, J. E., "Characterizing Computer Performance with a Single Number", Comm. of the ACM, Vol. 31, No. 10, October 1988, pp. 1202-1207.

• J. Zahorjan, "Workload Representations in Queueing Models of Computer Systems", Proc. 1983 ACM Sigmetrics Conf. on Measurement and Modeling of Computer Systems, Minneapolis, 1983, pp. 70-81.

Applications

• Adve, V. S., and M. K. Vernon, "Performance Analysis of Multiprocessor Mesh Interconnection Networks with Wormhole Routing", IEEE Trans. on Parallel and Distributed Systems, March 1994.

• Berry, R., and K. M. Chandy, "Performance Models of Token Ring Local Area Networks", Proc. ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, August 1983, pp. 266-274.

• Chiang, M.-C. and G. Sohi, "Evaluating Design Choices for Shared Bus Multiprocessors", IEEE Transactions on Computers, Vol. 41, No. 3, March 1992, pp. 297-317.

• Greenberg, A. G., I. Mitrani, and L. Rudolph, "Analysis of Snooping Caches", Proc. Performance '87 12th Int'l. Symp. on Computer Performance, Dec. 1987, pp. 345-361.

• May, M., J.-C. Bolot, A. Jean-Marie and C. Diot, "Simple Performance Models of Differentiated Services Schemes for the Internet", Proc. IEEE INFOCOM '99 18th Ann. Joint Conf. of the IEEE Computer and Communications Societies, Vol. 3, New York, March 1999, pp. 1385-1394.

• Padhye, J., V. Firoiu, D. Towsley, and J. Kurose, "Modeling TCP Throughput: A Simple Model and its Empirical Validation", Proc. SIGCOMM '98, August 1998.

• Willick, D. L., and Derek L. Eager, "An Analytical Model of Multistage Interconnection Networks", Proc. 1990 ACM SIGMETRICS Conf. on Measurement & Modeling of Computer Systems, Boulder, Colorado, May 1990, pp. 192-199.

Computer Sciences Department
College of Letters and Science
University of Wisconsin - Madison

INFORMATION ~ PEOPLE ~ GRADS ~ UNDERGRADS ~ RESEARCH ~ RESOURCES

5355a Computer Sciences and Statistics ~ 1210 West Dayton Street, Madison, WI 53706
cs@cs.wisc.edu ~ voice: 608-262-1204 ~ fax: 608-262-9777