A High-Throughput Secure Reliable Multicast Protocol

\[ M = \left< p, m, \left\{ B \right\}_{p} \right> \]

• \(p\) is the process identifier
• \(m\) is the message
• \(B\) is the set of message digests

\(seq(m)\) is the sequence number in \(m\). \(sender(M) = p\) \(seq(M) = seq(m)\) \(payload(M) = m\)

• Local Variables:
  • \(B2Prev \leftarrow \{\}\)
  • \(delivered \leftarrow \{\}\)
  • \(direct \leftarrow \{\}\)
  • \(c_{i} \leftarrow 0\) for \(i \in [n]\)
  • Graph \(G\)
• Events:
  • Input: \(\)
  • Internal: \(\)
  • Internal: \(\)
  • Internal: \(\)
  • Output: \(\)
• Conflict(M,M'):
  • If \(sender(M)=sender(M')\) and \(seq(M)=seq(M')\):
    • return \(payload(M) = payload(M')\)
  • return False
• Shadow(h, G):
  • If \(h \in delievered\):
    • Return false
  • If \(h \in direct\):
    • Return false
  • Return \(h \in G.V\)
• Candidate(M, G):
  • If \(M \not\in direct\):
    • Return false
  • For every \((h,h') \in G.E\):
    • If \(h' \not\in delivered\):
      • Return false
  • Return true
• Upon \(\):
  • For every \(h' \in G.V\):
    • If \(Shadow(h) = false\):
      • continue
    • For every \(h \in B_{1}\cup B_{2}\):
      • If \(h \rightarrow* h'\):
        • Return
  • \(B2Prev \leftarrow B2Prev \cup B_{2}\)
  • \(sent \leftarrow sent \cup B_{1}\cup B_{2}\)
  • Multicast \(\)
  • Schedule timeout \(\)
• Upon \(M = \) from \(r\):
  • If \(r=q\):
    • For every \(h' \in delivered\):
      • If \(Conflict(h, h') = true\):
        • return
    • For every \(h' \in direct\):
      • If \(Conflict(h,h') = true\):
        • return
    • \(direct \leftarrow direct \cup \{ h \}\)
  • \(G.V \leftarrow G.V \cup \{h\}\)
  • For \(h' \in B_{1} \cup B_{2}\):
    • \(G.V \leftarrow G.V \cup \{h'\}\)
    • \(G.E \leftarrow G.E \cup (h, h')\)
• Upon \(M\) from \(p_j\) such that \(seq(M)=c_{j}+1\), \(|DSet(M) = (n+t)/2+1|\) and \(Candidate(M, G) = true\):
  • trigger \(\)
  • \(c_{j} \leftarrow c_{j}+1\)
• Upon \(\):
  • For every \(M \in delivered\):
    • Let \(unknown\) be the set of servers that have not acknowledged delivering \(M\)
    • Let \(DSet(M)\) be the delivered set of \(M\)
    • Send \((M, DSet(M))\) to all servers in \(unknown\)
  • Reset timer
• Upon \(M\):
  • \(conflicted \leftarrow false\)
  • \(depends \leftarrow false\)
  • For every \(M'\):
    • If \(Conflict(M,M') = true\) and \(M'\) is stable:
      • \(conflicted \leftarrow true\)
  • For every \(M'\) such that \(h\rightarrow h'\):
    • If \(M'\) is not stable:
      • \(depends \leftarrow true\)
  • If \(depends = false\) and \(conflicted = true\):
    • Discard \(M\) and edges from \(G\)
• Upon \(\):
  • \(B_{2}\leftarrow \{\}\)
  • For every \(h \in G.V\):
    • \(cand \leftarrow true\)
    • For every \(h' \in direct\):
      • If \((h\rightarrow h')\):
        • \(cand \leftarrow false\)
    • If \(cand = false\):
      • continue
    • For every \((h\rightarrow* h')\):
      • If \(h' \not\in direct\) and \(h' \not\in delivered\):
        • \(cand \leftarrow false\)
    • If \(h \in B2Prev\):
      • \(cand \leftarrow false\)
    • If \(cand = true\):
      • \(B_{2} \leftarrow B_{2} \cup \{h\}\)
  • For every \(M = \) such that \(Candidate(M,G) = true\):
    • \(cand \leftarrow false\)
    • If \(M' \in sent\) and \(h'\rightarrow* h\):
      • \(cand \leftarrow true\)
    • If \(cand = true\) and \(M \not\in delivered\) and \(h \not\in B2Prev\):
      • \(B_{2} \leftarrow B_{2} \cup \{h\}\)
  • trigger \(\)
  • Reset timer
• Upon \(\):
  • trigger \(\)