• Goal: Increase efficiency with more threads
• Binary Fork-Join Model
  • Assume each processor shares memory
  • Threads may perform a fork operation
  • Later performs a join operation for sync

• Represent algorithm's computation as a DAG
  • Each node represents tasks, each edge is a dependency
• Span: Longest path within the graph
• Work: Total number of nodes in the graph

1. Parallel Peeling IBLT in One/Two Rounds
   1. IBLT
   2. Peeling Analysis
2. Dynamic Accountable Storage
   1. Accountable Storage Protocol
   2. IBLT Tree
3. Joinable B-Tree
   1. Fork-Join I/O Model
   2. Multi-way Join

• Applications:
  • Set Reconciliation of Distributed Computing
  • Block Chain Reconciliation
  • Network Reconciliation

• Will be focusing on insertion and peeling
  • Find difference operation simulated by pure insertions
• Peeling: Listing all elements from the IBLT destructively

• Analysis Jiang, Mitzenmacher, and Thaler
• rounds with hash functions
• Probability and round analysis relies on a constant

• hash functions
• size of IBLT
  • Partition IBLT into subtables
  • Prevents same element collision

Theorem 1

For a table of cells using hash functions, where is a constant, an IBLT peels in one round with probability at least where

• An element is unpeelable if all locations have collisions
  • Collisions occur in a subtable with probability at most
  • Across all subtables:
• Union bound across all elements gives

Theorem 2

For a table of cells using hash functions, where is a constant, an IBLT peels in two rounds with probability at least

• Prior proof analyzed the probability of a cell being single

• with probability
• Probability of not being peeled in round =
• Probability of not peeled in round from subtable =
• Dependencies on other subtables complicates the analysis

• Round: 1, 2
• Round: 3, 4
• Round: 5

Theorem 3

For a table of cells using hash functions, where is a positive integer constant and is a constant, an IBLT peels in rounds with probability at least

• Entrust our data to cloud storage providers
  • Amazon S3 advertises losing of one out of 100 billion objects per year
  • S3 currently stores hundreds of trillions of data
  • When data is lost or corrupted, we want a method of recovery

• Ateniese et al. developed a static protocol
• Recover data with IBLT, charge for lost data
• Homomorphic Tags
  • Ties blocks of data to tags
  • Users may verify server has all data they claim to have
• Segment Tree
  • Quickly generate IBLT from server's stored data

• Client data is often dynamic in the real world
• Model assumes a malicious server
  • Unrealistic since users are already entrusting the service with their data
  • Simple, unavoidable method of thwarting the protocol

• Static Accountable Storage charges server based on recovered data
  • If data unrecoverable, assume the worst and charge for everything lost
• Malicious server avoids significant amounts of responsibility
  • Generate IBLT at the start
  • Server recovers any lost data
  • Server would only be punished when data is unrecoverable

• IBLT Tree: BST Dynamic "Segment Tree"
• Bucket leaves, saves significant amount of space
• Let be the size of the bucket per leaf node
  • Leaf nodes contain an IBLT of elements
  • Internal nodes contain the union of their children

• Space:
• Time cost depends on BST implementation
• Protected Cartesian Tree as implementation
  • Initialize Tree:
  • Insertion/Deletion:
  • Construct IBLT:

• Modern computers are typically bottlenecked by memory accesses
  • Captured sequentially by the External Memory Model
  • PRAM has the parallel equivalent, PEM
  • Binary Fork Join model does not

• Each fork and join spawns and syncs at most threads
• Each thread may access a block of data in a single memory access

• Join-based framework
  • Supports efficient set operations
  • Core methods are Join and Split

• Multi-way cache efficient self-balancing tree
• Each node in the tree contains keys and children
• Focusing on B-Way Join
  • Extended to the Multi-Way Join

• General steps for the algorithm
  • Grouping
  • Recurse and Subtree Replace
  • Concatenate and Rebalance

Theorem 4

Let be a set of B-trees, with the largest tree height and the shortest tree height , and be a set of separator keys, where . The join operation can be performed in I/O span and I/O work.

• Leads to a span-inefficient solution
• Union with above primitive leads to I/O Span

• Grouping
• Fuse within Groups
• Divide Large Nodes
• Divide Smaller Nodes
• Concatenate and Rebalance

• Recall the grouping of tall trees
  • Do not recurse into subgroups
  • Fuse keys and nodes at their heights directly

• Maintain list of pointers along the left and right spines
• Finding the node a root merges with takes I/O span

• Suppose a node contains keys
  • When create nodes
  • Push keys to parent node
• After, each node contains at most keys
  • Each subsequent dividing of nodes will push up at most 1 key

Theorem 5

We can join B-trees and keys together in parallel with I/O span and I/O work, where is in the Fork-Join I/O model.

Theorem 6

We can split a B-tree by keys in parallel with I/O span and I/O work, where is in the Fork-Join I/O Model.

• Divide each tree into sections
  • Use the Multi-Split operation
• Perform a union on each pair of subtrees
• Use Multi-Join to combine all elements in the tree
  • Minor modifications may be made to Multi-Join to get Intersection and Difference operations

Theorem 7

Given two B-trees with sizes and , there exists a parallel algorithm that returns a new B-tree containing the union, intersection, and set difference of the two input trees in and I/O work, I/O span, where is the block size.

• Turning to
• Removing factor entirely
• Apply algorithm to adaptive sorting settings
• Use Fork-Join I/O model on other algorithms