Zero-Sum Game

Posted on December 31, 2015 by admin

Definition

The utility functions of both players sum up to 0

Equilibrium

Unique Equilibrium

If the utility function of each player has concavity, then there exist a unique equilibrium.

[Leetcode] Unique Path II

Posted on December 31, 2015 by admin

Problem

Follow up for “Unique Paths”:

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,

There is one obstacle in the middle of a 3×3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is 2.

Note: m and n will be at most 100.

Analysis

Similar to Unique Path except that we need to decide whether a position has obstacle or not

If yes, the number of ways to it is 0

Code

[Leetcode] Unique Path

Posted on December 31, 2015 by admin

Problem

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

Analysis

对于每一格，有两种到达它的方式，即从左边，或者从上边

所以 count[i][j] = count[i-1][j] + count[i][j-1]

Time: O(n^2)
Space: O(n^2)

Space可以进行优化为O(n), 因为计算count每一行的值的时候只需要上一行的信息

Code

How to come up with new ideas in security domain

Posted on December 30, 2015 by admin

The followings are my own experience in finding research ideas in security domain.

Ideas from Security Threat

What the defenders can do to improve security?

How to detect attackers?
How to defend against attackers?

For the cloud computing problem, the defenders can be further divided into two categories: (1) Cloud provider (2) Cloud benign users

What the attackers can do to increase damage?

Ideas from Existing Work

Improve

Scalability of their mechanism

Combine

Can we combine other mechanisms with their mechanism

New Problem

Can we use the proposed mechanism to solve a different problem

New Mechanism

Can we solve the problem with a better mechanism

Naming

Posted on December 30, 2015 by admin

Naming Entities

A name in a distributed system is a string of bits or characters that is used to refer to an entity
Type of names

Address

The name of an access point of an entity

Identifiers

A name that uniquely identifies an entity

Location-independent name

A name that is independent from its addresses

Name Resolution

A naming system maintains a name-to-address binding for resources
Main problem in naming

How to do name resolution in a distributed systems in a scalable way

Approaches for name resolution closely tied to naming scheme
Flat vs Structure naming

In a flat name space, identifiers are random bit strings
No information on location embedded in name

Name Resolution in a Flat Name Space

Simple solutions that work in a LAN environment

Broadcasting & Multicasting

Message containing identifier of the entity is boardcast
Machine with access point for the entity replies with the address of the access point

ARP protocol for finding the data-link address of a machine given the IP address
When network grows, multicast is more efficient

Forwarding pointers

When an entity moves from A to B, it leaves behind a reference to its new location at B

Home-based Approaches

Home agent keeps track of current location of mobile entity

Hierarchical Approaches

Similar to DNS

What is a DHT

Distributed Hash Table

key = hash(data)
lookup(key) -> IP address
send-RPC(IP address, PUT, key, value)
Send-RPC(IP address, GET, key) -> value

Chord

Structure Naming Systems

Names are organized into name spaces

A name space can be represented as a labeled, directed graph wit two types of nodes

Leaf nodes and directory nodes
Absolute vs relative path names
Local names vs global names

Name resolution: the process of looking up a name

Closure mechanism

Knowing where and how to start name resolution

Unix File Name Spaces

Linking and Mounting

Symbolic link

Mounting remote name spaces

Implementing Name Spaces

Naming service

A service that allows users and processes to add, remove, and lookup names

Name spaces for large-scale widely distributed systems are typically organized hierarchically
Three layers used to implement such distributed name spaces

Global layer

root node and its children

Administrational layer

Directory nodes within a single organization

Managerial layer

Example: DNS name space

Iterative vs Recursive Resolution

Recursive

puts a higher performance demand on each name server
cons

Too high for global layer name servers

Pros

Caching is more effective
Communication costs may be reduces

Example

Iterative

Example

Attribute-based Naming

An entity is described in terms of (attribute, value) pairs
Each entity can have several attributes
Attribute-based naming service are called directory services
LDAP (Lightweight directory access protocol) defacto industry standard

Based on OSI X.500 directory service

Another example: UDDI for web services

Cloud Virtual Machine Allocation

Posted on December 29, 2015 by admin

Concerns

When a user request for a virtual machine in the cloud, the cloud provider needs to allocate a VM for the user.

There are three concerns a cloud provider needs to take into account when doing the VM allocation.

Load Balance
Power Consumption
Security

For security, we aim to avoid the cloud covert channel attacks in which an attacker seeks to be co-locate with the target VM in order to extract private information from the victims.

Popular VM Allocation Policies

The following table [1] shows the popular VM allocation policies.

Reference

[1] Using Virtual Machine Allocation Policies to Defend against Co-resident Attacks in Cloud Computing, by Yi Han et al, in Transactions on Dependable and Secure Computing

Vickrey-Clarke-Groves (VCG) Mechanism

Posted on December 29, 2015 by admin

Introduction

VCG can maximize the social welfare given the individuals are all “selfish”

Model

Players

There are $n$ game players, $P_1, P_2, cdots, P_n$

Actions

The actions of the players are denoted as $X = (x_1, x_2, cdots, x_n)$

Payoff

$v_i(X)$

Real demand

$v_i$

Cost

$p_i$ for its action

Utility

$u_i = v_i - p_i$

Definition

Following Nisan’s work, the terms “mechanisms” and “incentive compatible” are defined as

Mechanism

Given a set of n players, and a set of outcomes, A, let $v_i$ be the set of possible valuation functions of the form $v_i(a)$ which player $i$ could have for an outcome $a in A$ . A mechanism is a function $f: V_1 cdot V_2 cdot cdots cdot V_n rightarrow A$ . Given the evaluations claimed by the players, f selects an outcome, and n payment functions, $p_1, p_2, cdots, p_n$ , where $p_i = V_1 cdot V_2 cdot cdots V_n rightarrow R$ .

The above defines Action and Reward.

Incentive Compatible

For every player $i$ , every $v_1 in V_1$ , $v_2 in V_2$ , $cdots$ , $v_n in V_n$ , and every $v'_i in V_i$ , where $a = f(v_i, v_{-i})$ and $a' = f(v'_i, v_{-i})$ , then

$v_i(a) - p_i(v_i, v_{-i}) geq v_i(a') - p_i(v'_i, v_{-i})$ , then the mechanism is incentive compatible.

Specifically, among those incentive compatible mechanisms, the Vickrey-Clarke-Groves (VCG) mechanism is the mostly used one.

The VCG generally seeks to maximize the social welfare of all players in one game, where the social welfare is calculated as $sum^n_{i=1} v_i$ . So the goal function of VCG is $argmax_{a in A} sum^n_{i=1} v_i$ .

The VCG mechanism and the rule to design VCG mechanisms are defined as follows.

VCG Mechanism

A mechanism, consisting of payment functions $p_1, p_2, cdots, p_n$ and a function $f$ , for a game with outcome set $A$ , is a Vickrey-Clarke-Groves mechanism if $f(v_1, v_2, cdots, v_n) = argmax_{a in A} sum^n_{i=1} v_i(a)$ ( f maximizes the social walfare) for some functions $h_1, h_2, cdots, h_n$ , where $h_i : V_{-i} rightarrow R$ (h_i does not depend on $v_i$ )

$forall v_i in V$ , $p_i(v_i) = h(v_{-i}) - sum_{j neq i} v_j$ .

My understanding

For user $i$ , its reward is depended on others, and not related to its action
But why in the payment function, it deducts other users’ true value?

Clarke Pivot Rule

The choice $h_i(v_{-i}) = max_{b in A} sum_{j neq i} v_i(b)$ is called the Clark pivot payment. Under this rule the payment of player $i$ is

$p_i(v_1, v_2, cdots, v_n) = max_{b} sum_{j neq i} v_i(b) - sum_{j neq i} v_i(a)$ where $a= f(v_1, v_2, cdots, v_n)$ .

My understanding

I didn’t understand it yet.

[Leetcode] Best Time to Buy and Sell Stock II

Posted on December 29, 2015 by admin

Problem

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Analysis

Sum up all possible increase
Time; O(n)
Space; O(1)

Code

Reference

[1] https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/

[Leetcode] Best Time to Buy and Sell Stock III

Posted on December 28, 2015 by admin

Problem

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Analysis

用一个数组pre记录在第i天或之前完成一个transaction的左右收益
用一个数组back记录从第i天或之后开始完成一个transaction的最大收益
则完成两个transactions的最大收益为 max(pre[i], back[i])

Code

Reference
[1] https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/

[Leetcode] Best Time to Buy and Sell Stock

Posted on December 28, 2015 by admin

Problem

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Analysis

遍历数组，记录当前最小值，记录当前最大profit

当前profit = 当前值 – 当前最小值

时间复杂度: O(n)
空间复杂度: O(1)

Code

Reference
[1] https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

Definition

Equilibrium

Unique Equilibrium

Problem

Analysis

Code

Problem

Analysis

Code

Ideas from Security Threat

Ideas from Existing Work

Naming Entities

Name Resolution

Name Resolution in a Flat Name Space

What is a DHT

Structure Naming Systems

Linking and Mounting

Symbolic link

Mounting remote name spaces

Implementing Name Spaces

Iterative vs Recursive Resolution

Recursive

Iterative Example

Attribute-based Naming

Concerns

Popular VM Allocation Policies

Introduction

Model

Definition

Mechanism

Incentive Compatible

VCG Mechanism

Clarke Pivot Rule

Problem

Analysis

Code

Problem

Analysis

Code

Problem

Analysis

Code

Iterative

Example