Homework 1

Homework 1: FIFO Delivery

In this relatively simple exercise you will write a Bud module that implements the DeliveryProtocol introduced earlier in the course, but provides different guarantees than either of the existing implementations (BestEffortDelivery and ReliableDelivery). The FIFODelivery module you implement will provide first-in-first-out semantics, preserving sender-specific order between a sender and receiver. In plain english, your delivery module will ensure that the receiver sees the messages in the order that the sender intended them to be seen.

To simplify the exercise and narrow the design space, we'll assume that the messages have already been given numeric IDs that represent the sender's intended order (we've already reviewed some techniques you might use to assign IDs to messages that appear in some order). Therefore a FIFO delivery module only needs to ensure that messages are delivered (appear in pipe_out) one-per-timestep, in the order of their ids, with no gaps. There is no need to re-implement the message plumbing or retry functionality already implemented in ReliableDelivery---you may simply use it. For an example of the convention of writing layered software in Bloom, take a look at how ReliableDelivery implements DeliveryProtocol by using BestEffortDelivery, using the import call.

Requirements

Name your module FIFODelivery. FIFODelivery "is a" DeliveryProtocol, so your module should either include DeliveryProtocol or otherwise define collections named pipe_in, pipe_out and pipe_sent. FIFODelivery should work like ReliableDelivery, but should additionally deliver messages to pipe_out with the following guarantees:

1. Only one message (per remote sender) appears in pipe_out at a time
2. Messages in pipe_out appear in an order reflecting the sequence of integers in the :ident column of tuples inserted into pipe_in.
3. There are no gaps: for every positive integer n > 0, if a pipe_out message with ident=n is delivered then a message with n-1 was delivered.

Code Layout

Implement your FIFODelivery module in a file named fifo.rb:

   require 'delivery/delivery'
   require 'delivery/reliable'

   module FIFODelivery
      # Implement your FIFO delivery protocol here
   end

The DeliveryProtocol and ReliableDelivery modules are provided in the lib directory in the course repository. Please use the exact require statements in the above example to use these modules in your code; do not use modified versions of these files.

To run your code, invoke ruby using the -I flag to add the lib directory to Ruby's include path:

   ruby -I/path/to/ptcrepo/lib/ -I. test.rb

Sample Unit Test

The unit test below tests some of the basic guarantees for a single client. It simply transmits a handful of messages in an order inconsistent with their IDs. It then (inefficiently) ensures that on the receiver, for every pair of messages received over the course of the run (call them l and r), if l's id is less than r's id, then l was received before r.

    require 'rubygems'
    require 'bud'
    require 'delivery/reliable'
    # The tests will include your module like this:
    require 'fifo'
    require 'test/unit'

    class FC
      include Bud
      include FIFODelivery

      state do
        table :timestamped, [:time, :ident, :payload]
      end

      bloom do
        timestamped <= pipe_out {|c| [budtime, c.ident, c.payload]}
      end

    end


    class TestFIFO < Test::Unit::TestCase
      def workload(fd)
        fd.sync_do { fd.pipe_in <+ [ ["localhost:12345", "localhost:54321", 3, "qux"] ] }
        fd.sync_do { fd.pipe_in <+ [ ["localhost:12345", "localhost:54321", 1, "bar"] ] }
        fd.sync_do { fd.pipe_in <+ [ ["localhost:12345", "localhost:54321", 0, "foo"] ] }
        fd.sync_do { fd.pipe_in <+ [ ["localhost:12345", "localhost:54321", 2, "baz"] ] }
      end

      def test_fifo
        sender_instance = FC.new(:port => 54321)
        receiver_instance = FC.new(:port => 12345)

        sender_instance.run_bg
        receiver_instance.run_bg
        workload(sender_instance)
        4.times {receiver_instance.sync_do}
        receiver_instance.sync_do do
          receiver_instance.timestamped.each do |t|
            receiver_instance.timestamped.each do |t2|
              if t.ident < t2.ident
                assert(t.time < t2.time)
              end
            end
          end
          assert_equal(4, receiver_instance.timestamped.length)
        end
      end
    end

Note that this unit test does not ensure that correct behavior is preserved when there are multiple senders and a single receiver. Ideally, your implementation should get this right too: the "instructor's copy" of the unit tests adds a few extra checks, including a check that your module supports FIFO delivery for multiple senders.

Submission

To submit Homework 1, please send an email to [email protected] with the subject: "Homework 1". The email's body should contain only your student id.

Attach a file named fifo.rb, containing the module (named FIFODelivery) that you have implemented.