712 Project: Preliminary description (Mar 21 2014)
I've decided to go for a programming project (rather than analysis).
There will be four components to the project.
Part 1
Implement a fifo channel that can span N addresses
across different machines.
Specifically, a program, say C, that when duplicated
at different addresses creates a fifo channel between them.
Here is one (not efficient way) to do it:
-
start process C(j) at each address j
-
establish tcp connections between every pair {C(j), C(k)}
Because tcp is byte-oriented,
the C(j)'s will need to do framing (of the byte stream into msgs).
Come with your own simple scheme or use an existing scheme.
Part 2
Implement a distributed algorithm that uses the fifo channel
of part 1 to implement the distributed termination detection channel
(Chapter 13) for the case where exactly one user is active initially.
Specifically, a program, say D, that when duplicated at different
addresses implements the distributed termination detection of diffusing
computation algorithm (chapter 14).
Part 3
Run some simple distributed application to exercise your implementation
from part 2.
Part 4
Implement a assertion checker process E that sits at one address.
Instrument programs C and D so that they send local state
(values of variables) to E.
E will use the info it gets to build up a global snapshot and
check the assertions that should hold, namely:
-
the engaged nodes and engagement edges form an in-tree rooted
at the start node.
-
start node correctly detects termination
-
...
Summary
To recap, the four parts are:
-
Part 1: distributed program Cdist that implements fifo channel
using sockets.
-
Part 2: distributed program Ddist that implements the
termination detection service using fifo channel.
-
Part 3: an application to run Ddist.
-
Part 4: testing harness
Each part is straightforward.
Use whatever procedural language you want,
e.g., C, C++, Java, Python, Ruby.
It makes sense for all the programs to be in the same language
(e.g., simplifies passing state to assertion checker process).
Using a high-level language should make it easier.
You can develop it on one machine using local tcp connections.
Due: one week before the last class.
Further details
will be uncovered as you ask questions.