Systems Area Reading List
Before taking the Systems Area Exam, students are expected to have
mastered all materials used in CS 6210. Below, we list only additional papers
that capture (1) older papers not covered anymore in 6210 but still required
for this exam and (2) additional papers parts of the core of the systems
area.
------------------------------------------------------------------------
Additional Papers at 6210 (and 4210) Level
Shared Memory Systems
Anderson, T.E., ``The Performance Implications of Spin-Waiting Alternatives
for Shared-Memory Multiprocessors", IEEE Transactions on Parallel and Distributed
Systems, 1, 1, pgs. 6-16, January 1990.
Threads and their weights: Engler, D.R., Andrews, G.R., Lowenthal, D.K.,
``Filaments: Efficient Support for Fine-Grain Parallelism", The Univ. of
Arizona, Department of Computer Science, TR 93-13a, February 1994.
Threads and communications: Bershad, B.N. Anderson, A.E., Lazowska, E.D.,
and Levy, H.M., ``User Level Interprocess Communication for Shared Memory
Multiprocessor", ACM Transactions on Computer Systems, 9, 2, pgs. 175-198,
May 1991.
Draves, R.P., Bershad, B.N., Rashid, R.F. and Dean, R.W., ``Using Continuations
to Implement Thread Management and Communication in Operating Systems", Proceedings
of the Thirteenth ACM Symposium on Operating System Principles, pgs. 122-136,
December 1991.
OS Survey: Mukherjee, B., and Schwan, K., "Survey of Multiprocessor Operating
Systems Kernels", Technical Report GIT-CC-92/05. College of Computing, Georgia
Institute of Technology, November 1993. (available as schwan/6420/mukherjee.ps).
From Parallel to Distributed Systems: Communication Mechanisms
Birrell and Nelson, "Implementing Remote Procedure Calls", ACM Transactions
on Computer Systems, 2, 1, pgs. 39-59, February 1984
Birrell, A.D., "Secure Communication Using Remote Procedure Calls", ACM Transactions
on Computer Systems, 3,1, pgs. 1-14, February 1985.
Clark, D.D., "The Structuring of Systems Using Upcalls", Proceedings of Tenth
ACM Symposium on Operating Systems Principles, pgs. 171-180, Dec. 1985.
V. Bala, et.al, "CCL: A portable and tunable Collective Communication Library
for scalable parallel computers", IEEE Transactions on Parallel and Distributed
Systems, Vol 6, No 2, Feb 1995.
Distributed System Services: File Systems and Virtual Memory
Nelson, M.N., Welch, B.B., Ousterhout, J.K., ``Caching in the Sprite Network
File System", ACM Transactions on Computer Systems, 6, 1, pgs. 134-154, February
1988.
D. James Gemmell, Harrick M. Vin, Dilip D. Kandlur, P. Venkat Rangan, and
Lawrence A. Rowe, ``Multimedia Storage Servers: A Tutorial'', IEEE Computer,
May 1995.
Distributed Systems: Failures, Consistency and Recovery
Walker et al., "The LOCUS Distributed Operating System," Proceedings of the
Ninth ACM Symposium on Operating Systems Principles, pgs 49-70, December
1983.
Object-based Systems and Object Technologies
Linden, T.A., ``Operating System Structures to Support Security and Reliable
Software", Computer Surveys, 8, 4, pgs. 409-445, 1976. Also see chapter on
protection in Peterson/Galvin, ``Operating System Concepts".
Saltzer, J.H., ``Protection and the Control of Information Sharing in Multics
'', Communications of the ACM, 17, 7, 1974.
Cox, G., et al., "Interprocess Communication and Processor Dispatching on
the Intel 432", Proceedings of the 8th Symposium on Operating System Principles,
Asilomar, pgs. 44-53, Dec. 1981.
Birrell, A., Nelson, G., Owicki, S., and Wobber, E., ``Network Objects'',
Digital, SRC Research Report No. 115, Dec. 1995.
This ends the material at 6210 level, to be mastered in addition to the materials
covered in the current version of CS 6210.
------------------------------------------------------------------------
Below is additional material for the Area Exam. Its purpose is to deepen
OS knowledge past 6210 and explore additional domains.
Distributed Systems Principles
M. Chandy and Leslie Lamport, "Distributed Snapshots: Determining Global
States of Distributed Systems", ACM Transactions on Computer Systems, Feb.
1985.
Reinhard Schwarz and Friedmann Mattern, "Detecting causal relationships in
distributed computations: in search of the holy grail", Distributed Computing,
1994, 7, 3.
Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson, "Impossibility
of Distributed Consensus with One Faulty Process", Journal of the ACM, 32,
2, April 1985.
Communication and Sharing in Distributed Systems
Kenneth Birman, Andre' Schiper, and Pat Stephenson, "Lightweight Causal and
Atomic Group Multicast", ACM Transactions on Computer Systems, Aug. 1991,
9, 3.
Kai Li and Paul Hudak, "Memory coherence in shared virtual memory systems",
ACM TOCS, 7(4):321--359, November 1989.
P. Keleher, A. Cox, and W. Zwaenepoel. Lazy Release Consistency for Software
Distributed Shared Memory, Proc. of the Twentieth Symposium on Computer Architecture,
1993.
Mustaque Ahamad, Gil Neiger, Prince Kohli, James Burns, and Phil Hutto, "Causal
Memory: Definitions, Implementation and Programming", Distributed Computing,
9(1):37--49, Aug 1995.
Karsten Schwan and Win Bo, "Topologies''- Distributed Objects on Multicomputers",
ACM Transactions on Computer Systems, 8, 2, May 1990 (partial reading: skip
performance results).
J.J. Kistler and M. Satyanarayanan, "Disconnected Operation in the CODA File
System", ACM Transactions on Computer Systems, Feb. 1992.
Note: in the future, we will add an Overlay Network paper here.
Communications
C. Maeda and B. Bershad, "Protocol Service Decomposition for High-Performance
Networking", Proceedings of the 14th ACm Symposium on Operating System Principles,
Dec. 1993.
Bhatti, Hiltunen, Schlichting, Chiu, "Coyote: A System for Constructing Fine-Grain
Configurable Communication Services", ACm Transactions on Computer
Systems, Nov. 1998.
Note: there is interesting additional material for those students who are
interested in networking dimensions, including how to deal with large- or
high peformance data transfers (TCP autotuning), wireless communications,
etc.
Other Systems and Topics
Robbert van Renesse, Takako Hickey, Kenneth Birman, "Design and Performance
of Horus: A Lightweight Group Communication", Cornell University, 94-1442,
1994.
David Kotz, "Disk-directed I/O for MIMD Multiprocessors", Symposium on Operating
Systems Design and Implementation (OSDI '94), Nov. 1994, Usenix, ACM SIGOPS
Notices, also in ~schwan/6420/kotz.ps.
Distributed Simulation
David R. Jefferson, "Virtual Time", ACM Transactions on Programming Languages
and Systems", 7, 3, July 1985.
R. M. Fujimoto, "Parallel Discrete Event Simulation", Communications of the
ACM, 33, 10, Oct. 1990.
Isolation, Safety, and Virtualization
Note: beyond the basic security readings in 6210 and the few OS-centric readings
below, all additional topics on security are required only for students who
are also taking the Security Area Exam.
Safety: R. Wahbe, S. Lucco, T.E. Anderson, S.L. Graham, "Efficient, Software-based
Fault Isolation", Proceedings of the 14th ACM Symposium on Operating System
Principles, Dec. 1993.
Isolation: Whitaker, Shaw, Gribble, "Scale and Performance in the Denali
Isolation Kernel", ACM OSDI 2002.
Virtualization: Chiueh, Venkitachalam, Pradhan, "Integrating Segmentation
and Paging Protection for Safe, Efficient and Transparent Software Extensions",
ACM Symposium on Operating System Principles, Dec. 1999.
Virtualization: Waldspurger, "Memory and Resource Management in VMWare ESX
Server", ACM OSDI 2002.
Real-Time, Pervasive, Configurable Systems
Scheduling:
Dertouzos, Michael L. and Mok, Aloysius Ka-Lau, "Multiprocessor On-Line Scheduling
of Hard-Real-Time Tasks", IEEE Transactions On Software Engineering, Dec
1989.
Lehoczky, L. Sha, Y. Ding, " The Rate Monotonic Scheduling Algorithm - Exact
Characterization and Average Case Behavior", Proceedings of the Real-Time
Systems Symposium, 1989.
Ramamritham, Krithi; Stankovic, John; Zhao, Wei, "Distributed Scheduling
of Tasks with Deadlines and Resource Requirements", IEEE Transactions on
Computers, vol.38, no.8, Aug.1989.
Karsten Schwan and Hongyi Zhou, "Dynamic Scheduling of Hard Real-Time Tasks
and Real-Time Threads, IEEE Transactions on Software Engineering, August
1992.
Mercer, Clifford W.; Savage, Stefan; and Tokuda, Hideyuki, "Processor Capacity
Reservation for Multimedia Operating Systems", Tech. Report CMU-CS-93-157,
Carnegie-Mellon Univ., May 1993, also in IEEE International Conference on
Multimedia Computing and Systems, May 1994.
Carl A. Waldspurger and William E. Weihl, "Lottery Scheduling: Flexible Proportional-Share
Resource Management", First Symposium on Operating Systems Design and Implementation
(OSDI '94), Monterey, CA, November 1994.
Michael B. Jones, Daniela Rosu, and Marcel-Catalin Rosu, "CPU Reservations:
Efficient Predictable Scheduling of Independent Activities", Sixteenth ACM
Symposium on Operating System Principles, ACM SIGPOS Notices, December 1997.
Lu, C.; Stankovic, J.A.; Tao, G.; Son, S.H., " Design and evaluation of a
feedback control EDF scheduling algorithm", Real-Time Systems Symposium,
1999. Proceedings. The 20th IEEE , 1999.
Real-time, Quality of Service, Pervasive Systems:
Stankovic, Ramamritham, "The Spring Kernel: A New Paradigm for Real-Time
Systems", IEEE Software, May 1991.
Tarek F. Abdelzaher and Kang G. Shin, " End-host Architecture for QoS-Adaptive
Communication", IEEE Real-Time Technology and Applications Symposium, Denver,
Colorado, June 1998.
Baochun Li and Klara Nahrstedt, " A Control-based Middleware Framework for
Quality of Service Adaptations", IEEE Journal of Selected Areas in Communication,
Special Issue on Service Enabling Platforms, 1999, Vol. 17, No. 9, September1999.
Pillai, Shin, "Dynamic Voltage Scaling for Low-Power Embedded Operating Systems",
ACM SOSP 2001.
John Heidemann, Fabio Silva, Chalermek Intanagonwiwat, Ramesh Govindan (USC/ISI),
Deborah Estrin, Deepak Ganesan (UCLA). Building Efficient Wireless Sensor
Networks with Low-Level Naming. Proceedings of SOSP 2001.
Configurable Systems:
Thomas E. Bihari and Karsten Schwan, "Dynamic Adaptation of Real-Time Software",
ACM Transactions on Computer Systems", May 1991.
Ahmed Gheith, Karsten Schwan, "CHAOSarc: Real-Time Objects and Atomicity
for Multiprocessors", ACM Transactions on Computer Systems, 11, 1, April
1993 (skip performance results, focus on software architecture).
Roy Campbell, Nayeem Islam, Peter Madany, and David Raila, "Designing and
Implementing Choices:an Object-Oriented System in C++", Communications of
the ACM, September 1993.
T. Audrey, A. Black, C. Consel, C. Cowan, J. Inouye, L. Kethana, J. Walpole,
and K. Zhang, "Optimistic Incremental Specialization: Streamlining a Commercial
Operating Systems", Fifteenth ACM Symposium on Operating System Principles,
ACM SIGOPS Notices, December 1995.
Dylan McNamee, Jonathan Walpole, Calton Pu, Crispin Cowan, Charles Krasic,
Ashvin Goel, Perry Wagle, Charles Consel, Gilles Muller, Renauld Marlet,
"Specialization Tools and Techniques for Systematic Optimization of System
Software", ACM Transactions on Computer Systems, May 2001.
Ashvin Goel, Luca Abeni, Charles Krasic, Jim Snow, and Jonathan Walpole.
Supporting time-sensitive applications on general-purpose operating systems.
In Proceedings of the Fifth USENIX Symposium on Operating Systems Design
and Implementation, Dec 2002.
Craig A. N. Soules, Jonathan Appavoo, Kevin Hui, Robert W. Wisniewski, Dilma
Da Silva, Gregory R. Ganger, Orran Krieger, Michael Stumm, Marc Auslander,
Michal Ostrowski, Bryan Rosenburg, Jimi Xenidis: "System Support for OnlineReconfiguration",
Proceedings of Usenix 2003, pg 141-154.
Middleware
Note: for brevity, we are not requiring knowledge about the various grid
computing infrastructures and efforts for this exam. Students are referred
to our course on High Performance Computing for these materials. Below, we
list only a few, current and ongoing efforts (and some basic materials about
them) required for this exam.
Lewis, Grimshaw, "The Core Legion Object Model", HPDC, Aug. 1996.
Angelo Corsaro and Douglas C. Schmidt. " Evaluating Real-Time Java Features
and Performance for Real-time Embedded Systems", Proceedings of the 8th IEEE
Real-Time Technology and Applications Symposium, San Jose, CA, September
2002.
Richard E. Schantz, Joseph P. Loyall, Douglas C. Schmidt, Craig Rodrigues,
Yamuna Krishnamurthy, and Irfan Pyarali. "Flexible and Adaptive QoS Control
for Distributed Real-time and Embedded Middleware", Middleware 2003, 4th
IFIP/ACM/USENIX International Conference on Distributed Systems Platforms,
June 16-20, 2003, Rio de Janeiro, Brazil.
Web Services
Note: there is substantial material on web servers, proxy caching, server
performance, etc. For brevity, such materials are not required for this exam.
They are of interest to our graduate students, however, and many useful references
are listed in conjunction with our course on Internet Computing (Prof. Liu).
The list below is designed to introduce students to newer computational/communication
models used for web services.
Gryphon: Banavar, Chandra, Mukherjee, Nagarajarao, Strom, Sturman, "An Efficient
Multicast Protocol for Content-based Publish-Subscribe Systems", International
Conference on Distributed Computing Systems, ACM/IEEE,1999.
A. Carzaniga, David Rosenblum, Alexander Wolf, "Design and Evaluation of
a Wide-Area Event Notification Service", ACM Transactions on Computer Systems,
Aug. 2001.
Peer-to-Peer: Dabek, Kaashoek, Karger, Morris, Stoica, "Wide-area Cooperative
Storage with CFS", ACM SOSP 2001.
Peer-to-Peer: Adya, Bolosky, Castro, Cermak, Chaiken, Douceur, Howell, Lorch,
Theimer, Wattenhofer, "FARSITE: Federated, Available, and Reliable Storage
for an Incompletely Trusted Environment", ACM OSDI 2002.
OS Measurement
Allen D. Malony and Daniel A. Reed, Harry A. G. Wijshoff, "Performance Measurement
Intrusion and Perturbation Analysis", IEEE Transactions on Parallel and Distributed
Systems, July 1992, 3, 4.
Weiming Gu, Greg Eisenhauer, Eileen Kraemer, Karsten Schwan, John Stasko,
and Jeffrey Vetter, "Falcon: On-line Monitoring and Steering of Large-Scale
Parallel Programs", Concurrency: Practice and Experience, 1998.
Ariel Tamches and Barton P. Miller, "Fine-Grained Dynamic Instrumentation
of Commodity Operating System Kernels", Third Symposium on Operating Systems
Design and Implementation (OSDI), New Orleans, February 1999.
Eric Shaffer, Shannon Whitmore, Benjamin Schaeffer, and Daniel A. Reed,
"Virtue: Immersive Performance Visualization of Parallel and Distributed
Applications: Immersive Performance Visualization of Parallel and Distributed
Applications," IEEE Computer, December 1999, pp. 44-51.