Next: Asymptotic efficiency
Up: Efficiency
Previous: Costs for protocol phases
Let us assume we have m=4 auctioneers (so t=1, no single
auctioneer can cheat or violate privacy), and let ,
so each point is 12 bytes. We will estimate the communication costs
(in terms of rounds, messages, and bytes) for two sample auctions. We
will assume that all bids must be verified immediately (this maximizes
the number of messages needed during bid submission), that the leading
digit of the selling price is non-zero (worst-case). Costs will be
counted as the total of sent and received for both bytes and messages.
Example 1: Consider the case with n=1000 bidders, V=1024 possible
prices, and base c=2 bid encoding (so d=10).
- Bid submission. Each bidder sends 4 messages of 480 bytes
each. Each auctioneer receives one of these messages and then sends
120 bytes to each other auctioneer. Total communication for each
auctioneer during submission is in 7000 total
messages.
- Bid resolution. In the first round of the protocol, phase 1 is
unnecessary, so there will be 10 multiplications over 3
communication rounds. The remaining 9 protocol rounds each require
1010 multiplications and 5 communication rounds. Each
multiplication requires 480 bytes of communication between each
pair of auctioneers. Total communication for each auctioneer is
in 288 messages over 48 communication
rounds.
Example 2: Consider the case with n=50 bidders, V=1024 possible
prices, and base c=4 bid encoding (so d=5).
- Bid submission. Each bidder sends 4 messages of 720 bytes
each. Each auctioneer receives one of these messages and then sends
180 bytes to each other auctioneer. Total communication for each
auctioneer during submission is 90K bytes in 350 total
messages.
- Bid resolution. In the first round of the protocol, phase 1 is
unnecessary, so there will be 18 multiplications over 3
communication rounds. The remaining 4 protocol rounds each require
168 multiplications and 5 communication rounds. Each
multiplication requires 480 bytes of communication between each
pair of auctioneers. Total communication for each auctioneer is
in 138 messages over 23 communication
rounds.
Next: Asymptotic efficiency
Up: Efficiency
Previous: Costs for protocol phases
Doug Tygar
Wed Jul 22 10:16:16 EDT 1998