Name
Abstract | ||
|---|---|---|
The resource discovery problem arises in the context of peer to peer (P2P) networks, where at any point of time a peer may be placed at or removed from any location over a general purpose network (e.g., an Internet site). A vertex (peer) can communicate with another vertex directly if and only if it knows a certain routing information to that other vertex. Hence, a critical task is for the peers to convey this routing information to each other.The problem was formalized by Harchol-Balter, Leighton and Lewin [13]. The routing information needed for a vertex to reach another peer is that peer's identifier (e.g., IP address).A logical directed edge represents the fact that the peer at the tail of the edge knows the IP address of the one at its head. A number of algorithms were developed in [13] for this problem in the model of a synchronous network over a weakly connected directed graph. The best of these algorithms was randomized. Subsequently, a deterministic algorithm for the problem on synchronous networks with improved complexity was presented in [15].The current paper extends the deterministic algorithm of [15] to the environment of asynchronous networks, maintaining similar complexities (translated to the asynchronous model). These are lower than the complexities that would be needed to synchronize the system. The main technical difficulty in a directed, weakly connected system is to ensure thatvertices take consistent steps, even if their knowledge about each other is not symmetric, and even if there is no timeout mechanism (which does exist in synchronous systems) to assist in that. (In particular, as opposed to the case in synchronous systems, here an algorithm cannot first transforming every directed edge to be bidirectional and second, apply an algorithm for bidirectional graph.) Thus our result takes another step towards representing the actual setting in a realistic manner. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.comnet.2006.02.005 | Computer Networks: The International Journal of Computer and Telecommunications Networking |
Keywords | DocType | Volume |
bidirectional graph,asynchronous network,time unit,synchronous algorithm,deterministic algorithm,synchronous network,resource discovery problem,asynchronous resource discovery,asynchronous networks.,p2p,routing information,certain routing information,distributed algorithms,synchronous system,peer-to-peer network,asynchronous model,ip address,peer networks,message delivery time,topol- ogy knowledge loss,topology changes,peer to peer,randomized algorithms,directed graph,internet,complexity,computational complexity,directed graphs,routing,web server,intelligent networks,tail,vertex | Journal | 51 |
Issue | ISSN | ISBN |
1 | 1060-9857 | 0-7695-1659-9 |
Citations | PageRank | References |
13 | 0.85 | 12 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shay Kutten | 1 | 2118 | 226.75 |
| David Peleg | 2 | 6662 | 824.19 |