An online algorithm for local address assignment supporting P2P distributed computing

In this paper, we consider a special type of Peer to Peer (P2P) networks that all nodes have only a small number of reusable local addresses and there is no global unique address for each node. Use of local address avoids the problem of managing global unique address for large networks. There are two constraints on the local address assignment of distributed networks. One is that a node cannot have the same address as its neighbors and all neighbors of a node should have distinguish addresses. The other is that when a node is not assigned an address, it is in a "dormant" state and cannot establish communication with the surrounding nodes. Based on the above two assumptions, we propose an online algorithm for local address assignment supporting P2P distributed computing. Compared with the traditional off-line algorithm, it can dynamically assign addresses to new nodes and handle conflicts in existing online distributed networks. Analogous to the 2nd-order graph coloring problem, we proved that at most Δ
²
+1 local addresses are needed for P2P distributed computing.