An exercise in selfish stabilization

ABSTRACT

Stabilizing distributed systems expect all the component processes to run predefined programs that are externally mandated. In Internet scale systems, this is unrealistic, since each process may have selfish interests and motives related to maximizing its own payoff. This article formulates the problem of selfish stabilization to show how competition blends with cooperation in a stabilizing environment.

REFERENCES

• 1: Anish Arora , Mohamed Gouda, Closure and Convergence: A Foundation of Fault-Tolerant Computing, IEEE Transactions on Software Engineering, v.19 n.11, p.1015-1027, November 1993 [doi>10.1109/32.256850]
• 2: Aumann, R. 1959. Acceptable points in general cooperative n-person games. In Contributions to the Theory of Games IV. Annals of Math. Study.
• 3: Hui Cao , Emre Ertin , Vinodkrishnan Kulathumani , Mukundan Sridharan , Anish Arora, Differential games in large-scale sensor-actuator networks, Proceedings of the 5th international conference on Information processing in sensor networks, April 19-21, 2006, Nashville, Tennessee, USA [doi>10.1145/1127777.1127792]
• 4: Cobb, J. A., Gouda, M. G., and Musunuri, R. 2003. A stabilizing solution to the stable path problem. In Self-Stabilizing Systems, S.-T. Huang and T. Herman, Eds. Lecture Notes in Computer Science, vol. 2704. Springer, Berlin, Heidelberg, Germany. 169--183.
• 5: Edsger W. Dijkstra, Self-stabilizing systems in spite of distributed control, Communications of the ACM, v.17 n.11, p.643-644, Nov. 1974 [doi>10.1145/361179.361202]
• 6: Shlomi Dolev, Self-stabilization, MIT Press, Cambridge, MA, 2000
• 7: Dolev, S., Schiller, E., and Spirakis, P. 2006. Game authority: for robust distributed selfish-computer systems. Tech. rep., DELIS. http://delis.upb.de/docs/.
• 8: Timothy G. Griffin , F. Bruce Shepherd , Gordon Wilfong, The stable paths problem and interdomain routing, IEEE/ACM Transactions on Networking (TON), v.10 n.2, April 2002
• 9: Halpern, J. 2000. A computer scientist looks at game theory. In Proceedings of the 1st World Congress of the Game Theory Society (GAMES).
• 10: Hoefer, M. 2006. Non-cooperative tree creation. In Proceedings of the 31st International Symposium on Mathematical Foundations of Computer Science (MFCS), R. Kralovic and P. Urzyczyn, Eds. Lecture Notes in Computer Science, vol. 4162. Springer, Berlin, Germany. 517--527.
• 11: Shing-Tsaan Huang , Nian-Shing Chen, A self-stabilizing algorithm for constructing breadth-first trees, Information Processing Letters, v.41 n.2, p.109-117, Feb. 14, 1992 [doi>10.1016/0020-0190(92)90264-V]
• 12: Idit Keidar , Roie Melamed , Ariel Orda, EquiCast: scalable multicast with selfish users, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146394]
• 13: Mavronicolas, M., Papadopoulou, V. G., Philippou, A., and Spirakis, P. G. 2005. A graph-theoretic network security game. In Proceedings of the 1st International Workshop on Internet and Network Economics (WINE), X. Deng and Y. Ye, Eds. Lecture Notes in Computer Science, vol. 3828. Springer, Berlin, Germany. 969--978.
• 14: Milchtaich, I. 1996. Congestion games with player-specific payoff functions. Games Eco. Behav. 13, 1 (March), 111--124.
• 15: Thomas Moscibroda , Stefan Schmid , Roger Wattenhofer, On the topologies formed by selfish peers, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146403]
• 16: Thomas Moscibroda , Stefan Schmid , Roger Wattenhofer, When selfish meets evil: byzantine players in a virus inoculation game, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146391]
• 17: Nash, J. 1950. Equilibrium points in n-person games. In Proceedings of the National Academy of Sciences USA 36, 48--49.
• 18: Simon, H. 1982. Models of Bounded Rationality: Vols. 1 and 2. MIT Press.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Protocol verification

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.1 Applicative (Functional) Programming
      D.1.3 Concurrent Programming
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging

General Terms:
Algorithms, Design, Theory

Keywords:
Stabilization, convergences, equilibrium, selfishness