Determinator
------------

why determinism?
  debugging, fault tolerance, intrusion detection

Deterministic scheduler?
  user-level scheduler on top of non-deterministic kernel scheduler
  instruction quanta vs time quanta (non-determinism still remains in programming model, just gets eliminated in repeat executions, not satisfactory, because impossible to test on all inputs and corresponding non-deterministic choices)

Non-determinism examples?
  * x++        and        x++
  * x = 1;     ASSERT(x || !y);
    y = 1;


Spaces vs. Processes? Same thing, different name.

Spaces vs. Unix Processes? Hierarchical namespaces, private filesystem state (can see only causally prior writes)

Spaces vs. Threads? Private Workspace, explicit and deterministic synchronization!

Read/write races? What if there are multiple state elements?

Conflicts vs. Write/Write Races? Do conflicts depend on the execution schedule?

Programming model today? shared memory. Programming with shared memory is hard! Solution: locks. Do locks get rid of non-determinism? What if you could record the order of synchronization operations [Kendo]?

Explicit Non-deterministic inputs: rdtsc, in/out, random numbers, etc. all these should be "controllable" for determinism to work

Synchronization: check-out, check-in model with conflict detection and reporting using exceptions (e.g., UNIX signals). Actors example. In this new world, a race condition is a program error!

Deterministic synchronization API? fork/join, barrier, futures

Futures? Discuss Multilisp concept from [32]

Locks? why non-deterministic? how to make deterministic? (possibly grant lock at explicit synchronization points, and choose the acquirer based on some fixed order)

Semaphores? non-deterministic if multiple actors can P() (or V())? Deterministic if only one actor P()s and one actor V()s.

Pipes similar.

Unix Namespace non-deterministic, why? malloc, open, mmap, fork? what is non-deterministic with these calls in multi-threaded programs? When would they be deterministic? Scalability implications (discuss Corey reference).

Spaces: discuss figure 2.

Why hierarchy? How else do you communicate across processes and make them deterministic?

Performance implications?
How best to implement the following workloads on Determinator (think about performance):
1. Web server with updates to filesystem
2. Concurrent hit-counter update in web server.
3. Data-parallel analytical processing
4. Concurrent hash table. (how many conflicts on average?)
5. Concurrent tree updates. (how many conflicts on average?) What happened to read/write races that one has to worry about on shared-memory?

Could you have deadlocks? Why not!

System call API? This is orthogonal to the determinism issue.

Put/Get/Ret.

If the parent calls put/get while child still executing, it waits for child to call "Ret" (rendezvous" semantics

Merge on get? byte-level merge.

Ret for exceptions, synchronization (including exit)

Pre-emption: start with limit
Fork: Use put/start. pid process local. what if we wanted it to be system-global?
Exec: Create new child process, load executable in child, then get to parent (thus maintain all original process attributes but change the executable)
exit: ret
waitpid: 'get' waiting for child's 'ret'. If 'ret' for something other than exit, simply start the child again after servicing its request
wait: waits for the child that forked earliest.
  consequences on shell that use wait to report when background processes complete?
  consequences on performance when parent looking to maintain a constant pool of workers? determinator answer: spawn as many workers as you like and let the system take care.

Filesystem semantics: distributed FS weak consistency semantics. Mark conflicts in file so that future opens fail. open/close/read/write are library functions that operate on the local in-memory FS state of each space.

Distributed Computing? Similar to distributed shared memory, just that explicit synchronization points reduce communication costs

Console output?
  One option was to simply use ret/get all the way to the root for each console output character. This would be very inefficient. Instead, determinator uses a local buffer for each space to which console output is appended. This local buffer is then transported all the way to the root using ret/get. Simultaneous console outputs by the child and the parent are handled by appending the child's output to the parent's in the parent space and vice versa.

Console input?
  Just like Unix, each keyboard input is tagged with the ID of the 'in-focus' space (note that the ID of a space can be represented by a string of pids starting from root to that space). The input will arrive at the root and then routed to the respective space. Routing can happen either in 'push' mode (parent calls put and waits for child) or 'pull' mode (child calls get and waits for parent).

Implementing mutex:
	use a 'parent scheduler' which uses instruction-limiting to schedule children.
	One way: Use 'ret' to the scheduler to implement 'lock'. If lock already taken, the scheduler calls 'get' on the current owner to obtain ownership.
  The way they implement: have an 'owner' of a lock at all times. lock/unlock calls by owner dont need to ret to scheduler. lock call by others will ret to scheduler and scheduler will get on the owner. If the owner is not holding a lock, it should ret after a fixed scheduling slice.
  Special handling of pre-emption in the middle of synchronization functions

Experiments;
  Coarse-grained parallel benchmarks peform well (sometimes better than Linux surprisingly, though this is not well investigated)
  Fine-grained parallel benchmarks perform poorly
  scales over multiple hosts in cluster too (though qemu-based experimental setup questionable)


Some questions to think about:
1. How would you implement client/server? How to ensure that you will not have DoS due to untrusted clients?
   (hint: least common ancestor can act as broker)
2. why tree? why not flat topology where anybody can send/receive or get/put/ret to anybody else?