Project #2: Bulletin Board Consistency Solution

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 that offer sequential consistency, Quorum consistency, or Read-your-Write consistency. You may 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 all articles and not communicate with other student’s servers. You can use any communication protocol/system (e.g. UDP, TCP, and RPC) as you want. In this lab, you will 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 client does not know or care who the coordinator is. All of the other servers are configured 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 one item per line (maybe just the first few words or the title of 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 or disconnect to any server (not just the coordinator) to carry out  any  operation.  Each article has an internal unique ID that is generated by the coordinator. So the contacted server (on a post or reply) will ask the coordinator for the next unique ID to use. The server will 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  be large, you should consider how many articles  should  be  shown

 

 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 to choose or reply. You can decide on the structure and format of an article. There are multiple clients in this system and each client will perform operations concurrently. Your clients will have a simple UI to manipulate the operations on the BB (the look of the interface is up to you). You will need to decide how to represent “reply” articles so that the client may format things properly. To emulate the propagation delay one might see in a wide-area network, you can delay the sending a message (from client to server or server to server) by sleeping a random amount of seconds.

 

 

a)    Implement sequential consistency

 

This means that all clients should see the same order of articles on a read from any server even if they were 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 an arbitrary 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 the coordinator as a control point for your quorum. That is, the client contacts any server, which in turn, contacts the coordinator to do the operation contacting the other randomly chosen servers needed for the quorum. Now, vary the values of NR and NW and measure the cost (as seen from the client) to do a write or read operation. Present data graphs and provide simple analysis.

 

 

c)    Implement Read-your-Write consistency

 

For this, suppose a client C posts an article or reply to a specific server S1. Later, if the client C connects 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 when deployed across different machines. In the quorum protocol, replicas can get out of synch. That is, a reader is always guaranteed to get the most recent article (i.e. the latest ID) from one of the replicas, but there is no guarantee that the history of updates will be preserved at all replicas. To fix this problem, implement a synch operation that brings all replicas up to date with each other and can be called periodically in the background.

 

 

4. Project Group

 

All students should work in groups of size 2.  There are some students who have done the Project 1  without a

 

 partner.  So  if  you  were  doing  the  project  alone but want to find a partner,  we encourage you to use the forum 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, and system calls. Try to catch as many of these as possible. Finally, you should run your clients and servers within the CSE firewall – 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 Survey