Is there an equilibrium for distributed consensus when all agents except one collude to steer the decision value towards their preference? If an equilibrium exists, then an n-1 size coalition cannot do better by deviating from the algorithm, even if it prefers a different decision value. We show that an equilibrium exists under this condition only if the number of agents in the network is odd and the decision is binary (among two possible input values). That is, in this framework we provide a separation between binary and multi-valued consensus. Moreover, the input and output distribution must be uniform, regardless of the communication model (synchronous or asynchronous). Furthermore, we define a new problem - Resilient Input Sharing (RIS), and use it to find an iff condition for the (n-1)-resilient equilibrium for deterministic binary consensus, essentially showing that an equilibrium for deterministic consensus is equivalent to each agent learning all the other inputs in some strong sense. Finally, we note that (n-2)-resilient equilibrium for binary consensus is possible for any n. The case of (n-2)-resilient equilibrium for multi-valued consensus is left open.

Until now, distributed algorithms for rational agents have assumed a-priori knowledge of $n$, the size of the network. This assumption is challenged here by proving how much a-priori knowledge is necessary for equilibrium in different distributed computing problems. Duplication - pretending to be more than one agent - is the main tool used by agents to deviate and increase their utility when not enough knowledge about $n$ is given. The a-priori knowledge of $n$ is formalized as a Bayesian setting where at the beginning of the algorithm agents only know a prior $σ$, a distribution from which they know $n$ originates. We begin by providing new algorithms for the Knowledge Sharing and Coloring problems when $n$ is a-priori known to all agents. We then prove that when agents have no a-priori knowledge of $n$, i.e., the support for $σ$ is infinite, equilibrium is impossible for the Knowledge Sharing problem. Finally, we consider priors with finite support and find bounds on the necessary interval $[α,β]$ that contains the support of $σ$, i.e., $α\leq n \leq β$, for which we have an equilibrium. When possible, we extend these bounds to hold for any possible protocol.

Modern big data processing platforms employ huge in-memory key-value (KV) maps. Their applications simultaneously drive high-rate data ingestion and large-scale analytics. These two scenarios expect KV-map implementations that scale well with both real-time updates and large atomic scans triggered by range queries.

Modern big data processing platforms employ huge in-memory key-value (KV-) maps. Their applications simultaneously drive high-rate data ingestion and large-scale analytics. These two scenarios expect KV-map implementations that scale well with both real-time updates and massive atomic scans triggered by range queries. However, today's state-of-the art concurrent KV-maps fall short of satisfying these requirements -- they either provide only limited or non-atomic scans, or severely hamper updates when scans are ongoing. We present KiWi, the first atomic KV-map to efficiently support simultaneous massive data retrieval and real-time access. The key to achieving this is treating scans as first class citizens, whereas most existing concurrent KV-maps do not provide atomic scans, and some others add them to existing maps without rethinking the design anew.

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 deviating from the protocol; any deviation would result in the agent losing, i.e., reducing its utility at the end of the algorithm. We distinguish between different utility functions in the context of distributed algorithms, e.g., utilities based on communication preference, solution preference, and output preference. Given these preferences 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 knowledge sharing building block that is resilient to any and in particular 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].