Distributed Computing Building Blocks for Rational Agents

Following [4] we extend and generalize the game-theoretic model of distributed computing, identifying different utility functions that encompass different potential preferences of players in a distributed system. A good distributed algorithm in the game-theoretic context is one that prohibits the agents (processors with interests) from de-viating from the protocol; any deviation would result in the agent losing, i.e., reducing its utility at the end of the algorithm. We dis-tinguish between different utility functions in the context of dis-tributed algorithms, e.g., utilities based on communication prefer-ence, solution preference, and output preference. Given these pref-erences we construct two basic building blocks for game theoretic distributed algorithms, a wake-up building block resilient to any preference and in particular to the communication preference (to which previous wake-up solutions were not resilient), and a knowl-edge sharing building block that is resilient to any and in partic-ular to solution and output preferences. Using the building blocks we present several new algorithms for consensus, and renaming as well as a modular presentation of the leader election algorithm of [4]