Skip to content

Instantly share code, notes, and snippets.

@vschiavoni
Last active September 29, 2015 21:09
Show Gist options
  • Save vschiavoni/b4f1f1820e7ee309cf78 to your computer and use it in GitHub Desktop.
Save vschiavoni/b4f1f1820e7ee309cf78 to your computer and use it in GitHub Desktop.
\begin{algorithm}[t]
\caption{
\label{alg:topc}
\SYS at process $i$
}
\variables{}{
$\candidates_i$ \tcp*{the candidates}
$\LT_i$ \tcp*{local top-$k$}
$\GT_i$ \tcp*{global top-$k$}
$\delta$ \tcp*{update period}
}
\update{}{
\upon{\textup{\textbf{receive}} $\langle \flagUpdate, C \rangle$ from $j$}{
$\candidates_i[j] \leftarrow C$ \labline{topc:1} \\
\ForEach{$(x,\any) \in C$}{
$\GT_i \assign \GT_i \setminus \{(x,\any)\}$ \labline{topc:2} \\
$\Omega \assign \sum_{(x,\omega) \in \candidates_i} \omega$ \labline{topc:3} \\
$\GT_i \assign \GT_i \cup \{(x,\Omega)\}$ \labline{topc:4}
}
$\GTi \assign \{\GTi[0], \ldots, \GTi[l-1]\}$ \labline{topc:5} \tcp*{keep top-$k$ items}
}
}
\disseminate{}{
\textbf{let} $(\any,\Gamma) = \GT_i[k-1]$ \labline{topc:6} \tcp*{lowest score in top-$k$}
$l \assign k$ \labline{topc:7} \\
\While{$l < \cardinalOf{\LT_i}$}{ \labline{topc:8}
\textbf{let} $(x,\omega) = \LT_i[l]$ \labline{topc:9} \\
\If{$\omega \times N \ge \Gamma$}{ \labline{topc:11}
$l \assign l + 1$ \labline{topc:12} \tcp*{candidacy test passed}
}\Else{
\textbf{break} \labline{topc:13}
}
}
$C \assign \emptySet$ \labline{topc:14} %\tcp*{the top-$l$ items are candidates}
$n \assign 0$ \labline{topc:15} \\
\While{ $n < l$}{ \labline{topc:16}
$C \assign C \cup \LT_i[n]$ \labline{topc:17} \\
$n \assign n + 1$ \labline{topc:18} \\
}
\ForEach{$(x,\any) \in \candidates_i$} { \labline{topc:19}
\If{$(x,\any) \notin C \wedge (x,\omega) \in \LT_i$ }{
$C \assign C \cup \{(x,\omega)\}$ \labline{topc:20}
}
}
\broadcast $\langle \flagUpdate,C \rangle$ to all sites \labline{topc:21} \\
}
\end{algorithm}
\begin{figure}[!htpb]
\begin{lstlisting}[frame={tblr},numbers=none]
every shuffling_period units do
target = select_gossip_destination(view)
if (target is public
or next_RVP(target) == target) then
send langleRequest,view,self,targetrangle to target
elif ((target is SYM and self is PRC)
or self is SYM) then
// Use relaying
send langleRequest,view,self,targetrangle
to next_RVP(target)
else
// Hole punching
send langleOpen_Hole,self,targetrangle to next_RVP(target)
if self is not public then
send langlePingrangle to target
decrease_routing_table_ttls()
on receive langleRequest,view_s,src,destrangle from p do
update_next_RVP(p,p,HOLE_TIMEOUT)
if dest != self then
// Forwarding
send langleRequest,view_s,src,destrangle to next_RVP(dest)
elif (src is SYM and self /*@$\neq$@*/ public)
or (self is SYM and src != public) then
// Use relaying
send langleResponse,view,srcrangle to next_RVP(src)
else
send langleResponse,view,srcrangle to src
view = merge_and_truncate(view,view_s)
update_routing_table(view)
on receive langleResponse,view_t,destrangle from p do
update_next_RVP(p,p,HOLE_TIMEOUT)
if dest != self then
// Forwarding
send langleResponse,view,destrangle to next_RVP(dest)
else
view = merge_and_truncate(view,view_t)
update_routing_table(view)
on receive langleOpen_Hole,src,destrangle from p do
update_next_RVP(p,p,HOLE_TIMEOUT)
if dest == self then
send langlePongrangle to src
else
send langleOpen_Hole,src,destrangle to next_RVP(dest)
on receive langlePingrangle from p do
update_next_RVP(p,p,HOLE_TIMEOUT)
send langlePongrangle to src
on receive langlepongrangle from p do
update_next_RVP(p,p,HOLE_TIMEOUT)
send langleRequest,view,self,prangle to p
\end{lstlisting}
\caption{The {\nyl} protocol.}
\label{fig:nylon_code}
\end{figure}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment