Distributed
Computing – Fall 2005
Office Hours: Wednesday
after class (7:00 PM), Room 604, WWH
Final Project:
v
A graphical Responder by Chris
Fagiani.
v The specification of the project
v An image of a full network. An image of a partial network
v
Before
you begin programming:
Ø
You
can download Java sdk from here
Ø
If
you don’t know Java, Sun’s Java Tutorial
is a good place to start
Ø
You
should as well go over threads, and synchronization.
Here is a nice example of
synchronization.
Ø
You
should get familiar with Java Remote Method Invocation
(Java RMI) (in order to invoke each
other’s processes)
§
An example of a
client/server
§
A full example of a conversation between two entities:
·
A documentation of
the example
·
Files for Windows –
please go over README.txt before
you try to execute the files
·
I removed the files for Sun as they only complicated this example.
If you are using Sun you’ll have to
figure out the RMIregistry issues by yourself.
v
The
following describes the interfaces and classes that you should implement:
Ø
A documentation of the interfaces
Ø
.class files for
Windows.
Ø
.class files for
Sun
Ø
You
should write a class called FinderImp.java that implements Finder.java
Ø
You
should write a class called ResponderImp.java that implements Responder.java
Ø
You
should write a class called AntImp.java that implements Ant.java
Ø
You
should use Location.java (or inherit it)
Ø
You
can implement any other class which you think is necessary
v
‘main’
procedures and batch files:
Ø
Please
read this first.
Ø
The
‘main’ procedure
for the Finder.
Ø
The
‘main’ procedure
for the Responder.
Ø
Batch
files: run.bat,
run2.bat, runResponder.bat,
runFinder.bat
and runRMI
v
Reference implementation
of communication portion of Responder and Finder:
Ø
The
reference includes a full implementation of the project, thus you can test both
your Responder and Finder. Note that my implementation is minimal and is only
intended in order for you to test the RMI settings. You should be able to use
your own Finder and Responder in order to test the efficiency and correctness
of your algorithms (especially note that my Finder always reports 0 golden
paths). If my Finder reveals the Responder’s network in fewer rounds than
yours, then you should strongly consider redesigning your algorithms ;-)
Ø
Make
sure you read the file README before
trying to execute the project.
Ø
During
the contest in class we will use the same .bat that are provided here, so make
sure that your project runs correctly when using them.
v
Submit
the following:
Ø
A
complete code
Ø
A
description of the Finder's algorithm for dispatching the Ants (not more than 1
page long).
Ø
A
description (or an image) of the Responder's network and an explanation why you
chose that particular network topology. A description of the algorithm for
deciding when/where to kill an Ant (both together not more than 1 page long).
Ø
If
you wish your Finder/Responder to take a part in the Ant Wars competition
please email me your code until December 4.
v
Grading:
Ø
60%
- The Finder's algorithm for dispatching the Ants. It is evaluated based on a
reasonable speed of finding the various paths. If the best programs take t
time for a given Responder topology then as close to t one can get as
possible (disregarding luck) the better one does. For those programs that are
not involved in the class competition, we will try three topologies.
Ø
5%
- The topology of the Responder's network.
Ø
20%
- The Responder's algorithm for killing Ants.
Ø
15%
- Overall structure (including coding).
Ø
You
get a slight subjective bonus if you perform credibly at the competition.
v UPDATES:
Ø
Dec
2 – The order of the Locations in the Golden paths should be from source to
destination.
Ø
Nov
23 – I uploaded new .class files, please download them (the reference
implementation was also updated).
Ø
Nov
23 – There is a new section of ‘main’ procedures and batch files.
Ø
Nov
18 – A grading criteria was posted.
Ø
Nov
18 – An addition to the submission rules: a description of the algorithm for deciding
when/where to kill an
Ø
Nov
16 – Update to the specification: only three golden paths should be reported by
the finder, as explained in the spec.
Ø
Nov
14 – Update to the specification: a golden path is a simple path (i.e. no
repeated nodes).
Ø
Nov
10 – New submission rules were defined above.
Ø
Nov
10 – Update to the specification: if the distance of the optimal path is d,
then a golden path is up to distance of d+2.
Ø
Oct
31 – Update to the specification: the Responder removes ALL the links from at
most 50 of the nodes (instead of part of the node’s links).
Ø
Oct
19 – Reference implementation is available.
Ø
Oct
17 – The class Utilities was added. Please use its static variables to define
your network, number of Ants and etc. (the values of the variables match those
in the project’s description). In addition, it includes a method that can be
used for printing the network.
Homework #1: