Narrow Results

Content networks are overlay networks, enabling access to distributed contents on centralized servers or individual computers. Since flooding-based routing scheme features poor scalability, we present a modification, which reduces the total network traffic while retaining the original efficiency. In choosy routing, as we call it, each node, while passing an answer, remembers which neighbor it came from. Subsequently repeated queries about the same content are forwarded only to that neighbor. This way, the network learns effective routes. The simulations on several topology types have shown the expected behavior, with up to three-fold reduction in the overall query traffic.

We present a quantum auction protocol using superpositions to represent bids and distributed search to identify the winner(s). Measuring the final quantum state gives the auction outcome while simultaneously destroying the superposition. Thus, non-winning bids are never revealed. Participants can use entanglement to arrange for correlations among their bids, with the assurance that this entanglement is not observable by others. This protocol is useful for information hiding applications, such as partnership bidding with allocative externality or concerns about revealing bidding preferences. The protocol applies to a variety of auction types, e.g. first or second price, and to auctions involving either a single item or arbitrary bundles of items (i.e. combinatorial auctions). We analyze the game-theoretical behavior of the quantum protocol for the simple case of a sealed-bid quantum, and show how a suitably designed adiabatic search reduces the possibilities for bidders to game the auction. This design illustrates how incentive rather that computational constraints affect quantum algorithm choices.