Distributed Routing of Ads and Bids through Random Walks in the IDOS System
✍ Scribed by Yosi Ben-Asher
- Publisher
- Elsevier Science
- Year
- 2001
- Tongue
- English
- Weight
- 220 KB
- Volume
- 61
- Category
- Article
- ISSN
- 0743-7315
No coin nor oath required. For personal study only.
✦ Synopsis
We propose a novel highly distributed system called IDOS (Internet Distributed Objects System) for BuyÂSell interactions on the Internet. In IDOS there is no main or single site that handles user interactions. Instead, each new user joins'' a dynamic graph of users that are currently interested in a specific type of BuyÂSell interaction. The objects for the BuyÂSell interactions are moved between the nodes (users) of the dynamic graph. The BuyÂSell interactions are therefore realized by updating the objects whenever they pass through the current node. This should solve the communication bottleneck caused by the common use of central servers for interactions on the Internet. It does, however, pose a distributed routing problem where messages sent by the users must be distributed between all the interested'' users that are currently connected to the graph. The proposed routing algorithm should overcome the dynamic changes that occur in the graph's topology because some of the users leave the graph while others join it. The proposed solution is to use random walks to distribute the messages, so that the ever-changing topology of the dynamic graph can be overlooked. Consequently, there is no notion of addresses in the system; each user knows only how to communicate with her neighbors. The user must wait until the desired object reaches its node. This simplifies the communication layer, since the centralized client server TCPÂIP infrastructure can be replaced by a point-to-point communication system. We use a system of multiple random ``postmen'' to overcome the potential communications delay caused by the theoretical large cover-time required by random-walks in graphs. Experimental results of the system as well as how it can be employed to realize public auctions are discussed.