An issue in making computing potently diffuse throughout a domain is the need to come up with an efficient, many-to-many dissemination protocol among a group of n devices that communicate using omni-directional wireless transmission mechanisms (for example, 802.11b). Such a protocol could be a basis for a network-level solution (middleware). Previous solutions can be grouped into two categories: deterministic (absolute guarantee of delivery) and best effort (delivery with a high probability).

The paper presents a new, deterministically reliable protocol with no imposed routing structure, called Scribble. A minimal aliveness property is key to the design measures to ensure desired coverage, namely, that enough devices have received a message m. Essentially, this property is that at least one subgroup of n devices, which contains the initiating device for a message m to be disseminated to k other devices (1 < k <= n), and which contains at least k - 1 other devices, must not suffer a permanent partition (be separated from the rest of the entire group). The design of the protocol also includes identification of responsible nodes, starting with the initiating device, for dissemination of the message.

The performance of the protocol is compared, using simulation, to a best effort multicast routing protocol and an on-demand multicast routing protocol (ODMRP) in various network densities. The comparison is made by percentage success rate (PSR), always 100 percent for Scribble, and transmission overhead.

An open question is making Scribble fault tolerant. Most of the details of the minimal aliveness property are included in a technical report not included with this paper.