COMPSCI 677 - Spring 20
This project is a group project and it is due on
March 4th, 11.59 pm March 8th, 11.59 pm
The goal of this project is to teach you:
- The basics of distributed programing.
- Programming with RPCs/RMIs
- Concurrent programming
- The design of peer-to-peer systems
- The basics of systems design and experimentation.
You can be creative with this project. You are free to use any of programming languages (we recommend C++, Java, or python; contact us beforehand if you plan to use something else) and any abstractions such as RPCs, RMIs, threads, events, etc. that might be needed. You have considerable flexibility to make appropriate design decisions and implement them in your program.
Project description: The bazaar
This project will implement a peer-to-peer market (bazaar). The bazaar contains two types of people (i.e., computing nodes): buyers and sellers. Each seller sells one of of the following goods: fish, salt, or boars. Each buyer in the bazaar is looking to buy one of these three items.
Previously buyers met sellers by screaming for what one wished to buy or sell. However, as the bazaar grew larger and larger, this broadcast method has become too noisy. The village chief has thus decreed that henceforth all bazaar announcements shall strictly follow the peer-to-peer model. Each buyer shall gently whisper their needs to all her neighbors, who will then propagate the message to their neighbors and so on, until a seller is found or the maximum limit on the number of hops a message can traverse is reached.
If a seller is found, then the seller sends back a response that traverses in the reverse direction back to the buyer. At this point, the buyer and the seller directly enter into a transaction (without using intermediate peers).
Assume that the number of people in the bazaar N is specified beforehand (N should be configurable in your system).
First construct a p2p network such all N peers form a connected network. You can use either a structured or unstructured P2P topology to construct the network. No neighbor discovery is needed; assume that a list of all N peers and their addresses/ports are specified in a configuration file. Note that the network is not necessarily fully connected. A peer may be neighbor only to a subset of the total peers.
Once the network is formed, randomly assign a seller or buyer role to each peer, or both. The buyer and seller role are fixed throughout the entire execution. Each seller picks one of three items to sell. Each buyer randomly picks an item and attempts to purchase it; it then waits a random amount of time, then picks another item to buy and so on. Each seller starts with n items (e.g., n boars) to sell; upon selling all n items, the seller picks another item at random and becomes a seller of that item. If a peer is both a buyer and a seller, it will buy and sell different items.
Components and Interfaces
Your system should implement the following interfaces and components (we recommend using RPCs or RMIs; low-level socket programming is also acceptable):
lookup (product_name,hopcount)– this procedure should search the network; all matching sellers respond to this message with their IDs using a
reply(sellerID)call. The hopcount is decremented at each hop and the message is discarded when it reaches 0.
reply(sellerID)this is a reply message with the peerID of the seller
buy(sellerID)if multiple sellers respond, the buyer picks one at random, and contacts it directly with the buy message. A buy causes the seller to decrement the number of items in stock.
Remember: a peer could be both a client and a server.
- As a client, the buyer specifies a
lookup. Upon receiving replies, the buyer peer picks one matching seller and and then connects directly to that peer to finish the transaction.
- As a server, a seller waits for
lookuprequests from other peers and sends back a
replyfor each match. Each
lookuprequest is also propagated to all its neighbors.
lookup requests use flooding. A peer can only contact its neighbors during the lookup process. While
lookup requests use flooding, a
reply should traverse along the reverse path back to the buyer without using flooding (one way to meet this requirement is to have each peer append its peerID to a list which is propagated with the lookup message; the list yields the full path back to the buyer; other techniques are possible which involve stateful peers).
Each peer should be able to process multiple requests/replies at the same time. This could be easily done using threads. Be aware of the thread synchronizing issues to avoid inconsistency or deadlock in your system. For instance, a seller should be able to process multiple concurrent buy requests and decrementing the number of items in stock should be done using synchronization. As part of your design, consider whether to use a thread per request model (where you spawn a new thread for each new request) or a pre-spawned thread pool model at each peer for concurrent event processing.
Evaluation and Measurements
Deploy at least 6 peers. They can be setup on the same machine (different directories). Next deploy the peers such that at least some of the peers are on different machines and demonstrate that your system works over a network. You should be able to run peers on different on Edlab servers (see below for how to access edlab machines). Measure the latencies to process a RPC call between peers on different edlab machines, as well as latencies between peers on you local machine(s). Conduct a simple experiment study to evaluate the behavior of your system. Compute the average response time per client search request by measuring the response time seen by a client for, say, 1000 sequential requests. Also, measure the response times when multiple clients are concurrently making requests to a peer, for instance, you can vary the number of neighbors for each peer and observe how the average response time changes, make necessary plots to support your conclusions.
What You Will Submit
When you have finished implementing the complete assignment as described above, you will submit your solution to the GitHub Classroom repository of your group. We expect you will use GitHub throughout for source code development for this lab, with frequent commits. Please use GitHub to turn in all of the following (in addition to your code)
- Source code with inline comments/documentation.
- An electronic copy of the output generated by running your program. When it receives a product, have your program print a message “bought product_name from peerID”. When a peer issues a query (
lookup), your program will print the returned replies in a nicely formatted manner.
- A seperate design document of approximately two to three pages describing the overall program design, a description of “how it works”, and design tradeoffs considered and made. Also describe possible improvements and extensions to your program (and sketch how they might be made). You also need to describe clearly how we can run your program. Please submit the design document and the output in the docs directory in your repository.
- A seperate description of the tests you ran on your program to convince yourself that it is indeed correct. Also describe any cases for which your program is known not to work correctly. Please submit this document along with the above design doc in the docs directory in your repo. The tests themselves should be checked into a tests sub-directory.
- Include one single script that automatically compiles your code, deploys it on multiple EdLab machines, and runs all your tests and experiments on those machines. You can assume that the graders will have set up passwordless SSH to run your script.
- Performance results of your measurements/experiments should be included in the docs directory. Provide the results/data as a simple graphs or table with brief explanation.
Grading policy for all programming assignments
- Program Listing
- works correctly by running a single script: 40%
- in-line documentation: 10%
- Design Document
- quality of your system design and creativity: 15%
- quality of your design document: 10%
- Performance experiments: 10%
- Development style
- Use of github with checkin comments: 5%
- Thoroughness of test cases: 10%
Note about EdLab machines
- We expect that most of you will work on this lab on your own machine or a machine to which you have access. However we will grade your submission by running it on the EdLab machines, so please keep the following instructions in mind.
- You will soon be given accounts on the CICS Education Lab (EdLab). Read more about edlab and how to access it here
- Although it is not required that you develop your code on the EdLab machines, we will run and test your solutions on the EdLab machines. Testing your code on the EdLab machines is a good way to ensure that we can run and grade your code. Remember, if we can’t run it, we can’t grade it.
- There are no visiting hours for the EdLab. You should all have remote access to the EdLab machines. Please make sure you are able to log into and access your EdLab accounts.