FS20

4. Task Graphs

5.

For Map, we do not have to draw anymore nodes in.
For Reduce, we have to get back to one node
For Pack, we reduce once to get the prefix sum, then map out again for the collection.

8. Locks

b)

For fine grained synchronization, we first go from head → tail (holding d, tail) at the end. That’s 6 locks.
Then for the contains, we go from head → d, (head, a, b, c, d) which is 5 more locks
Thus a total of 11.

For optimistic synchronization, we lock d and tail (then we validate).
Again for conains, we lock c and d (and then validate).
So total of 4

9. Linearizability

a)

• Equivalent histories
  • the thread projections are identical
• Sequential history
  • method calls of different threads do not interleave
  • (every invocation is immediately followed by it’s matching response)
• well-formed
  • per thread projections are sequential

A complete history is one without pending invocations.

10. Barriers

a)

The bug in this barrier is the else while(nDone < n).
If the first thread leaves the function completely, setting nDone -= 1 before any other thread can leave the while loop, they are all stuck in there!

b)

non-reusable barrier

11. Wait-Free

a)

The critical state is also automatically bivalent!

a critical state is one where if any thread moves, the state becomes univalent

13. Mixer

a)

Semaphore with initial value 1.

b)

Transactions in TM cannot deadlock. But on the application level, we can still encounter them.
Can definitely livelock though!

What else cannot occur with TM:

• convoying:
  • thread holding ressource $R$ is descheduled while other threads queue up for R
• Priority Inversion
  • lower priority thread holds a ressource that a high priority thread is waiting on
    8

d)

Prove that if binary Consensus not solvable for 2 threads with atomic registers, it’s also unsolvable for $n$ Threads with $n>2$.

Assume that it’s possible. Then the $n-2$ other threads could die immediately. Since it’s wait-free our two remaining threads would still have working consensus.