Consistent hashing is a technique for distributing data across a network of nodes in a way that minimizes reorganization when nodes join or leave the network. It is extensively applied in modern distributed systems as a fundamental mechanism for routing and data placement. Similarly, distributed storage systems rely on consistent hashing for scalable and fault-tolerant data partitioning. This paper introduces BinomialHash, a consistent hashing algorithm that executes in constant time and requires minimal memory. We provide a detailed explanation of the algorithm, present a pseudocode implementation, and formally establish its strong theoretical guarantees. Finally, we compare its performance against state-of-the-art constant-time consistent hashing algorithms, demonstrating that our solution is both highly competitive and effective, while also validating the theoretical boundaries.

Consistent hashing is used in distributed systems and networking applications to spread data evenly and efficiently across a cluster of nodes. In this paper, we present MementoHash, a novel consistent hashing algorithm that eliminates known limitations of state-of-the-art algorithms while keeping optimal performance and minimal memory usage. We describe the algorithm in detail, provide a pseudo-code implementation, and formally establish its solid theoretical guarantees. To measure the efficacy of MementoHash, we compare its performance, in terms of memory usage and lookup time, to that of state-of-the-art algorithms, namely, AnchorHash, DxHash, and JumpHash. Unlike JumpHash, MementoHash can handle random failures. Moreover, MementoHash does not require fixing the overall capacity of the cluster (as AnchorHash and DxHash do), allowing it to scale indefinitely. The number of removed nodes affects the performance of all the considered algorithms. Therefore, we conduct experiments considering three different scenarios: stable (no removed nodes), one-shot removals (90% of the nodes removed at once), and incremental removals. We report experimental results that averaged a varying number of nodes from ten to one million. Results indicate that our algorithm shows optimal lookup performance and minimal memory usage in its best-case scenario. It behaves better than AnchorHash and DxHash in its average-case scenario and at least as well as those two algorithms in its worst-case scenario.

When a cluster is scaled, a well-known hashing technique called consistent hashing permits only a small number of resources to be remapped. In a variety of settings, including distributed databases, cloud infrastructures, and peer-to-peer networks, it performs key functions as a data router and load balancer. The literature does not offer a full review and comparative assessment of consistent hashing algorithms, despite the fact that research on these algorithms in relation to various usage scenarios has been conducted. Consequently, in a rather neutral setting, this study surveys and empirically compares the most widely used consistent hashing algorithms for distributed databases and cloud infrastructures, published from 1997 to 2021. All algorithms have been implemented in Java and benchmarked on common hardware to perform the comparison. We found Jump, Anchor, and Dx to outmatch the other algorithms on all the considered metrics. The measured values match the asymptotic curves. Although, some asymptotically faster algorithms have been shown to be slower in practice due to the number of memory accesses.

Following a constant rise in the complexity and scale of peer-to-peer networks, researchers have looked at biological phenomena in order to develop self-organized, adaptive, and robust management systems. Our focus is on distributed swarm intelligence mechanisms that mimic the behavior of social insects to solve problems such as overlay management, routing, task allocation, and resource discovery. A central problem in the validation of novel networking solutions is their empirical evaluation under different conditions. Whereas existing network simulation platforms lack specific support for ant-inspired protocols (like transparent agent migration), dedicated frameworks for bio-inspired systems fail to implement accurate network models. To bridge this gap, we introduce a framework with support for bio-inspired techniques and realistic network underlay simulation based on Over Sim. To validate our work, we describe the implementation of several swarm-based protocols and we provide some measurements of the simulation performance.

When comparing digital board games with their traditional counterparts, it becomes clear that certain features such as graphics, mundane task automation or saving and restoring the state of the game have been greatly improved.Nonetheless, the transition to a digital environment leads to a loss of the flexibility that makes traditional board games inherently popular. While modifying aspects of the game is straight forward in traditional board games, achieving such a level of customization in the digital domain requires deep knowledge of and access to the game source code. In this paper we focus on board games and by means of an in-depth online survey we validate our previous observation, namely that enhancements should be made to digital board games by incorporating gaming facets found in the physical environment,e.g. support for flexibility by means of house rules. To this end,we introduce a conceptual model for the design of digital board games, which is supported by a set of visual programming tools to enable game development according to the principles set out by our proposed model. The set of the tools along with the underlying intuitive model comprise the FLEXIBLERULES framework, which enables and facilitates flexible and extensible game design and development.

Much work has been done to exploit the effectiveness and efficiency of job scheduling upon distributed computational--resources. With regard to existing resource topology and administrative constraints, scheduling approaches are designed for different hierarchic layers, for example, scheduling for job queues of local resource management systems (local scheduling), and scheduling for job queues of high level schedulers (also known as meta-schedulers or grid schedulers). Such scheduling approaches mainly focus on optimizing job queues of the hosting nodes, which are interconnected with computational resources directly or indirectly. In the real world (or in a community-based grid), a grid is comprised of nodes with different computing power and scheduling preferences, which in turn, raise a notable opportunity that is to exploit and optimize the process of job sharing between reachable grid nodes via improving the job allocation and efficiency ratio. In our work, we introduce a novel scheduling protocol which dedicates to disseminate scheduling events happened on each involving node to as many candidate nodes as possible. By means of the proposed protocol, scheduling process of each received job consists of several phases with awareness of grid volatility, and dynamic scheduling and rescheduling is allowed as long as the job execution has not started yet. To this end, a set of concerning algorithms and processing steps are described. A prototype of our scheduling approach is being implemented within the SmartGRID project.

Critical to the successful deployment of grid systems is their ability to guarantee efficient meta-scheduling, namely optimal allocation of jobs across a pool of sites with diverse local scheduling policies. The centralized nature of current meta-scheduling solutions is not well suited for the envisioned increasing scale and dynamicity of next-generation grids, the success of which relies on the development of fully distributed, flexible and autonomic systems tailored to very large sets of highly volatile and heterogeneous resources. In this respect, we introduce a fully distributed grid meta-scheduling scheme that effectively addresses the concerns regarding the scalability and adaptability of future grid systems. Our approach employs a lightweight protocol, called A RiA, that is based on peer-to-peer communication between grid nodes, and makes use of dynamic rescheduling to consider and adapt to changes in the availability of resources. Extensive evaluation by means of an in depth simulation study highlighted the effectiveness of the proposed solution in improving the overall performance in terms of job completion time and load-balancing.

Efficient, scalable and robust grid service provisioning is one of the cornerstones of next generation grid systems. In agreement with this vision, we propose a flexible grid service provisioning framework built on a two layer architecture. A lower layer provides membership management and basic communication upon a self-organized peer-to-peer overlay maintained and optimized using a fully distributed bio-inspired algorithm. An upper layer exploits these facilities to deliver high-level grid services such as resource discovery and monitoring. We evaluate the proposed solution on different scenarios and assess its qualities concerning performance, reliability, fault-resilience and network communication efficiency.

This paper describes a distributed algorithm to construct and maintain a peer-to-peer network overlay with bounded diameter. The proposed approach merges a bio-inspired self-organized behavior with a pure peer-to-peer approach, in order to adapt the overlay to underlying changes in the network topology. Ant colonies are used to collect and spread information across all peers, whereas pheromone trails help detecting crashed nodes. Construction of the network favors balanced distribution of links across all peers, so that the resulting topology does not exhibit large hubs. Fault resilience and recovery mechanisms have also been implemented to prevent network partition in the event of node crashes. Validation has been conducted through simulations of different network scenarios.

Network resources management issues in complex and dynamic scenarios require decentralized solutions and adaptive systems to face critical and unattended situations. Bio-inspired techniques such as swarm intelligence algorithms, have proved to be robust and suitable for managing tasks like routing, load-balancing or resource discovery. In this paper we describe Solenopsis, a framework for the development, simulation and deployment of ant-algorithms, which is aimed at supporting network management middlewares. The system provides a modular and scalable environment that can be distributed over a network. Ants are coded using a simple programming language, and are able to migrate across nodes. Two basic load-balancing algorithms are presented and evaluated, as an example of how this tool works and can be used in practice.