SELFISH STABILIZATION OF SHORTEST PATH TREE FOR TWO- COLORED GRAPHS

摘要

In modern day stabilizing distributed systems, each process/node or each administrative domain may have selfish motives to optimize its payoff. While maximizing/minimizing own payoffs, the nodes or the domains do not require to give up their stabilization property. Optimizing individual pay offs without sacrificing the stabilization property is a relatively new trend and this characteristic of the system is termed as selfish stabilization The focus of this paper is to investigate the problem of finding a stable shortest path tree for two-colored graphs, where the colors represent different types of processes or domains. In a shortest path tree, for every node, its path along the tree has the minimum possible distance of any path to the root. In this paper we study the impact of selfishness on stabilization, provide examples to demonstrate the effects of different types of schedulers, and explore how the stabilization time is affected by parameter changes.