What I think about and prove (1000 most common words)
(A description of my research, using only the thousand most common words, as checked by XKCD’s Simple Writer)
I like to think about jobs waiting in lines inside large computer systems. I think about the mean waiting time across all jobs. I have proven new findings in systems where many jobs are run at once. People really like my papers.
I ask the question, “What is the best way to choose what jobs to run?” I have discovered the best way to choose, in the setting where jobs arrive almost as fast as possible. I showed that the best way to choose many jobs to run is the same as the best way to choose one job to run. People already knew the best one-job choice, so this paper settled the question for the many-job situation. While my answer is pretty simple, the ideas I used to prove it are quite hard. A key idea in my paper is how much work a given job has to wait behind. I show that there’s not much more work in my many-jobs-at-once system than in the simpler one-job-at-a-time system. I further show that because the work is about the same, the mean waiting time in both systems is also about the same.
My paper is about the situation where jobs arrive when they like, not at times already known, but also not chosen by a bad guy. Jobs don’t arrive at any one time more or less often. They arrive at any time just as often as at any other time. Job sizes, which are how long jobs take to run, are almost the same. Some sizes happen more or less often, but nothing more is known ahead of time, and there’s no bad guy. I proved interesting ideas in this setting that can’t be proven in the bad-guy setting, which people looked at a lot in the past.
All of what I wrote about above was proven in my first paper. In my second paper, I looked at the situation where jobs had to be sent to different groups when they arrived, one group for each job that is run at a time. I had to create a new system for sending jobs to different groups, and I was able to prove that my new system is the best possible, in the same sense as in my first paper. I’ve also looked at situations where we don’t know a job’s size even after the job arrives, or if we just have a guess for its size. A final line of my work looks at the waiting time of the slowest few jobs to finish, while everything above is about the mean waiting time. I’ve got lots of new ideas that I’m working on right now – I hope I can prove new and exciting things!