I've been thinking more about the whole "better multiplexing" issue for a bit now, and I suspect that some sort of http://en.wikipedia.org/wiki/Carrier_sense_multiple_access_w... type of solution is ideal for this use case. Because if you think about it, two transmitters at once is not an unrecoverable failure mode, in fact it's easier to handle here than in, say, the original ethernet standard, because with packet-based internet stuff we can do things like changing the data rate on the fly in response to collisions.

Currently the system I'm imagining works as follows: Every T seconds a new packet is initiated, and fancy spanning tree relaying or whatever is used, and eventually everyone has the XOR of all server and client versions of the packet, which happens to be the XOR of whatever various clients happened to include into their packet. Now the additional information for a client who chooses to add that will be the payload plus a checksum value (which must not be homomorphic under the XOR operation). If one client transmits, the checksum passes, and everyone is happy. If multiple clients transmit, they collide, and the checksum does not pass, and each transmitter knows this and waits a random backoff time (number of packets) before trying again. But in addition, a collision is often a signal that the packet rate is too low, so collisions also cause the packet period T to decrease (and lack of messages will cause it to increase, naturally).

So I think the basic "matrix of shared secrets" construct can be extended to allow low-overhead (for values where "low" means "on the order of 3x") communications, because dynamically varying the period between packets and allowing anyone to try transmitting during any packet time will tend to mean that when no one is transmitting bandwidth drops to a very low level (I could easily believe 16-byte idle packets every 5 seconds for something where absolutely low latency isn't a requirement).