It was a struggle writing this review--not because the paper was difficult to comprehend, but because it was so succinct. In fact, it would be hard to convey the information presented in fewer words. As such, my summary risks missing key points. Nonetheless, here it is.
The problem is to count the number of nodes by bitwise ORing that the message received from each node in a manner that is tolerant of message duplicates. The context is a distributed network of sensors where the total number of sensor nodes is unknown. I would have just had each node send a unique identifier (along the lines of a network media access control (MAC) address) and counted the unique source addresses. But then that would be solving a different problem.
In 1985, a paper by Flajolet and Martin [1] presented an ingenious solution to the problem by drawing a uniform random number at each node and transmitting a bit string of zeros with only the least significant nonzero bit from the random number present. Given the bitwise OR of these bit strings, the number of nodes can be estimated as two to the power of the length of the maximal string of trailing 1s divided by 0.775.
In this paper, Preparata improves on the standard error of the above estimate fivefold by sending a Bernoulli random string with each bit having a set probability 2J of being 1. The estimate of the number of nodes is then computed from the number of 1s in the bitwise OR. To get a minimal variance of estimate, the value of J is dependent on the number of nodes. As such, the author recommends running the original algorithm in [1] to compute a good estimate for J, which is then transmitted to the nodes.
