Description
1. Overview In this project, you will implement a simple Bulletin Board (BB) system (like our Moodle forum) in which clients can post, reply, and read articles stored in the BB. The BB is maintained by a group of replicated servers thatoffersequentialconsistency,Quorumconsistency,orRead-your-Writeconsistency.Youmay reuse any of the code developed in Project 1 or you can start from scratch. However, unlike the PubSub system, your server(s) will store and remember allarticlesandnotcommunicatewithotherstudent’sservers. You canuseanycommunicationprotocol/system(e.g.UDP,TCP,andRPC)asyouwant.Inthislab,youwill learn about how to implement various forms of consistency and their tradeoffs. The desired consistency mechanism is supplied as a parameter at runtime.
2. Project Details The project will be comprised of: clients and servers (one of the servers is designed as the primary or coordinator). The clientdoesnotknoworcarewhothecoordinatoris.Alloftheotherserversareconfigured to know who the coordinator is. Clients can connect to any server(s). Thus, the client knows the address of every server (you may deploy servers on the same machine with different ports if you like or within virtual machines). To keep things simple, there is only one BB with a single topic stream. The operations that the clients should be able to perform are below: 1. Post an article 2. Read a list of articles and display the list oneitemperline(maybejustthefirstfewwordsorthetitleof the article) 3. Choose one of articles and display its contents 4. Reply to an existing article (also posts a new article)
Internally, the client should be able to connect ordisconnecttoanyserver(notjustthecoordinator)tocarry out any operation. Each article has an internal unique ID that is generated by the coordinator. So the contacted server (onapostorreply)willaskthecoordinatorforthenextuniqueIDtouse.Theserverwill order the articles in increasing order using the ID (1, 2 …) as this captures time order. For the Read comment, the client should print the articles in this order using indentation for replies, e.g. 1 Article 1 2 Article 2 3 A reply to Article 2
4 A reply to Article 2 5 A reply to Article 4 Since the number of articles in the BB can belarge,youshouldconsiderhowmanyarticlesshouldbeshown in a page and how to enable subsequent pages to be shown.
The article IDs are returned with the article and can be used both in formatting and in calls tochoose or reply.You can decideonthestructureandformatofanarticle.Therearemultipleclientsinthissystem and each client will perform operations concurrently. Your clients will have a simple UI to manipulate the operations ontheBB(thelookoftheinterfaceisuptoyou).Youwillneedtodecidehowtorepresent“reply” articles so that the client may format things properly. To emulate the propagation delay one might see in a wide-area network,youcandelaythesendingamessage(fromclienttoserverorservertoserver)bysleeping a random amount of seconds.
a) Implement sequential consistency This means that all clients should see thesameorderofarticlesonareadfromanyservereveniftheywere posted by concurrent clients to any servers. You can use the primary-backup protocol. b) Implement quorum consistency Given N replicas, you will to assemble a read quorum (NR) which is anarbitrary collection of servers in order to read/choose, and a write quorum (NW), an arbitrary collection of servers in order to post/reply for the client. The values of NR and NW are subject to the following two constraints: 1. NR + NW > N 2. NW > N/2 You may use thecoordinatorasacontrolpointforyourquorum.Thatis,theclientcontactsanyserver,which in turn, contacts the coordinatortodotheoperationcontactingtheotherrandomlychosenserversneededfor the quorum. Now, vary the values of NR and NW and measure thecost(asseenfromtheclient)todoawrite or read operation. Present data graphs and provide simple analysis.
c) Implement Read-your-Write consistency For this, suppose a client CpostsanarticleorreplytoaspecificserverS1.Later,iftheclientCconnects to a different server S2 and does a read or choose, they are guaranteed to see the prior updates. You can use the local-write protocol. Measure the cost of client operations and compare.
For all consistency policies, measure the cost of client operations, and compare across the policies.
Done Early? Try this for no extra credit: d) Allow the coordinator to fail and hold a leader election to determine a new coordinator. e) Pick another consistency policy to implement.
To realize your project goals, you have to define an API for server-server communication to propagate updates, request new article IDs, and so on. This is up to you to define.
3. Implementation Details You may borrow code that you like from Project 1.Do not use any code found on-line. To make multiple servers run easily, your servers may run in a single machine with different port numbers. Note that your servers are also expected to work whendeployedacrossdifferentmachines.Inthequorumprotocol,replicas can get out ofsynch. That is, a reader is always guaranteed to get the most recent article (i.e.thelatestID) from one of the replicas, but thereisnoguaranteethatthehistoryofupdateswillbepreservedatallreplicas. To fix thisproblem,implementasynch operationthatbringsallreplicasuptodatewitheachotherandcan be called periodically in the background.
4. Project Group All students should work in groups of size 2.TherearesomestudentswhohavedonetheProject1withouta partner. So if you were doing the project alonebutwanttofindapartner,weencourageyoutousetheforum to find your partner.
5. Test Cases You should also develop your own test cases for all the components of the architecture, and provide documentation that explains how to run each of your test cases, including the expected results. Also tell us about any possible deadlocks or race conditions.
There are many failure modes relating to the content of messages,parameters,andsystemcalls.Trytocatch as many of these as possible.Finally, you should run your clients and serverswithintheCSEfirewall– as outside access particularly through UDP and TCP may be blocked.
6. Deliverables a. Design document briefly describing each component. Performance graphs and simple analysis. Not to exceed 3 pages. b. Instructions explaining how to run each component and how to use the service as a whole, including command line syntax, configuration file particulars, and user input interface. c. Testing description, including a list of cases attempted (which must include negative cases) and the results. d. Source code, makefiles and/or a script to start the system, and executables.
Note: a, b, and c should be in a single document file.
7. Grading The grade for this assignment will include the following components: a. 20% – The document you submit – This includes a detailed description of the system design and operation along with the test cases used for the system (must include negative cases) b. 70% – The functionality and correctness of your own server and clients c. 10% – The quality of the source code, in terms of style and in line documentation
8. Resources a. D. K. GIFFORD, Weighted voting for replicated data , in Proc. 7th Annual ACM Symp. Oper. Sys. Principles (SIGOPS), ACM, New York, 1979. b. S. B. DAVIDSON, H. GARCIA-MOLINA, AND D. SKEEN, Consistency in partitioned networks , ACM Computing Surveys, 17 (1985).
