Please decide on your term project by Tuesday, November 13.  A final report/presentation on the project will be due the week of Dec 11 -- more details will come later. Throughout the remainder of this term, I can meet weekly with every project group/student weekly to discuss any project-related issues.

(1) Research problem related to your area of research

If you are aware of an algorithmic problem in your research area (systems, networking, databases, theory), then that may provide the best choice for your project.  You need to formulate the algorithmic problem and research various approaches to solve it.  The work can be primarily experimental, or primarily theoretical, or a good mix, but should involve some theoretical analysis or survey of theoretically-sound techniques.

(2) Analysis of a synchronization process

Synchronization problems arise often in distributed computing.  Such problems come up when we want a collection processors to all reach a particular state (or agree on a particular value) at the same time. There are tons of variants of synchronization problems depending on the underlying model of communication and the objective, among other factors.  A famous example of a synchronization problem is the firing squad problem.

This project concerns the analysis of the following synchronization problem, which can be very loosely thought of as a variant of the firing squad problem.  We have a set of n processors (think of small sensors) each having a certain orientation specified by a vector in 2D-space.  In each step, we take three processors uniformly at random and orient each of them according to the median vector.  The median of three vectors v_1, v_2, and v_3 is a vector in {v_1, v_2, v_3} whose angle with the other two vectors is at least 120 degrees.

It can be shown that eventually all the vectors will be identical. The goal of this project is to analyze the convergence time of the above process.  The work would involve literature survey, simulations, and some theoretical analysis.

(3) Fault-oblivious load balancing

In this project, we consider load balancing procedures that are oblivious to how faults are distributed among the servers.  Here is one possible problem formulation.

Consider a set A of clients, each periodically seeking some service from a set B of servers.  Let G = (A,B,E) be a bipartite graph with the set E of edges between A and B, whose edges specify the set of servers that are capable of serving each client.  For a client v in A, let S(v) denote the adjacent servers in G.  When a client v seeks some service, it needs to connect with one of the servers in S(v).  In a large-scale distributed system with unpredictable load, some of the servers may be faulty or simply unreachable at any given time. Consider the following simple process for the client v to select a server: v walks through a permutation p(v) of the servers in S(v), selecting the first server that is reachable.  Given a permutation function p and a set T of live servers, we define the load load(p,T) to be the maximum, over all servers j in T, of

|{v : j is the first server from T in the permutation p(v)}|

We would like to determine a permutation function p that minimizes the maximum, over all server subsets T, of the ratio load(p,T)/opt_T, where opt_T is the load of the optimal assignment of clients to servers in T.

The work involved in this project would be development of models and theoretical analysis.

(4) Confluent flows on networks of arbitrary capacities

In past work, we have studied a special class of network flows, called confluent flows in which flows toward a given destination form a tree. A major motivation for studying confluent flows is that Internet routing is primarily confluent.  We have obtained some results for both single-commodity and multi-commodity confluent flows, both under some restrictive conditions.

This project concerns more general problems in this domain -- in particular, single-commodity confluent flows in which edge/node capacities are arbitrary.

The work involved in this project would be primarily theoretical, focusing on certain interesting special cases that have not been handled before.

(5) The complexity of average-stretch scheduling

Consider a scheduling problem in which a collection of jobs arrive over time and need to be assigned on a single processor.  Further suppose, the arrival time and the processing time of the jobs is known in advance.  We can define the stretch of a job in a schedule to be the ratio of the response time of the job (completion time minus arrival time) to the processing time.  

This project studies the complexity of average-stretch scheduling.  It is not known to be NP-hard; yet only constant-factor approximations exist.  It is also closely related to a wide open problem in scheduling, the weighted flow time problem.

The work involved in this project would be primarily theoretical, consisting of a thorough literature survey and attempting to resolve special cases.

(6) Experimental evaluation of multicommodity flow algorithms

This project will experimentally evaluate some multicommodity flow algorithms on large network instances.  Candidate algorithms are the Garg-Konemann algorithm we studied in class, improvements due to Fleischer and Karakotsas, and a recent distributed algorithm due to Awerbuch and Khandekar.  The latter algorithm could also be tested in an distributed environment.

The work involved in this project would be primarily experimental, with a focus on a specific application, e.g., network routing, transportation.