416 Distributed Systems: Assignment 7

Due: Apr 14 at midnight

2016W2, Winter 2017

In this assignment you will create a different implementation of the A6 transactional key-value service that has a nearly identical interface and semantics. Your A7 implementation will be based on a distributed block-chain.

High-level description

As in A6, your system will be composed of N nodes and some clients. Your system must provide identical fault tolerance guarantees: nodes can fail and your system must be available even if N-1 of the nodes fail. As before, when nodes fail, they do not come back. Similarly to A6, clients may also fail, and your system must be able to continue as these failures occur.

Your service must implement the key-value service as a distributed block-chain that is distributed among, and known by, all of the nodes. Blocks in this block-chain will correspond to client transactions. Nodes will non-deterministically race to integrate transactions into the block-chain using a proof-of-work approach based on Hashcash.

Your system should have the following structure:

• Client begins a new transaction by communicating with all nodes, issuing get/put requests in a transaction to all nodes.
• When a client commits the transaction, the nodes race to integrate the client's transaction into the block-chain.
• The node that completes a proof-of-work and integrate the transaction block into the chain, broadcast the new block to all nodes. Other nodes verify that the block is valid, stop their work and build on the new block, assuming that it is part of the longest chain of blocks in the block-chain.
• A client/system considers a transaction to be committed if (1) the corresponding block is on the longest chain in the block chain, and (2) this block is followed by validateNum blocks (validateNum, an integer greater or equal to 0, is a new argument in the tx.commit interface). We say that these blocks validate the transaction.

As in A6 your system must provide transactional (ACID) semantics to clients without Durability.

In contrast with A6, you are not allowed to abort a transaction when nodes fail. Non-conflict transactions (that do not overlap in the keys accessed sets) should be able to commit successfully regardless of node failures. Conflicting transactions (that overlap in the keys accessed sets) should execute without blocking (as with optimistic concurrency control), but may abort on an operation when a conflicting transaction has been integrated into the block chain (but not necessarily validated).

The details

Block generation. Each node must implement a mining procedure by which it can generate a new block in the block chain. A node can only compute one block at a time and cannot work on multiple blocks simultaneously. There are two kinds of blocks: no-op blocks and txn blocks.

• A no-op block does not contain any transactions. These blocks are generated so as to prevent pre-computation of long block sequences by malicious nodes. All nodes should always be working on no-op blocks in the background, constantly generating these and adding them to the block-chain.
• A txn block contains a single transaction. When a client notifies a node of a transaction commit (i.e., when the transaction is ready to be integrated into the block-chain), the node stops working on no-op blocks and switches to work on a txn block to integrate the new transaction into the block-chain.

Block chain. Nodes maintain a tree representation of the block chain. The chain is the longest path in this tree, starting at the genesis block whose hash is specified on the node's command line. A node should only compute no-op and txn blocks along the chain, and not along any shorter path in the tree. In the case that there are several (longest) chains, the node should (1) pick the one that does not cause a transaction abort for the current txn block it is generating, or if no txn block is being generated or none cause an abort for the existing transaction, then (2) pick among the chains uniformly at random.

Block data structure. A txn block is a data structure that contains at least the following data:

• A hash of the previous block in the chain (prev-hash)
• A record of the client transaction (txn)
• The ID of the node that computed this block
• A 32-bit unsigned integer nonce

Note that a block hash computed for a txn or a no-op by a node A will always be different from blocks generated by other nodes (for the same txn/no-op) and will always differ from other block generated by node A. This is because a block contains a prev-hash, which uniquely identifies its position in the tree, and a block contains a node ID (e.g., of node A), which makes each block unique to A.

A no-op block is identical to a txn block except that it does not include a txn. Its hash is similarly computed using a proof-of-work algorithm.

Note that a txn block only needs to record the mutating operations in a transaction (i.e., put commands). That is, a transaction in the txn block can be represented as a key-value map that is a subset of the global key-value map, and which contains updated values for those keys that were mutated by put operations in the transaction.

Key-value API. Each node must implement the key-value interface from A6. For this, the node must (1) maintain the key-value store that corresponds to the in-order execution of all the transactions along the block-chain, and (2) it must respond to get/put requests against this version of the key-value store. It must continue to respond to client queries even though the block-chain underneath changes. As noted above, a node may respond with an abort on an operation in the case that a conflicting transaction has been integrated into the block-chain. As in A6, an aborted transaction must remain aborted and can never commit.

For this assignment an outstanding transaction conflicts with a transaction that is part of the block chain if the set of accessed keys by the outstanding transaction overlaps with the keys accessed by puts in the transaction in the block chain.

Applications will use a modified A6-interface to operate on your key-value store. As in A6 you are not allowed to change this client interface. However, you have design freedom to implement this interface however you want.

• Download the updated kvservice.go

• The tx.Commit call includes a validateNum argument for the number of blocks (no-op or txn) that must follow this transaction's block in the block-chain along the longest path before the commit can return with success set to True.
• A client may ask any node for information about the block-chain. This call is part of the connection object, so a client can call connection.GetChildren(node, parentHash) where node is an IP:port string of one of the nodes that was used to create the connection, and where parentHash is either the empty string to indicate that the client wants to retrieve the genesis block. Or, parentHash is a string identifying the hash of one of the blocks in the block-chain. The return value should be the hash values of all of the children blocks that have the block identified by parentHash as their prev-hash value.

Semantic difference between A6 and A7. Although A6 and A7 provide a nearly identical API and have very similar semantics, there are cases in which A7 semantics will differ from A6. Here are a few such cases

Assume you have a chain that looks like: Genesis Block <- Block 1{TX1, validateNum: 6} <- Block 2{TX2, validateNum: 1}. Then, once TX2 is validated, the client for TX2 should get their commit returned regardless of whether TX1 has been validated. This has two outcomes:

• 1. A txn that appears logically earlier in the chain does not get to commit until after a txn that appears logically later in the chain (this is because commit must block until validateNum is satisfied)
• 2. A txn always operates on the latest state of the key-value store. This state may include txns that have not been validated. In a sense this is a violation of the strict independence requirement in A6.

Assumptions you can make

Identical to A6:

• Each node and each client will run in its own VM (e.g., will have a unique IP address and have the usual port range available).
• All nodes will start within 4 seconds of each other.
• Clients will not start until all nodes have started and have been running for 4 seconds.
• Clients will not issue get requests on keys that have no values (have not been written with a put request).
• The client library only needs to support one transaction at a time for the application it is hosting (does not need to support multiple concurrent transactions).
• Each node can be identified by a unique ip:port argument (give on the command line)
• No network failures.
• txID values must be monotonically increasing and correspond to the serialized ordering of transactions (as observed by the client). The txID values can skip numbers (e.g., txID for one transactions could be 5, and for the next transaction could be 42).
• Node-node and node-client round-trip times are at most 2s.
• The client will pass a list IP:port strings, one per kv node, in its call to NewConnection. Each of these IP:port strings will be an external IP:port that corresponds to the listen-client-in IP:port for some kvnode instances (see below). This list of IP:port strings is not guaranteed to be in any particular order.
• Nodes, started using your submitted kvnode.go file, will be passed an identical [nodesFile] argument.

• Nodes execute on VMs provisioned with identical compute resources.
• All nodes will be started with same num-zeroes argument.

Assumptions you cannot make

Identical to A6:

• Nodes have synchronized clocks (e.g., running on the same physical host).
• Perfectly reliable network (e.g., if you use UDP for your peer protocol, expect loss and reordering)
• Nodes/clients fail at some particular time or in some particular order.

Implementation requirements

• The client code must be runnable on Azure Ubuntu machines configured with Go 1.7.4 (see the linked azureinstall.sh script and the Google slides presentation for more info).
• Your solution can only use the standard library Go packages.
• Your solution code must be Gofmt'd using gofmt.

Extra credit

The assignment is extensible with extra credit. You must create an EXTRACREDIT.txt file in your repository and specify in this file which extra credit features you have implemented, one per line, e.g., EC1.

EC1 (3% of final grade): A benefit of a proof-of-work design is that it makes it challenging to mount Sybil attacks. However, a majority of nodes can still collude to disrupt the system.

Create a malicious node (malicious-kvnode.go) that takes identical arguments to a regular node and mounts a denial of service attack against your system by sneaking in spurious transactions into the block-chain that cause real client transactions to abort. Your malicious nodes should behave like regular nodes when a minority (< 50%) of nodes are malicious. When a majority (> 50%) of nodes in the system are malicious, the malicious nodes should activate and behave maliciously, attempting to abort every received client transaction.

EC1 will be tested without node failures. Your malicious nodes should abort client transactions with a probability proportional to the number of participating malicious nodes.

EC2 (2% of final grade): Add support for adding new nodes to the system. You have to do this without changing any of the existing interfaces. The new node will be given a list of all the nodes that have ever existed in the system (regardless of whether or not they are currently alive). Once a new node has joined, it should print out "JOINED-SYSTEM\n" to stdout. At this point it should be safe to terminate all nodes except for the newly joined node and have the system continue to operate without unavailability.

Solution spec

You must submit kvnode.go, your version of kvservice.go, and any other go files your service implementation requires. Clients should be able to use your library by (1) setting GOPATH to the root of your repository, and (2) using import "./kvservice" at top of file.

The kvnode process command line usage must be:

• [ghash] : SHA 256 hash in hexadecimal of the genesis block for this instantiation of the system (new in A7).
• [num-zeroes] : required number of leading zeroes in the proof-of-work algorithm, greater or equal to 1 (new in A7).
• [nodesFile] : a file containing one line per node in the key-value service. Each line must be terminated by '\n' and indicates the IP:port that should be used to by this node to connect to the other nodes in the service.
• [nodeID] : an integer between 1 and number of lines in nodesFile. The IP:port on line i of nodesFile is the external IP:port corresponding to the listen-node-in IP:port, which will be used by other nodes to connect to this node.
• [listen-node-in IP:port] : the IP:port that this node should listen on to receive connections from other nodes.
• [listen-client-in IP:port] : the IP:port that this node should listen on to receive connections from clients.

Rough grading rubric

• 5%: No failures, 1-client, non-aborting txns
• 5%: No failures, 1-client, aborting and non-aborting txns
• 10%: No failures, n-clients, non-conflicting txns
• 15%: No failures, n-clients, conflicting txns
• 15%: No failures, n-clients, deadlocking txns progress check
• 5%: Client-failures, n-clients, incomplete txns abort
• 5%: Client-failures, n-clients, committed txns retained
• 2%: Node-failures, 1-client, kv-service available
• 2%: Node-failures, n-clients, kv-service available
• 2%: Node-failures, n-clients, aborting and non-aborting txns
• 5%: Node-failures, n-clients, non-conflicting txns
• 6%: Node-failures, n-clients, conflicting txns/deadlocking txns progress
• 4%: Correct behavior of validateNum
• 4%: Block-chain evolves correctly as observed via GetChildren
• 5%: Node+Client-failures, n-clients, non-conflicting txns
• 5%: Node+Client-failures, n-clients, conflicting txns
• 5%: Node+Client-failures, n-clients, deadlocking txns progress check

Make sure to follow the course collaboration policy and refer to the assignments instructions that detail how to submit your solution.