Thesis Proposal: Theoretical Foundations for Modern Multiprocessor Hardware

Naama Ben-David gave her proposal this morning on Theoretical Foundations for Modern Multiprocessor Hardware.

Is there a theoretical foundation for why exponential backoff is a good design?  Exponential backoff is a practically developed algorithm that 0.

To develop such a foundation, we need to a model of time; however, requests are asynchronous and not according to a single time source.  To address this, model time with adversarial scheduling.  Thus when performing a request, there are three sources of delay:

• self-delay: backoff, sleep, local computation
• system-delay: interrupts, context switches
• contention-delay: delay caused by contention

Given this model, the adversary can, to a limited degree, decide when requests that an entity's request have passed from self-delay into the system delay can then move to contention-delay and ultimately be completed.

In BBlelloch'17, this model was applied and the work measured for different approaches.

• With no backoff, there is omega(n³) work.
• Exp backoff reduces to theta(n² log n) bound on work
• The paper also proposes a new algorithm that has high probability of O(n²)

The second phase of work is developing simple and efficient algorithms for systems that have non-volatile memory (NVRAM).  With NVRAM, on a crash or system failure, the contents in memory persist across reboot (or other restore).  This permits the system to restore the running program(s) to a finer degree than happens from auto-saves or other current techniques.  However, systems also have caches, which are not persistent.  Caches are presently managed by hardware and make decisions as to when to write contents back to memory.  Algorithms must work with the caches to ensure that results are safely in memory at selected points of execution.  There are a variety of approaches for how to select these points.

The third phase of work is modeling RDMA (remote direct memory access) systems.  Can there be a model of the different parts of such a system: memory, NIC (network interface card), and CPU?  Then explore the contention as well as possible failures in the system.

One scheme is for every processes to also be able to send messages on behalf of its shared memory neighbors, so that even if a process fails, its ability to participate in algorithms, such as consensus, is still possible.

Being a proposal, ongoing work will work on instantiations of these algorithms to measure the practical performance.

Richard Lipton - Knuth Prize (Practice) Talk

Richard J. Lipton is the 2014 winner of the Knuth Prize.  His talk today was a summary of his work, which lead to received the prize.  The talk proved to be a series of short anecdotes, which are difficult to capture, but I've copied down the highlights, as best as I can.

"Do problems have labels?"  For example, simulate a queue as two stacks, is this a theory problem or system problem?  At the time, the qualifying exams were split by problem types, so labeling it mattered for which exam contained it.  Faculty at Yale were 50/50 split on whether to mix the problem types and instead students would sit for several days of CS questions rather than a theory day, then a systems day, etc.

Finding a division, separator to a planar graph, in root time.  T(n) <= C*T(n/2)
In explaining the result to Knuth, while visiting Tarjan, who responded "You've ruined my lunch."  As the result destroyed the best known algorithms that were being written, at the time, in Vol. 4.

"Throw away comments are wrong"  Many introductions make inaccurate statements like "non-uniform cannot imply uniform".  There is the work of Karp-Lipton dealing with non-uniform circuits and the uniform nature of algorithms.  The proof was later handed out on tote-bags at CCC 2010.

"Think in High Dimensions"  Binary search in high dimensional space, still logarithmic in the number of elements.  For example, take a planar graph and split it by the intersections, each slab is linear and can be quickly searched.

"Learn New Tools"  Now, one tool is "Probabilistic method" published on June 28, 1974, which shortly thereafter was a Yale seminar.  "By an Elementary Calculation" means to Erdos to use Sterling's approximation, which in one case required taking the approximation to 7 places.  Before learning this method, had been asked about the problem of Extendible Hashing, and had no idea and put it out of mind.  Later asked about it again, and the problem solved easily (or perhaps two days of proofs).

"Guess Right" One problem in solving problems in the community is that we are guessing wrong.  "It is really hard to prove false statements."  Take the problem of detecting whether a sequence of a_nb_m has n = m?  Possible using a multi-pass scan with a probablistic FSM.  Can do with one-way (i.e., single pass)?

"Need a Trick" Solving a problem of vector addition, with fixed counters, with adding and subtracting (where cannot subtract from 0).  1 counter is decidable, 2 counters is not.  But if there is no test for whether the counter is 0.  Proved it takes EXPSPACE-hard.  Pair counters, so add is subtract and vice versa.

"My Favorite Two Results" - Proving that a a^-1 = 1, in long sequence (abaaaba^-1...) can be done in LOGSPACE.  Do so by replacing the a, b with matrices, then modulo prime.  Given the distributed law and applying in any order, prove that it always stops on any expression.

"Future" Old problems, yes.  But dream of finding proofs to math problems that use CS theory tricks.

Computer Science Education (part 0 of N)

Besides my usual semesters of computer science courses and research, this fall I'm cross-enrolled at a neighboring university that offers education classes. Last night had some very interesting conversations. We are starting to prepare syllabi for the course we'd either ideally teach or want to be prepared to teach. I was in a group with two education PhDs (most of the class are). They consented to consider an introductory computer science course and answer two questions.

What are common naive theories that students have entering the course?
How might the course be designed to encourage students to reconstruct their theories?

So what naive theories do students have?

First, computers are magical. No, computers do exactly what a programmer tells them to do. (More advanced students learn about race conditions, compiler influence on correctness, etc). Which, unfortunately, means that if a computer is not doing what you want it to do, then you instructed it incorrectly (c.f., The rat is always right).

Second, I'm going to be a game programmer. No, most computer scientists do not write games (or at least, aren't paid to). But we find many other interesting parts to the field. Besides, many game programmers are treated little better than grad students.

Do you know other naive theories?

Then after class, I spent some time discussing more "advanced" theories in computer science.

Functional versus imperative programming. Does one paradigm exist to rule them all? Is one class of programming languages sufficient? Do students gain by learning about both paradigms? I discussed this briefly in Is versus ought, and have been regularly reading a strong function view in Existential Type.

Big 'O' notation and algorithm / data structure selection. I previously discussed this some in Know your N. And was co-author on a paper, "Brainy: effective selection of data structures", that demonstrated actual data structure selection for a program is not always best from the "Big 'O'" point of view.

Language equivalence. Related to functional versus imperative and one of my first posts, "Problem Solving via Programming", programming languages are theoretically equivalent (i.e., turning complete). But in practice languages should be selected for particular problems. What problems are best for specific languages?

What are some other major theories about computer science that students should know?