http:^^www.cs.wisc.edu^~solomon^projects.html

This data set contains WWW-pages collected from computer science departments of various universities

What causes spikes in usage (and corresponding drops in response)?
<p>
For example, in a recent
USENIX conference Matt Blaze describes a publicly
available program for eavesdropping on NFS traffic on a local area Ethernet
and gathering statistics.
Install this program, use it to gather some statistics, and compare them
with similar data from the literature.
See also the suggestions regarding distributed file systems above.

<a name="garbage">
<h2>Distributed or Persistent Garbage:</h2>
</a>
The problem of garbage collection (finding and reclaiming space allocated
to inaccessible objects) has been well studied for almost 30 years.
Algorithms can be roughly classified as explicit deletion
(``It's my data and I'll throw it away when I want to!''),
reference counting
(``Will the last one out please turn off the lights?''),
mark-and-sweep
(``Unclaimed goods will be recycled''),
and generational
(``When the ashtray is full it's time to buy a new car'').
Recently, there's been a resurgence of research in garbage collection spurred
by two developments:
distributed systems
(``I can't throw this away because somebody in France may still want it'')
and persistent programming languages (the Pampers problem:
The only thing worse than garbage is persistent garbage).
Well known garbage collection algorithms that work fine for physical or
virtual memory are terrible when pointers can cross continents or disk
cylinders.
Interesting algorithms for a disk-based or distributed environment have
been proposed (see me for references).
Study some of these algorithms, and either suggest improvements or implement
them and study their performance.

<a name="consumersreports">
<h2>Consumer Reports:</h2>
</a>
Many people are generating software and making it freely available on
the network for
``anonymous ftp.''
Often, there are several packages available for the same or similar purposes.
Much of this software is worth exactly what it costs, but some of it is
as good as, if not better than, expensive
``commercial''
products.
Select two or more related programs and do a careful comparative critical
review.
Depending on the nature of programs, the review might be a benchmarking
study of relative performance, an analysis of functionality or ease-of-use,
or some combination of these factors.
<p>
One area of particular interest is file accessing and indexing packages
(if this were cs764, I would call them low-level database facilities).
Examples are the WISS and Exodus storage managers, both written here,
and the dbm and libdb packages from Berkeley (the latter is in the
yet-to-be-released 4.4BSD version of Unix, but we have a early version of
this code).
<p>
A related suggestion is to compare implementations of Unix and alternative
ways of achieving the same function in different ways.
For example, consider the question,
``What's the best way to get data from one process to another?''
Under various flavors of Unix you can use TCP or UDP, Unix-domain sockets,
pipes, fifo's, shared memory, files, or at least three different flavors
of remote procedure call.
The answer depends on the versions of Unix involved, and various
characteristics of the communication desired (such as the amount of data
to be transferred, the sizes of messages, whether replies are required,
the degree of reliability needed, etc.)
I've written a rough program that tests many of these techniques.
I would like someone to polish the program a bit and use it to do an evaluation
of many of the IPC mechanisms available.

<a name="condor">
<h2>Condor:</h2>
</a>
Condor is a locally-written utility that makes unused cpu power on
idle workstations available for productive use.
A daemon process on each workstation monitors activity and reports to
a central resource manager.
A client who wishes to run a long cpu-bound program contacts the resource
manager to obtain the name of an idle workstation.
It then contacts the selected server workstation and sends the job to be
executed.
Jobs to be run under Condor are linked with a version of the
C library that handles system calls specially:
File I/O calls are turned into requests sent back to a
<em>shadow</em>
process running on the submitting host.
If the server workstation should become non-idle before the job finishes,
the job is checkpointed and restarted on another workstation in the pool.
One user of Condor had a program successfully complete after consuming
over 300 cpu
<em>days</em>
during a period that spanned the department's move to a new building!
<p>
Several enhancements to Condor have been considered.
<ol>
<li>
<em>Security:</em>
Server security seems adequate.
Application processes runs with a non-privileged guest user id under control
of a trusted
``starter''
that can kill them at any time.
Providing security for condor users seems much more tricky.
Here the problem is that the shadow, which by design runs under the UID of
the job's owner and has all of that person's privileges, is vulnerable to
``spoofing''
by software on the server machine.
If we assume that the server workstation is owned by a hostile
user who has super-user capabilities, the problem becomes
quite difficult.
Design and implement a mutual-authentication protocol, perhaps using
the Kerberos package.
<li>
<em>Multiprocess Jobs:</em>
Currently, Condor only supports jobs consisting of a single UNIX process;
Condor does not support the UNIX
<em>fork</em>
call.
Design extensions to Condor that support a collection of processes connected
by pipes.
Your design must deal with problems such as co-scheduling (making sure
all processes are running at the same time) and maintaining connections
as processes are checkpointed and moved.
<li>
<em>Condor Lite:</em>
Condor is designed for single processes that consume many hours of cpu time.
Fixed overhead makes Condor impractical
for short jobs (such as a C compilation).
Consider how to use some of the Condor machinery to produce a
<em>network make</em>
facility.
</ol>
<p>
Other enhancements suggested by Mike Litzkow, principal implementor and
maintainer of Condor, include:
<ul>
<li>
Execution of condor jobs across wide area networks.
<li>
Support for a parallel programming model other than pipe/fork/exec
(e.g., Linda).
<li>
More sophisticated matching of jobs to available resources.
<li>
Checkpointing mechanisms which require less data movement.
<li>
Implementation of applications which are well suited to Condor's
capabilities and can really show off its power.
Applications in such
``trendy''
areas as code decryption or genetic engineering are obvious choices.
</ul>
<p>
The current implementation of Condor is available by anonymous ftp.

<a name="efsd">
<h2>Specialized NFS Servers:</h2>
</a>
<p>
The Unix File System interface provides a convenient abstraction for
a variety of data beyond ordinary files.
For example,
``classic''
Unix makes I/O devices and communication channels (pipes) look like files.
Some flavors of Unix support other kinds of objects that look like files,
including network connections, 
``named pipes''
and shared-memory regions.
The Network File System
(NFS) provides a convenient path for adding new kinds of
``file-like''
objects without modifying the operating system kernel.
An NFS server running as user-level process can be
``mounted''
in the Unix name space.
Any requests to open, read, or write files in this space are forwarded
to the server.
This trick is used in the CAPITL program-development environment and
the SHORE object-oriented database system to allow access to database
objects from
``legacy''
applications such as compilers, editors,
<em>grep </em>,
etc. without the need to modify, or even re-link them.
I have written a package of C++ classes that encapsulate all the messy
details of the NFS protocol to create a
``do it yourself''
NFS server kit.
All you have to do is implement the necessary data structures to
simulate Unix file behavior.
<p>
Use this kit to provide a Unix-compatible veneer over some other service.
A representative example is FTP.
Write a server that allows you to navigate the space of files accessible
via anonymous FTP as if they were part of the local file system.

<a name="shore">
<h2>Shore:</h2>
</a>
<p>
Shore is an experimental object-oriented database being developed in our
department.
It combines many of the features of traditional databases (concurrency
control and recovery and high-speed bulk operations), object-oriented databases
(fine-grained strongly typed objects with identity), and file systems
(a hierarchical name space with secure protection of objects and Unix
compatibility).
Write a persistent application using the facilities of Shore and critically
evaluate how well it served your needs, or work to extend or improve
Shore in some way (see me for ideas).

<a name="miscresearch">
<h2>UW--Madison Research Projects:</h2>
</a>
<p>
<!WA31><!WA31><!WA31><!WA31><!WA31><!WA31><!WA31><!WA31><!WA31><!WA31><!WA31><!WA31><a href="http://www.cs.wisc.edu/rsch-info/"> Detailed descriptions </a>
of several of the research projects mentioned above
(and more) are available via the
<!WA32><!WA32><!WA32><!WA32><!WA32><!WA32><!WA32><!WA32><!WA32><!WA32><!WA32><!WA32><a href="http://www.cs.wisc.edu/"> CS Department Home Page </a>.
Most of the projects listed there would welcome participation by interested
students.
<a name="tempest">
<h2>Tempest</h2>
</a>
From: [e-mail] (Mark D. Hill)
<p>
Date: Mon, 27 Feb 1995 14:36:04 -0600 (CST)
<p>
Here is a 736 project that I think would be interesting:
<p>
Background: Future parallel computers must execute efficiently both
hand-coded applications and also programs written in high-level
programming languages.  Today's machines limit programs to a single
communication paradigm--message-passing or shared-memory--which results
in uneven performance.  To address this problem, we have developed the
Tempest interface, which supports shared-memory, message-passing, and
hybrid applications.  Tempest enhances portability of parallel programs
by allowing low-cost networks of workstations to provide the same
abstractions (e.g., shared memory) as high-performance parallel machines.
<p>
The Tempest interface consists of low-level communication and
memory-system mechanisms.  Policies, such as shared memory, are
implemented in user-level software, which allows programmers and compilers
to customize policies to an application's semantics and sharing patterns.
Experiments show that custom cache coherency policies can produce upto
an order-of-magnitude performance improvement.
<p>
The <!WA33><!WA33><!WA33><!WA33><!WA33><!WA33><!WA33><!WA33><!WA33><!WA33><!WA33><!WA33><a href="http://www.cs.wisc.edu/~wwt">Wisconsin Wind Tunnel Project</a> has
developed implementations of Tempest for the CM-5 and a cluster of
workstations (COW) (Sun SS-20 running Solaris 2.4).  To complete our
portability story and facilitate program development, we would like to see
Tempest run a single workstation (either uniprocessor or multiprocessor).
<p>
The project: Implement Tempest so that all processes run on on a single
two-processor node of COW.  The key challenge is implementing the
messaging so that functionally it looks exactly the same as the version
that sends messages between nodes.  
<p>
Interested groups should read
<!WA34><!WA34><!WA34><!WA34><!WA34><!WA34><!WA34><!WA34><!WA34><!WA34><!WA34><!WA34><a href="ftp://ftp.cs.wisc.edu/wwt/compcon95_tempest.ps.Z">
the paper
</a>
before talking with him further.

<hr>

<address>
<i>
<!WA35><!WA35><!WA35><!WA35><!WA35><!WA35><!WA35><!WA35><!WA35><!WA35><!WA35><!WA35><a HREF="http://www.cs.wisc.edu/~solomon/solomon.html">
[e-mail]
</a>
<br>
Fri Sep 29 16:30:41 CDT 1995
</i>
</address>

</body>

</html>