Steve's talk

Too-much bloody determinism?

Multicore is a thing

Possibly not a problem -- most systems actually work quite well.  Best
case is that transactional memory buys you about 12% (TxLinux).

Widespread belief that you need threads to scale.  Widely believed
that programmers can't do concurrency.

Deterministic programming -- normal programmers shouldn't need to
worry, but dealt with by MapReduce, Ciel, etc.

Alternative: deterministic systems, where programs are deterministic
by construction, becaause the platform doesn't support nondeterminism.

Weakness of deterministic threading: depends on inputs.  Also, almost
everything evaluated on SPLASH, Phoenix, Parsec, etc -> risk of
overfitting.

<I have no idea what happened next>


-----------------------
Verifying transactional programs with programmer-defined conflict detection
Omer Subasi

Example: linked list sorted in ascending order.  Insert transactions
which modify disjoint parts of the list might have physical conflicts
but not logical ones.  Their approach is just to have annotations like
ignore-write-after-read.  Difficult to reason about.

Alternative: use ``right mover'' semantics i.e. say that a particular
operation can always be commuted to the right over other threads'
operations.

a is a right mover if whenever a;b goes to state S, b;a also goes to
state S.

Complication: need to make sure you get consistent reads?

<This looks like it's going to be very specific to implementing linked
lists using transactional memory.>

Generic thing:

-- Validate sequential code
-- Do some kind of abstraction thing to make it atomic
-- Validate it again?

Q: How much is automated?
A: None.


--------------------------
Aviso: Emprical automatic failure avoidance
Brendan Lucia

Looking at concurrency bugs.  Sometimes repro, sometimes don't,
depending on schedule.

Fixed by determinism? No -- schedule memoisation etc. only work for
fixed inputs.

Fixed by testing? No, for usual reasons.

Aviso: run, observe bugs.  Try generating constraints which might ban
the bug, then test them, then see if they worked.

e.g.

lock();
valid = p != NULL;
unlock();
...
lock()
if (valid)
   use p;
unlock()

other thread:

lock();
p = NULL;
unlock();

Easily avoided by imposing scheduling constraints.

Hypothesis: a sequence of events that preceded a failure might be its
cause.

Q: So you're assuming that the cause is proximate?
A: Yes.

Step 1: monitor events during execution, log order over all threads.
Events == synchronization, shared memory accesses, signals, etc.
Prune shared memory events a bit: CFG domination, and also events
which are very close together.

Step 2: generate interesting subsequences.  Consider triples and also
pairs.  Triple: event A from thread 1, then event B from thread 2,
then event C from thread 1.  Pair: Any pair of events in two threads.
Trivially <?> turned into schedule constraints, which are then
instantiated into state machines, and you insert delays to make sure
that you never complete the state machines.

Q: Could run the algorithm backwards to make failure more likely?
A: Earlier work (MSR, ``bug depth'') did that.

Q: Assuming fixed hardware?
A: Don't think so; haven't really thought about it.

Q: This is not a sound technique?
A: No.

Q: Matching cannot be perfect e.g. dependency on inputs?  i.e. how do
   you identify events?
A: <Usual answer about if it being a different sequence then it's a different
   bug.>

More detail:

running the program and have a bunch of available constraints which
aren't currently enforced.  Simulate all of the available constraints
as you run, use that to figure out which ones actually work.  Also how
we go about enforcement.

Vetting constraint: essentially try a bunch of constraints and see
whether they increase the time between failures.

Demonstrate that patches are composable.

Runtime overhead is very reasonable; usually <1%, worst case they've
found is 39%.