Last active
September 29, 2015 21:09
-
-
Save vschiavoni/b4f1f1820e7ee309cf78 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
\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} |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
\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