Minimum Performance Guarantee (cont…)

For

, the degree of

Therefore, the number of collisions between two nodes using unique and different polynomials is bounded as well.

For more than two nodes, it is necessary to control or know a-priori the maximum degree of the network (network is viewed as a graph G(V,E)):

In order to guarantee unique polynomial assignment:

(1)

In order to guarantee a bounded number of collisions (guarantee):

(2)

(N = number of nodes in the network           = max. degree of the network)