Distributed Systems ETH 2020

A strategy profile is called social optimum (SO) iff it minimizes the sum of all costs.

A strategy is dominant if a player is never worse off by playing this strategy. A dominant strategy profile is a strategy profile in which each player plays a dominant strategy.

A Nash Equilibrium (NE) is a strategy profile in which no player can improve by unilaterally changing its strategy.

e.g. all players play dominant strategy

Find NE: write down every best response, find all NE

Let NE_ be the NE with the highest cost. The PoA is defined as

\(PoA = {cost(NE_-) \over cost(SO)}\)

Let NE+ be the NE with the smallest cost. The OPoA is

\(OPoA = {cost(NE_+) \over cost(SO)}\)

Adding a super fast road between u and v can increase the travel time.

Every game has a mixed NE, this means strategies are chosen non-deterministically.

One good is sold to a group of bidders, Each bidder has a secret value z_i for the good and tells his bid b_i to the auctioneer. The auctioneer sells the good to one bidder for a price p.

An auction is truthful if no player v_i can gain anything by not stating the truth, i.e. b_i = z_i

Truthful bidding is a dominant strategy in a second price auction.

Hash unique filename of movie and unique parameters of each node h(u) -> [0,1) and store the movie on the node if the hashes are minimal. 

Nodes exhibit a high churn if they constantly join and leave the distributed system.

• homogeneous: no node should play a dominant role, no node should be a single point of failure.

• The nodes should have IDs, in the universe [0, 1)

• Every node should have a small degree

• small diameter, routing should be easy. If a node does not have the information about a data item, then it should know which neighbor to ask. Within a few (polylogarithmic in n) hops, one should find the node that has the correct information.

The mesh is a graph with node set V=[m]^d, [m] means the set {0, 1, ..., m-1}. 

The edges \(E = \{\{(a_1,...,a_d),(b_1,...,b_d)\} | a_i,b_i \in [m], \sum_{i=1}^d |a_i-b_i| = 1 \}\)

The T(m,d) torus is an (m,x) mesh and additionally wrap-around edges.

M(2,d) = T(2,d): d-dimensional hypercube

Let d ∈ N. The d-dimensional butterfly BF(d) is a graph with node set V =[d+1]×[2]^d and an edge set E = E1 ∪ E2 with

\(E_1= \{\{ (i, \alpha),(i+1, \alpha) \} | i \in [d], \alpha \in [2]^d\}\)

and

\(E_2 = \{\{ (i, \alpha),(i+1, \beta) \} | i \in [d], \alpha, \beta \in [2]^d, \alpha \oplus \beta = 2^i \}\)

it has (d+1)2^d nodes, 2d*2^d edges and degree 4

A cube-connected cycle network is a graph with node set \(V = \{(a,p) | a \in [2]^d, p \in [d]\}\)

and edge set i-am-very-much-not-going-to-type-this-as-I-wont-be-able-to-remember-anyway

It is defined as an unidirected graph...

It is an unidirected graph with node set V = {v \in [b]^d} and edge set E that contains all edges {v, w} with the property that \(w \in \{ (x,v_1, ...v_{d-1}): x \in [b], \text{where } v=(v_1, ..., v_d)\}\)

The skip list is an ordinary ordered linked list of objects, augmented with additional forward links. The ordinary linked list is the level 0 of the skip list. In addition, every object is promoted to level 1 with probability 1/2. As for level 0, all level 1 objects are connected by a linked list. In general, every object on level i is promoted to the next level with probability 1/2. A special start-object points to the smallest/first object on each level.

Search, insert, delete in O(log n)

A distributed hash table (DHT) is a distributed data structure that implements a distributed storage. A DHT should support at least (i) a search (for a key) and (ii) an insert (key, object) operation, possibly also (iii) a delete (key) operation.

can be implemented as a hypercubic overlay network

We have a fully scalable, efficient distributed storage system which tolerates O(log n) worst-case joins and/or crashes per constant time interval. As in other storage systems, nodes have O(log n) overlay neighbors, and the usual operations (e.g., search, insert) take time O(log n).

releases oldest unpublished block if more than two blocks ahead

it depends on ration of the selfish miner's mining power and the share of altruistic mining power if selfish mining is rational

altruistic = 0 -> break even at 1/3

altruistic = 1/2 -> selfish 1/4

In a DAG-blockchain the genesis block does not reference other blocks. Every other block has at least one (and possibly multiple references) to previous blocks. All references should be relevant in the sense that a reference does not already include another reference recursively.

The weight of a dag-ancestor block a with respect to a block b is defined as the number of tree-descendants of a in the set of dag-ancestors of b. If two blocks a and a′ have the same weight, we use the hashes of a and a′ to break ties.

Let x and y be any pair of dag-parents of b, and z be the lowest common tree-ancestor of x and y. x′ and y′ are the tree- children of z that are tree-ancestors of x and y respectively. If x′ has a higher weight than y′, then block b orders dag-parent x before y.

How To Order: "one part of sub-DAG is heavier => earlier in ordering"

Ethereum is a distributed state machine. It promises to run arbitrary computer programs in a blockchain.
Smart contracts are programs deployed on the ETH blockchain that have associated storage and can execute arbitrary complex logic.

In ETH up to two "uncles" are allowed additionally to the parent.

There are externally owned accounts (EOAs) that are controlled by individuals with a secret key and contract accounts (CAs) that are for smart contracts.

• Nonce: counts how many transactions the account of the sender of the transaction has already sent.
• address of the recipient.
• signature by the user controlling the EOA.
• Value: The amount of Wei to transfer
• Data: Optional, can be accessed by smart contracts.
• StartGas: maximum amount of computation this transaction is allowed to use.
• GasPrice: How many Wei per unit of Gas the sender is paying. a high GasPrice will make sure that the transaction is executed more quickly.

• simple transaction: transfers some native currency from one EOA to another
• smart contract creation transaction: recipient address field set to 0, data field set to compiled EVM code, used to deploy code as a smart contract, it is deployed after it has been mined "sufficiently deep"
• smart contract execution transaction: smart contract address as recipient and code to execute a specific function of that contract in its data field

In Ethereum, like in Bitcoin, a block is a collection of transactions that is considered a part of the canonical history of transactions. Among other things, a block contains: pointers to parent and up to two uncles, the hash of the root node of a trie structure populated with each transaction of the block, the hash of the root node of the state trie (after transactions have been executed).

A smart contract hub is a payment hub that is realized by a smart contract on a blockchain and an off-chain server. The smart contract and the server together enable off-chain payments between users that joined the hub.

• Chain: Accounts hold lottery tickets according to their stake. The lottery is pseudo-random, in the sense that hash functions computed on the state of the blockchain will select which account is winning. The winning account can extend the longest chain by a block, and earn the block reward.
• BFT: The lottery winner only gets to propose a block to be added to the blockchain. A committee then votes (yes, byzantine fault tolerance) whether to accept that block into the blockchain. If no agreement is reached, this process is repeated.

Fork problem, nothing at stake attack: just extend all forks

It can tolerate f < n byzantine failures while terminating in f+1 rounds

It does not fulfil the validity conditions (would need f<n/2 byzantine nodes)

We consider a system with n = 3f +1 nodes, and additionally an unbounded number of clients. There are at most f byzantine nodes, and clients can be byzantine as well. The network is asynchronous, and messages have variable delay and can get lost. Clients send requests that correct nodes have to order to achieve state replication.

Each node will consider one node to be primary and the rest backups.

A view v is a non-negative integer representing the node’s local perception of the system. We say that node u is in view v as long as node u considers node p = v mod n to be the primary.

1. The nodes receive a request and relay it to the primary.

2. The primary sends a pre-prepare-message to all backups, informing them that it wants to execute that request with the sequence number specified in the message.

3. Backups send prepare-messages to all nodes, informing them that they agree with that suggestion. (Needs 2f including its own)

4. All nodes send commit-messages to all nodes, informing everyone that they have committed to execute the request with that sequence number. (needs 2f+1 including its own)

5. They execute the request and inform the client.