Summary Achieving efficient many‐to‐many communication on a given network topology is a challenging task when many data streams from different sources have to be scattered concurrently to many destinations with low variance in arrival times. In such scenarios, it is critical to saturate but not to congest the bisectional bandwidth of the network topology in order to achieve a good aggregate throughput. When there are many concurrent point‐to‐point connections, the communication pattern needs to be dynamically scheduled in a fine‐grained manner to avoid network congestion (links, switches), overload in the node's incoming links, and receive buffer overflow. Motivated by the use case of the Compressed Baryonic Matter experiment (CBM), we study the performance and variance of such communication patterns on a Cray XC40 with different routing schemes and scheduling approaches. We present a distributed Data Flow Scheduler (DFS) that reduces the variance of arrival times from all sources at least 30 times and increases the achieved aggregate bandwidth by up to 50%.

Building consensus sequences based on distributed, fault-tolerant consensus, as used for replicated state machines, typically requires a separate distributed state for every new consensus instance. Allocating and maintaining this state causes significant overhead. In particular, freeing the distributed, outdated states in a fault-tolerant way is not trivial and adds further complexity and cost to the system. In this article, we propose an extension to the single-decree Paxos protocol that can learn a sequence of consensus decisions `in-place', i.e., with a single set of distributed states. Our protocol does not require dynamic log structures and hence has no need for distributed log pruning, snapshotting, compaction, or dynamic resource allocation. The protocol builds a fault-tolerant atomic register that supports arbitrary read-modify-write operations. We use the concept of consistent quorums to detect whether the previous consensus still needs to be consolidated or is already finished so that the next consensus value can be safely proposed. Reading a consolidated consensus is done without state modifications and is thereby free of concurrency control and demand for serialisation. A proposer that is not interrupted reaches agreement on consecutive consensus decisions within a single message round-trip per decision by preparing the acceptors eagerly with the previous request.

General solutions of state machine replication have to ensure that all replicas apply the same commands in the same order, even in the presence of failures. Such strict ordering incurs high synchronization costs due to the use of distributed consensus or a leader. This paper presents a protocol for linearizable state machine replication of conflict-free replicated data types (CRDTs) that neither requires consensus nor a leader. By leveraging the properties of state-based CRDTs---in particular the monotonic growth of a join semilattice---synchronization overhead is greatly reduced. In addition, updates just need a single round trip and modify the state 'in-place' without the need for a log. Furthermore, the message size overhead for coordination consists of a single counter per message. While reads in the presence of concurrent updates are not wait-free without a coordinator, we show that more than 97\,% of reads can be handled in one or two round trips under highly concurrent accesses. Our protocol achieves high throughput without auxiliary processes such as command log management or leader election. It is well suited for all practical scenarios that need linearizable access on CRDT data on a fine-granular scale.

SUMMARY MR‐Search is a framework for massively parallel heuristic search. Based on the MapReduce paradigm, it efficiently utilizes all available resources: processors, memories, and disks. MR‐Search uses OpenMP on shared memory systems, Message Passing Interface on clusters with distributed memory, and a combination of both on clusters with multi‐core processors. Large graphs that do not fit into the main memory can be efficiently processed with an out‐of‐core variant. We implemented two node expansion strategies in MR‐Search: breadth‐first frontier search and breadth‐first iterative deepening A*. With breadth‐first frontier search, we computed large and powerful table‐driven heuristics, so‐called pattern databases that exceed the main memory capacity. These pattern databases were then used to solve random instances of the 24‐puzzle with breadth‐first iterative deepening A* on systems with up to 4093 processor cores. MR‐Search is conceptually simple. It takes care of data partitioning, process scheduling, out‐of‐core data merging, communication, and synchronization. Application developers benefit from the parallel computational capacity without having the burden of implementing parallel application code. Copyright © 2011 John Wiley & Sons, Ltd.

Distributed hash tables (DHT) often rely on uniform hashing for balancing the load among their nodes. However, the most overloaded node may still have a load up to O(log N) times higher than the average load. DHTs with support for range queries cannot rely on hashing to fairly balance the system's load since hashing destroys the order of the stored items. Ensuring a fair load distribution is vital to avoid individual nodes becoming overloaded, potentially leading to node crashes or an incentive not to participate in the system. In both scenarios explicit load balancing schemes can help to spread the load more evenly. In this paper, we improve on existing algorithms for item-based active load balancing by relying on approximations of global properties. We show that the algorithms can be made more efficient by incorporating estimates of properties such as the average load and the standard deviation. Our algorithms reduce the network traffic induced by load balancing while achieving a better load balance than standard algorithms. We also show that these improvements can be applied to passive load balancing algorithms. Compared to DHTs without explicit load balancing, both variants are able to reduce the total maintenance traffic, i.e. item movements due to churn and load balancing, by up to 18%. Simultaneously the system is being balanced achieving a better load distribution.

Key/value stores which are built on structured overlay networks often lack support for atomic transactions and strong data consistency among replicas. This is unfortunate, because consistency guarantees and transactions would allow a wide range of additional application domains to benefit from the inherent scalability and fault-tolerance of DHTs. The Scalaris key/value store supports strong data consistency and atomic transactions. It uses an enhanced Paxos Commit protocol with only four communication steps rather than six. This improvement was possible by exploiting information from the replica distribution in the DHT. Scalaris enables implementation of more reliable and scalable infrastructure for collaborative Web services that require strong consistency and atomic changes across multiple items.

Pattern databases (PDBs) store heuristic estimates that are used to improve the performance of heuristic search algorithms. They are key to the success of heuristic search in many application domains. While it is known [12] that the effectiveness of PDBs critically depends on their size, current implementations use only small PDBs because they require random access to main memory.

We present a distributed algorithm for identifying the location of data centers and their relative sizes. This topology information can be used in P2P systems to improve the routing performance, replica placement, or job scheduling. The algorithm uses gossiping with local agglomerative clustering. It is robust to failures and it correctly identifies outliers that are caused, e.g., by temporarily overloaded nodes or network failures. We present empirical results on the Grid 5000 testbed.

Structured Overlay Networks (SONs) provide a promising platform for high performance applications since they are scalable, fault-tolerant and self-managing. SONs provide lookup services that map keys to nodes that can be used as processing or storage resources. In SONs, lookups for a key may return inconsistent results. Consequently, it is difficult to provide consistent data services on top of SONs that build on key-based search. In this paper, we study the frequency of occurrence of inconsistent lookups. We show that the affect of lookup inconsistencies can be reduced by using node responsibilities. We present our results as a trade-off between consistency and availability of keys.

Core Grid technologies are rapidly maturing, but there remains a shortage of real Grid applications. One important reason is the lack of a simple and high-level application programming toolkit, bridging the gap between existing Grid middleware and application-level needs. The Grid Application Toolkit (GAT), as currently developed by the EC-funded project GridLab, provides this missing functionality. As seen from the application, the GAT provides a unified simple programming interface to the Grid infrastructure, tailored to the needs of Grid application programmers and users. A uniform programming interface will be needed for application developers to create a new generation of "Grid-aware" applications. The GAT implementation handles both the complexity and the variety of existing Grid middleware services via so-called adaptors. Complementing existing Grid middleware, GridLab also provides high-level services to implement the GAT functionality. We present the GridLab software architecture, consisting of the GAT, environment-specific adaptors, and GridLab services. We elaborate the concepts underlying the GAT and outline the corresponding application programming interface. We present the functionality of GridLab's high-level services and demonstrate how a dynamic Grid application can easily benefit from the GAT. All GridLab software is open source and can be downloaded from the project Web site.

We present a method for the efficient access to parts of remote files. The efficiency is achieved by using a file format independent compact pattern description, that allows us to request several parts of a file in a single operation. This results in a drastically reduced number of remote operations and network latencies if compared to common solutions. We measured the time to access parts of remote files with compact patterns, compared it with normal GridFTP remote partial file access and observed a significant performance increase. Further we discuss how the presented pattern access can be used for an efficient read from multiple replicas and how this can be integrated into a data management system to support the storage of partial replicas for large scale simulations.