From 1990 to 1994 I investigated stochastic properties of task graphs at the University of the Witwatersrand, initially as a final-year undergraduate, and then as an MSc student in Computer Science. A technical report is available summarising some of the initial results of this work.
The most interesting result of this work is: with work-preserving scheduling and infinite processors, if a subgraph relation between task graphs holds, then their execution time distributions are pointwise comparable. It then trivially follows that the expected mean execution times are also comparable. This gives simpler derivations for several known results.
During this period, I also managed all computer systems in the department and handled the transition to a networked environment connected to the Internet. Ultimately the temptation to join the Internet boom in 1994 proved too strong, and I joined an ISP startup, The Internet Solution (now called Internet Solutions, a division of Dimension Data PLC). As a director of the company, I established the services division to contain customer support costs, and helped to set up and grow the security and training divisions into profitable businesses. Highlights were training more than 200 Internet administrators, drafting the defense in a complex legal dispute with the monopoly telco, and establishing a culture of automating systems administration through scripting. After four years, having helped the company to grow to over 500 people, I returned to finish my degree in 1999.
Changing focus from a stochastic model to a deterministic model emphasizing the poset structure of task graphs, I was awarded an MSc (with distinction) in April 2001 for a dissertation on task graph performance bounds (PDF format, 141 pages). An abstract is available in text format.
The dissertation considers the relationship between the structure of a task graph (activity-on-node network), and its execution time (makespan). It turns out that two task graphs are makespan-comparable for all workloads precisely when one is a reorder-extension of the other. (This occurs precisely when the underlying comparability graphs are comparable by the subgraph relation.)
A best series-parallelisation is formed by adding precedence constraints to a task graph, so that the resulting task graph is series-parallel and has minimal makespan among all such series-parallelisations, for a given set of task durations (workload). A bounded slowdown conjecture is posed: is it always possible to add precedence constraints to a task graph so that the new graph is series-parallel and has makespan at most 4/3 times that of the original? This bound is shown to be the best possible, and the conjecture is shown to be true for 4-node graphs. Using modular decompositions, a theory is also developed which allows the 5-node case to be reduced to considering only three cases.Since December 2000, I have been involved in establishing another business, Borntosend, a South African reseller of courier and freight services. I am also on the technical advisory board of Men & Mice, an Icelandic software company focusing on DNS management tools. During 2000, 2001 and 2002 I lectured and examined the fourth-year computer science course in Computer Networking at the University of the Witwatersrand.
In 2003, I confirmed the 4/3 bounded slowdown conjecture for the cases with 5 and 6 nodes also, by applying the constraint solver clp(q,r) to the systems of inequalities obtained by enumerating all possible cases.
However, the number of candidate posets is very large even for 6 nodes, so I am working on techniques to reduce the size of the candidate set using additional domination properties. The software to exhaustively check all possible cases also needs further work, since its complexity makes it difficult to demonstrate its correctness.
The 7-node case should be especially interesting, since that is the minimum number of nodes required for an N-poset composed with another N-poset, for which my current modular decomposition results can only be used to prove a 16/9 bound.
The complexity of producing 4/3 series-parallelisations appears to be NP-hard. This seems quite difficult to prove. The form of the problem is quite different to most existing NP-complete problems, so modelling the reduction along the lines of existing reductions has not proved useful.
I am writing several papers outlining the main results of the work to date. A BibTeX file of bibliography entries for my research is available.
Currently I am working towards a research qualification at the University of Oxford, in the Constraints Research Group, specializing in the mathematics of constraint satisfaction. A good representative paper in this area is The complexity of maximal constraint languages by Andrei Bulatov, Andrei Krokhin and Peter Jeavons, or see the earlier research report RR-01-03 for the freely available version of this document.