63 lines
2.1 KiB
Markdown
63 lines
2.1 KiB
Markdown
# CSE5313 Computer Vision (Lecture 16: Exam Review)
|
|
|
|
## Exam Review
|
|
|
|
### Information flow graph
|
|
|
|
Parameters:
|
|
|
|
- $n$ is the number of nodes in the initial system (before any node leaves/crashes).
|
|
- $k$ is the number of nodes required to reconstruct the file $k$.
|
|
- $d$ is the number of nodes required to repair a failed node.
|
|
- $\alpha$ is the storage at each node.
|
|
- $\beta$ is the edge capacity **for repair**.
|
|
- $B$ is the file size.
|
|
|
|
#### Graph construction
|
|
|
|
Source: System admin.
|
|
|
|
Sink: Data collector.
|
|
|
|
Nodes: Storage servers.
|
|
|
|
Edges: Represents transmission of information. (Number of $\mathbb{F}_q$ elements is weight.)
|
|
|
|
Main observation:
|
|
|
|
- $k$ elements (number of servers required to reconstruct the file) The message size is $B$. from $\mathbb{F}_q$ must "flow" from the source (system admin) to the sink (data collector).
|
|
- Any cut $(U,\overline{U})$ which separates source from sink must have capacity at least $k$.
|
|
|
|
### Bounds for local recoverable codes
|
|
|
|
#### Turan's Lemma
|
|
|
|
Let $G$ be a graph with $n$ vertices. Then there exists an induced directed acyclic subgraph (DAG) of $G$ on at least $\frac{n}{1+\operatorname{avg}_i(d^{out}_i)}$ nodes, where $d^{out}_i$ is the out-degree of vertex $i$.
|
|
|
|
#### Bound 2
|
|
|
|
Consider the induced acyclic graph $G_U$ on $U$ nodes.
|
|
|
|
By the definition of $r$-locally recoverable code, each leaf node in $G_U$ must be determined by other nodes in $G\setminus G_U$, so we can safely remove all leaf nodes in $G_U$ and the remaining graph is still a DAG.
|
|
|
|
Let $N\subseteq [n]\setminus U$ be the set of neighbors of $U$ in $G$.
|
|
|
|
$|N|\leq r|U|\leq k-1$.
|
|
|
|
Complete $n$ to be of the size $k-1$ by adding elements not in $U$.
|
|
|
|
$|C_N|\leq q^{k-1}$
|
|
|
|
Also $|N\cup U'|=k-1+\lfloor\frac{k-1}{r}\rfloor$
|
|
|
|
All nodes in $G_U$ can be recovered from nodes in $N$.
|
|
|
|
So $|C_{N\cup U'}|=|C_N|\leq q^{k-1}$.
|
|
|
|
Therefore, $\max\{|I|:C_I<q^k,I\subseteq [n]\}\geq |N\cup U'|=k-1+\lfloor\frac{k-1}{r}\rfloor$.
|
|
|
|
Using reduction lemma, we have $d= n-\max\{|I|:C_I<q^k,I\subseteq [n]\}\leq n-k-1-\lfloor\frac{k-1}{r}\rfloor+2=n-k-\lceil\frac{k}{r}\rceil +2$.
|
|
|
|
### Reed-Solomon code
|
|
|