More Safety Oracles :)

[naterush]

Issue

• What's wrong?
• How are things currently?
• How should things be?

Proposed Implementation

Fill this out as best you can, and we'll start the discussion to flesh it out.

[seanavery]

Simple Upper Bound

One super simple optimization could be setting an upper bound on the clique size.

• Lets say our graph G has a maxiumum clique of size x
• Each vertex in in the max clique has a degree of x-1
• Simply iterate through the validator nodes and take the node with the highest degree z-1
• Then we know z >= x is the largest possible size for the maximum clique

This could be used in conjunction with the Turan oracle to bound a brute force search for the max clique size. And its a super quick linear lookup.

[seanavery]

Hopeful Heuristic Lower Bound Approach

Turan's lower bound is a great constant time check that could result in a quick safety calculation. We can also implore other hopeful lower bound strategies:

G = (V, E)

Iterate through V and choose the vertex v with the highest degree (most likely candidate to be in the maximum clique)

C = {}

1. Add base case v to K
2. Remove all vertices in V not adjacent to v
3. Choose the next largest degree vertex in V called v' add to C
4. Remove all vertices in V not adjacent to v'
5. If V is empty stop, else go back to 3

The number of vertices in K will be a lower bound on the maximum clique.

This could potentially result in a clique size less than the Turan calculation or give us a much greater find :). This strategy too is liable to sybil attackers who construct a huge "hub and spoke" vertex without a resulting large clique.

(I am finding some great literature on maximum clique finding algorithms. Almost every one, starts by finding lower and upper bounds. This is the lower bound strategy used in http://www.m-hikari.com/ams/ams-2014/ams-1-4-2014/mamatAMS1-4-2014-3.pdf)

[seanavery]

Parallel Computation and Verification

Maximum clique calculation is hard, NP-hard. But luckily it is also NP-Complete so we can verify a correct solution in polynomial time. We can take advantage of the NP dichotomy by allowing anyone to submit a solution and then verify it relatively fast.

This can be combined with the above hopeful lower-bound strategy to allow for a paralleled brute force over the graph space.

[seanavery]

Independent Maximal Cliques and Sharding

One possible sharding strategy. Not sure if it would actually work, but noting here so I do not forget.

• S = [s1, s2, ..] is the global sharded state containing a flat set of shards s
• search for maximal cliques in the graph using Bron–Kerbosch algorithm (which is very efficient in graphs with small number of independent cliques)
• reduce the maximal clique set:

1. If the maximal clique is independent, the clique is safe, reward the validators
2. If the clique is the maximum compared to all other dependent cliques, the maximum clique has safety. Reward the maximum clique. Penalize all other cliques dependent on this maximal clique
3. If the maximal clique is not independent and not the maximum relative to dependent cliques. remove and penalize.

• Iterate through the reduced maximal clique set, check to see if the shard sn exists in S

1. If s does not exist in S, update the state of s to s`
2. If s does not exist in S, append s to the sharded state set

[seanavery]

Pruning Optimizer

Instead of blindly iterating through the graph and searching for the largest weighted clique, we can use the information we get along the way to eliminate parts of the graph that cannot possibly contain the largest clique.

let m be the highest known clique

• we can safely prune away all vertices that contain fewer neighbors than m
• avoid recomputing on vertices in which we already know are in a maximal clique

[naterush]

@vladzamfir mentioned an O(1), or O(n) safety oracle today. Writing a note here as a reminder to ask about this. It isn't totally obvious to me how to do this, with the exception of maintaining some information about messages when receiving it.