The Problem

In this problem, we will take a break from trying to minimize the runtime of the algorithm and focus on an important resource in distributed computing: the total number of bits communicated over a network by the algorithm.

Given a graph $G=(V,E)$, which is the underlying network topology, we want to compute the intersection of $n=|V|$ sets over the network $G$. More precisely, every node $u\in V$, gets a set $S_u\subseteq [M]$ for some integer $M\ge 1$. (Note that $M$ has nothing to do with the number of edges in $G$.) Further we are given a special node $t\in V$. The goal of this problem is to design an algorithm such that when the algorithm terminates, the node $t$ knows the intersection of all sets: \[\cap_{u\in V} S_u.\] Moreover, we want to design such an algorithm that minimizes the total communication over $G$.

Next, we give more details on the problem above. First, we will assume that any two nodes $u$ and $w$ can communicate directly if and only if $(u,w)\in E$. Further, sending one bit over an edge $e\in E$ incurs a cost of $c_e\ge 0$. ¹ An algorithm given both the graph $G$ and sets $S_u$ for every $u\in V$ has to decide on a series of computations at the nodes and communication over the edges $e\in E$. ² At the start of algorithm, every node $u\in V$ has an array $A_u$ of length $M$ such that \[A_u[i]= \begin{cases} 1 &\text{ if } i\in S_u\\ 0&\text{ otherwise} \end{cases} \] for every $i\in [M]$. When the algorithm terminates node $t$ has an array $B$ of length $M$ such that \[B[i]= \begin{cases} 1&\text{ if } A_u[i]=1 \text{ for every } u\in V\\ 0&\text{otherwise}, \end{cases} \] for every $i\in [M]$.

The communication cost of the algorithm is defined as follows. Let $b_e$ bits be the total number of bits sent by the algorithm on edge $e$ in (for a given input). Then the communication cost (for the input) is $\sum_{e\in E} b_e\cdot c_e$.

The goal of this problem is to solve the set intersection problem with small communication cost. Unlike previous homeworks, we will start with part (b) first:

• Part (b):

  The problem you need to solve

  Design an algorithm whose worst-case communication cost over all inputs over the universe $[M]$ is $O(MST(G)\cdot M)$, where $MST(G)$ is the cost of an MST on $G$ (i.e. it is the sum of costs of all edges in the MST). Note that the algorithm is only provided four things: (1) $G$, (2) $t \in V$, (3) cost of each edge $e$ in $G$, and (4) the arrays $A_u$ for every $u\in V$ as input. You should also assume that $G$ is connected.

  Some clarifications

  Some clarifications on what the algorithm can and cannot do:

  • Your algorithm can use the knowledge of $G$ to build a protocol: i.e. the sequence of bits that should be exchanged over any edge (and when to send those bits).
  • Once the protocol is built, the rest of the computation happens in a distributed manner. In other words any point of time and any node $u$, what bit(s) $u$ sends over an edge $(u,v)\in E$ depends only on $A_u$ and all the bits that $u$ has received till this point of time. (Again what computation to apply to compute these bits to be sent over is determined by the protocol.)
  • At the end of the run of the protocol, the node $t$ has to output the final answer $B$ only based on $A_t$ and all the bits it has received from its neighbors over the entire run of the protocol.

• Part (a): You will argue part (b) for two special cases of $G$:
  1. Show that when $G$ is a complete graph on $n$ vertices (i.e. $G=([n],E)$ where $E=\{(i,j)|i<j\in [n]\}$) and $c_e=1$ for every $e\in E$, there is a protocol whose worst-case communication cost over all inputs over the universe $[M]$ is $O(n\cdot M)$.

     Example (Continued)

     Continuing our specific example consider the case when $c_{(u,w)}=c_{(u,t)}=c_{w,t)}=1$. In this case note that $MST(G)=2$. Here is a protocol that works for this special case. Node $u$ sends $A_u=[1,1,0,0,1]$ to $t$ over the edge $(u,t)$ and node $w$ sends $A_w =[0,1,0,1,0]$ to $t$ over the edge $(w,t)$. Note that in this case the algorithm sends $b_{(u,t)}=5$ bits over the edge $(u,t)$ and the algorithm sends $b_{(w,t)}=5$ bits over the edge $(w,t)$ for a total of $2\cdot 5=10$ bits. Now note that node $t$ has all of $A_u,A_w$ and $A_t$ and hence can compute $B$.

     Note 1

     The algorithm above is not a true distributed algorithm: this is because the algorithm can use the knowledge of the entire $G$. In a true distributed algorithm, the algorithm can only use ``local" information about $G$ (i.e. a node $u$ only knows about its neighbors) but we'll go with (easier) centralized algorithms in this problem.)

     In the protocol above, we completely ignored the time needed by the nodes to do their computation and as the problem asks, we only concentrated on the communication cost of the algorithm.

  2. Show that when $G$ is a star graph on $n$ vertices with $t$ as its center (i.e. $G=([n],E)$ where $E=\{(t,j)|j\neq t\in [n]\}$) and $c_e=1$ for every $e\in E$, there is a protocol whose worst-case communication cost over all inputs over the universe $[M]$ is $O(n\cdot M)$.

  Note

  We would like to point out two things:

  1. Since for both the complete graph and star graph above, we have $MST(G)=n-1$, the bound of $O(n\cdot M)$ in both sub-parts is indeed $O(MST(G)\cdot M)$ for the special case of $G$.
  2. Note that your protocols for part (a) above can use the special structure of the complete graph while your algorithm for part (b) should work for any network topology $G$.

The Problem

Consider the following problem. Given a Directed Acyclic Graph (or DAG) $G$ with arbitrary weights on the edges (i.e. they can be positive or negative) with $n$ vertices and $m$ edges, and given two vertices $s$ and $t$, compute the shortest path from $s$ to $t$ in $G$. (You can assume that $G$ is given to you in the adjacency list format.)

Here are the two parts of the problem:

• Part (a): Fix any topological ordering of $G$. Then consider the new graph $G'$ that one obtains by removing all vertices from $G$ that come before $s$ in the chosen topological ordering. (Note that when you remove a vertex, you also remove all of its incident edges.) Then argue that any $s-t$ path in $G$ is also an $s-t$ path in $G'$.
• Part (b): Present an $O(m+n)$ algorithm to compute the shortest path from $s$ to $t$ in $G$.

The Problem

In this problem, we will explore node-weighted graphs.

We are given a starting node $s$ and an ending node $e$, for some undirected graph $G$ with $n$ nodes. Further, each node $u$ has its own weight, $w_u$ (0 <= wu <= 50). The graph is formatted as an adjacency list, with the leading number being the node weight, meaning that for each node, $u$, we can access all of $u$'s neighbors, as well as $u$'s weight. The goal is to output the array of nodes in a shortest path from $s$ to $e$. (The weight of a path $P=(u_1,\dots,u_{\ell})$ is $\sum_{i=1}^{\ell} w_{u_i}$ and the shortest path is the one with the minimum weight.)

Input

The input file is given with the first two lines being the start node and the end node, and the remainder of the file is an adjacency list with node weights for graph $G$ (we assume that the set of vertices is $\{0,1,\dots,n-1\}$). The adjacency list assumes that the current node is the index of the line under consideration. For instance the third line of the input file has the list of all nodes adjacent to node 0 (the first two being the start and end nodes) and so on.

                s   <- Starting node (some node between u0 and un-1).
                e   <- Ending node (some node between u0 and un-1).
            	w0 u1 u4 u6	<- All nodes that share edges with u0
            	w1 u3 uu		<- All nodes that share edges with u1
		w2 u0		<- All nodes that share edges with u2
		.
		.
		.
		wn-1 u0 u4 u2 u7 	<- All nodes that share edges with un-1
	    

Output

The output should be a list/ArrayList/vector (depending on your language of choice) where every 2 adjacent nodes have an edge between them. The 1st node in the output should be startNode and the last node in the output should be endNode.

For example, if startNode was 2 and endNode was 7, and the minimum path between them is 2-9-8-4-7 then you should output [2, 9, 8, 4, 7]. If there is no path between the start and end nodes, output an empty output.

            [s, n0 n1 n2... nm, e]   		<- Each entry is a node on the shortest path between 's' and 'e'