Homework 1

Homework 1: FIFO Delivery

In this relatively simple exercise you will write a Bud (or possibly Erlang) module that implements the DeliveryProtocol introduced earlier in the course, but provides stronger 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_chan) one-per-timestep, in the order of their ids, with no gaps.

Requirements

Name your module FIFODelivery. FIFODelivery "is a" DeliveryProtocol, so your module should either include DeliveryProtocol or otherwise define collections named pipe_in and pipe_sent. It must also define a channel collection called pipe_chan (just as the other delivery modules do), representing the receiver end of the channel (and over which we must provide FIFO guarantees). FIFODelivery should work like ReliableDelivery, but should additionally deliver messages to pipe chan with the following guarantees:

1. Only one message (per remote sender) appears in pipe_chan at a time
2. Messages in pipe_chan 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_chan message with ident=n is delivered then a message with n-1 was delivered.

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.

class FC
  include Bud
  include FIFODelivery

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

  bloom do
    timestamped <= pipe_chan {|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

Email the FIFODelivery module code to [email protected] (not @googlegroups.com!!)