Linearizability [5] of a concurrent object ensures that operations on that object appear to execute atomically. It is well known that linearizable implementations are composable: in an algorithm designed to work with atomic objects, replacing any atomic object with a linearizable implementation preserves the correctness of the original algorithm. However, replacing atomic objects with linearizable ones in a randomized algorithm can break the original probabilistic guarantees [3]. With an adaptive adversary, this problem is solved by using strongly linearizable [3] objects in the composition. How about with an oblivious adversary.

We consider the following natural problem: n failure-prone servers, communicating synchronously through message passing, must assign themselves one-to-one to n distinct items. Existing literature suggests two possible approaches to this problem. First, model it as an instance of tight renaming in synchronous message-passing systems; for deterministic solutions, a tight bound of Θ(log n) communication rounds is known. Second, model the scenario as an instance of randomized load-balancing, for which elegant sub-logarithmic solutions exist. However, careful examination reveals that known load-balancing schemes do not apply to our scenario, because they either do not tolerate faults or do not ensure one-to-one allocation. It is thus natural to ask if sub-logarithmic solutions exist for this apparently simple but intriguing problem.

Abstract—Renaming is a fundamental problem in distributed computing, which consists of a set of processes picking distinct names from a given namespace. The paper presents algorithms that solve order-preserving renaming in synchronous message passing systems with Byzantine processes. To the best of our knowledge, this work is the first to address order-preserving renaming in the given model. Although this problem can be solved by using consensus, it is known that renaming is “weaker ” than consensus, therefore we are mainly concerned with the efficiency of performing renaming and make three contributions in this direction. We present an order-preserving renaming algorithm for N> 3t with target namespace of size N+t−1 and logarithmic step complexity (where N is the number of processes and t is an upper bound on the number of faults). Similarly to the existing crash-tolerant solution, our algorithm employs the ideas from the approximate agreement problem. We show that our algorithm has constant step complexity if N> t2 + 2t and achieves tight namespace of size N. Finally, we present an algorithm that solves order-preserving renaming in just 2 communication steps, if N> 2t2 + t. I.

In this paper we consider the fundamental problems of renaming and order-preserving renaming [1] in a synchronous message passing system with Byzantine failures. We study the feasibility of solving these problems using randomized algorithms under both non-rushing and rushing adversaries. We first show that there is a randomized algorithm that solves renaming efficiently for any t < N under the non-rushing adversary (N is the number of processes, and t is the maximum number of Byzantine processes). This result establishes a separation between randomized and deterministic renaming, since it is known that there are no efficient deterministic algorithms for t≥N/3. Our algorithm terminates in O(log N) rounds w.h.p. We next consider the renaming problem in the harder setting with the rushing adversary. Interestingly, we show that in this setting the algorithm also works with t = 1 but fails for larger t. We then give an algorithm that works with any t < N by relying on cryptographic commitment. Finally, we turn our attention to the problem of order-preserving renaming, which requires the new names to preserve the order of the initial identifiers. For this problem, we prove a tight t < N/3 bound that holds for both deterministic and randomized algorithms.

Renaming is a fundamental problem in distributed computing which consists in a set of processors picking distinct names from a given namespace. We are interested in a stronger variant of the problem in which the processors have to pick new names according to the initial order of their original ids.

Multicast is an important building block for many applications in MANETs, including data dissemination, service discovery, publish-subscribe, among others. Therefore, it has been widely studied and many solutions can be found in the literature. However, most existing multicast protocols are tailored to a specific type of mobility pattern and therefore are unable to excel in face of heterogeneous topology stability conditions. This paper proposes and evaluates TSAMP, a Topology Stability-Aware Multicast Protocol for MANETs that exploits locally perceived mobility conditions in order to promote the use of stable routes, when available.