The regionals of the ACM ICPC takes place every year around October. Today was that day for 2010. This posts just documents my experiences around the preperation leading up to the event, what went wrong, what went right, and some notes regarding AbacusCM.
I have to give my commendations to Linda Marshall first off. In spite of many things going severely wrong (more on this later) I think she handled the whole thing excellently. I don’t think that any additional planning would have made any difference to the things that went wrong.
So what did go wrong? Two things primarily. Firstly Nigeria didn’t come to the party, wiping their asses with Linda and myself when requesting access to server resources. There is unfortunately no more polite way to put this. Various requests for working logins and access to a MySQL database was flatly ignored, we received a single response with non-working ssh details. This had a cascading effect which I will detail later. The second problem was specific to the University of Pretoria. In particular the technical team there failed. Entirely. I won’t detail the various ways in which they failed, but I blame this team of people entirely for a late start of an hour and a half. I used to head off this for most of my three years working on this team between 2002 and 2005.
Nigeria ended up emailing their solutions to Linda, who ended up logging into and out of abacus over an X11 forwarded over ssh session running from my netbook with the appropriate users. I personally would have told them to
With the unpleasantness out of the way. A six site contest is no mean feat. The logistics is crazy. Trying to organize people is not easy. Other than UP the South African sites was (at least from my point of view) ran smoothly. So thanks to the folks at the Rhodes University, the University of Cape Town and the University of Kwazulu Natal. The two “african” sites was a 50/50 business. As mentioned above, Nigeria was a mess, Benin however went reasonably well. I suspect they might have been using an older version of the client which hammered the server harder than required, but the same can be said for Rhodes (except they didn’t mention anything). Thanks to Bruce Merry for helping to speed things up over the last few years, and especially changes made during their IT Challenge earlier in the year. Three of the five servers survived quite comfortably. Unfortunately the updates on the server side requires some assistance from the clients.
A few things became apparent to me. We’re not the only people who previously had problems with PC Squared. We overlooked something called Moonash (Thanks Alex), but apparently even that is not the way to go. I won’t claim Abacus is perfect (I’ll discuss this lower down), but from the feedback I’ve received I am confident that it shows a lot of promise.
Regarding the problem set (Available from http://acm.cs.up.ac.za/) was a good mix between really easy, medium and some hard problems. Having participated myself a few years back it almost feels as if the problems got way, way easier (but that could just be me gaining significantly more experience over the last few years). To give an idea, during the contest I managed to hack together solutions for three of the seven problems (probably spent about an hour on this). I reckon I would quite comfortably have been able to hack together another two solutions, and even perhaps have solved the ultra hard problem.
The stats however looks horrid. Quite a number of teams didn’t solve any problems in spite of numerous submissions. Problems for these teams ranged from minor errors, outright not reading the spec (trying to open/close files instead of reading input from stdin and outputting to stdout), stupid errors (like placing arbitrary limits on how big they think the input data sets will be instead of dynamically allocating) and things like trying to pop up JPanel (Java mortality rate was high, again, this year) input boxes, we even tracked some solutions that worked on a dirty stack but not a clean one (uninitialized boolean, int main() { bool fneh; while (fneh) { … }} type thing, that worked when run by hand, but not inside the clinical testing environment). There was obviously a lot of calculation errors too (heck, on all three problems I submitted I had one incorrect submission first – note that I didn’t bother to test my solutions properly before submitting, preferring to waste the judges time rather than my own). Two teams managed to solve all seven problems. The general guidelines are (as far as I understand):
- Every team should solve one problem.
- No team should solve all problems.
- Every problem should be solved by at least one team.
- No problem should be solved by all teams.
So stats wise the contest only complied with one of these guidelines. Not good.
Regarding abacus, I realized a few things. So starting with the interface things, things which (given time 5 years back probably would have been done differently).
- The interface really should have a “home” page for contestants showing all problems, and current state for the problem (solved, not attempted, submitted with wrong answer), number of incorrect submissions type of thing. I’m not an interface designer, so sue me. This is the first year I actually did some problem attempts myself, thus the first time I really used this side of the interface.
- We need a quick way to bring up a specific submission ID from the judges/admin side of things.
- We really need a way for contestants to submit a candidate solution, along with their own test input sets to be compiled and run by the marker machines (obviously actual marking takes priority). There are a few motivations behind this, firstly, it’s insanely hard to get the hardware spec the same over six sites. This will allow contestants to more accurately gage whether their solutions are fast enough. And check for errors that occur inside the marking environment that doesn’t outside of it (We’re jailing non-Java programs without read-write perms on the filesystem, and Java programs are getting a rather stringent policy enforced on them, we’ve seen submissions where the actual output is now being sent to System.out.print{,ln}, but the actual act of creating the old output file still happens, resulting in an Exception indicating the violation of the policy.
- Balloon notifications should stop when blinds kicks in.
- We need a way to export the standings from the standings page, either overall or per-site.
- Contestants needs to be grouped into sites.
- The client should display the time till start/resume of contest.
- Various other admin related configuration methods are really crap. This is primarily due to me focusing on Judging/Contestant activities up to date (correct thing to do IMHO).
Then there are also various other issues in the side that are not typically visible. Some of these are gross oversights and some others are just bad design decisions.
There are some other issues (time synchronization between servers being a big bastard). In particular abacus uses the time() function which returns the number of seconds since epoc in local time. It should be made to use gmtime() instead, and the client should do the conversion between local/gmt using it’s own locale settings, but obtaining the gmt time from the server (Benin’s server was set to SAST time in WAT – meaning that the GMT time differed by 1 hour between it and the SA servers). So the SA servers was at 10:00 SAST and the Benin server at 10:00 WAT, however, converting this to GMT SA was at 8:00 and Benin at 9:00. Bruce made some modifications to the timing and this caused issues for Benin today.
The servers themselves should some way of checking that they are at least reasonably closely synchronized (should not differ by more than a few minutes).
Inter-server communications should return to a pure udp based protocol. Especially with links into Africa this is a major issue. Whilst better than last year the link to Benin was suspect on more than one occasion today, fortunately things survived reasonably well. Previously this was not tested well enough and a udp/tcp combining hack was implemented to transport larger PeerMessages using a notify/pull method over tcp (notify would use udp and transport would go over tcp). This improved congestion control at the network level and works pretty well between SA universities now due to the fiber ring they use, but caused some lag issues for Benin.
The database itself is currently a relational database. This has various problems (one of the commits into abacus this week was to get rid of foreign keys). My primary ones are as follows:
- Unable to dynamically update the DB structure to accommodate different data (structure is rigid).
- Not easy to revision data whilst maintaining concurrency.
- Need different PeerMessage encodings for different updates due to current design.
With the first of these I mean that dealing with different problem types is quite hard. And writing modules that works with different tables is extremely hard, and all modules needs to know the underlying database technology indirectly, or you need a database module that knows all the other modules. Also, not everything fits properly into the designed schema. Period. Having some voice (asterisk) experience I worked a little with astdb. Initially I thought this was really, really crap. I was both very right and very wrong. It doesn’t have any referential integrity, so it’s crap, however, it’s also very free-form, which is really awesome. It’s also very simple. Basically it uses a family+key to get to a value. This can easily be simplified to key => value, but the family gives it a bit of a tree structure. This is similar to (but different) from ldap where you have objects (family) with attribute/value pairs. ldap has schemas which it enforces on objects, so you can’t have random attributes on objects (which is good), however, there is still no referential integrity (a value might reference an object/attribute that doesn’t actually exist).
I came to realize that this is actually pretty perfect for abacus. Consider this, we have users, so we create a base called users. Then we assume the next level is the username, followed by whatever attributes we want (like team name etc …), so we could end up with user jkroon (being the admin) looking something like:
users/jkroon:
name=Jaco Kroon
type=Admin
password=$1$some$hash
Whereas a contestant could look like:
users/up1:
name=Kick Ass
type=Contestant
password=$1$some$hash
site=UP
Now the site itself could again look something like this:
sites/UP:
name=University of Pretoria
Simple. No real glam here. A problem can be stored something like:
problems/Blue:
name=Something
files:
description/name=blue.pdf
description/contenst=#binary data#
description/desc=The problem specification
samplein/name=sample.in
samplein/desc=sample input data in specification
samplein/content=#more binary#
The above might be slightly confusing. Basically the backend now has two calls up the database:
- get(key[, attime]) – Call to get the value (C++ string) of a key, eg db.get(“problems.Blue.files.samplein.name”) which will return the string “sample.in”.
- set(key, value[, at, serv, upkey]) – Will just set a key to a specific value, the at serv and upkey values are not important from a module perspective but can be used internally to add historic revisions when replicating. Also why we need the attime in the previous call.
Other calls will be required for other purposes like finding what revisions was available etc …
The client itself actually also needs to become thinner, in that most of the processing needs to happen with server modules. The server modules should have a way of telling the client what to display and how to act rather than the client being overly intelligent. Similar to a browser concept, albeit today’s browsers are pretty damn smart, it still uses javascript (coming from the server) to do what they do.
This has the advantage that we can replicate the calls to set() above only. Each server will automatically add the at value as now(), it’s own server name and upkey ([serv,upkey] should be unique) before storing in the backing store and replicating.
From here I reckon it will become easier to add more functionality. Time will tell whether I have the guts to attempt what I’ve outlined here, or whether it even makes sense. What I can say is that I’ve learned a heck of a lot with the whole process of designing and writing Abacus. I hope those people who used it to date don’t have too many complaints. It will be back next year :p. Hopefully.
Either way, it has contributed to my life. Hopefully someone else too finds it useful. I was glad to hear today that Wits has installed an Abacus server and have been using the software. Probably mostly because they knew it was going to be used at ACM though.