Distributed Computing

In the fast evacuation problem, we study the path planning problem for two robots who want to minimize the worst-case evacuation time on the unit disk. The robots are initially placed at the center of the disk. In order to evacuate, they need to reach an unknown point, the exit, on the boundary of the disk. Once one of the robots finds the exit, it will instantaneously (using wireless communication) notify the other agent, who will make a beeline to it.The problem has been studied for robots with the same speed [8]. We study a more general case where one robot has speed 1 and the other has speed $$s \ge 1$$. We provide optimal evacuation strategies in the case that $$s \ge c_{2.75} \approx 2.75$$ by showing matching upper and lower bounds on the worst-case evacuation time. For $$1\le s < c_{2.75}$$, we show (non-matching) upper and lower bounds on the evacuation time with a ratio less than 1.22. Moreover, we demonstrate that a different-speeds generalization of the two-robot search strategy from [8] is outperformed by our proposed strategies for any $$s \ge c_{1.71} \approx 1.71$$.

This paper presents a distributed algorithm, called $$\mathcal{STT}$$, for electing deterministically a leader in an arbitrary network, assuming processors have unique identifiers of size $$O(\log n)$$, where n is the number of processors. It elects a leader in $$O(D +\log n)$$ rounds, where D is the diameter of the network, with messages of size O(1). Thus it has a bit round complexity of $$O(D +\log n)$$. This substantially improves upon the best known algorithm whose bit round complexity is $$O(D\log n)$$. In fact, using the lower bound by Kutten et al. [13] and a result of Dinitz and Solomon [8], we show that the bit round complexity of $$\mathcal{STT}$$ is optimal (up to a constant factor), which is a step forward in understanding the interplay between time and message optimality for the election problem. Our algorithm requires no knowledge on the graph such as n or D.

We develop a new technique for constructing sparse graphs that allow us to prove near-linear lower bounds on the round complexity of computing distances in the CONGEST model. Specifically, we show an $$\widetilde{\varOmega }(n)$$ lower bound for computing the diameter in sparse networks, which was previously known only for dense networks. In fact, we can even modify our construction to obtain graphs with constant degree, using a simple but powerful degree-reduction technique which we define.Moreover, our technique allows us to show $$\widetilde{\varOmega }(n)$$ lower bounds for computing $$(\frac{3}{2}-\varepsilon )$$-approximations of the diameter or the radius, and for computing a $$(\frac{5}{3}-\varepsilon )$$-approximation of all eccentricities. For radius, we are unaware of any previous lower bounds. For diameter, these greatly improve upon previous lower bounds and are tight up to polylogarithmic factors, and for eccentricities the improvement is both in the lower bound and in the approximation factor.Interestingly, our technique also allows showing an almost-linear lower bound for the verification of $$(\alpha ,\beta )$$-spanners, for $$\alpha < \beta +1$$.

We provide a thorough study of distributed property testing – producing algorithms for the approximation problems of property testing in the CONGEST model. In particular, for the so-called dense graph testing model we emulate sequential tests for nearly all graph properties having 1-sided tests, while in the general and sparse models we obtain faster tests for triangle-freeness, cycle-freeness and bipartiteness, respectively. In addition, we show a logarithmic lower bound for testing bipartiteness and cycle-freeness, which holds even in the LOCAL model.In most cases, aided by parallelism, the distributed algorithms have a much shorter running time as compared to their counterparts from the sequential querying model of traditional property testing. The simplest property testing algorithms allow a relatively smooth transitioning to the distributed model. For the more complex tasks we develop new machinery that may be of independent interest.

Censor-Hillel et al. [PODC’15] recently showed how to efficiently implement centralized algebraic algorithms for matrix multiplication in the congested clique model, a model of distributed computing that has received increasing attention in the past few years. This paper develops further algebraic techniques for designing algorithms in this model. We present deterministic and randomized algorithms, in the congested clique model, for efficiently computing multiple independent instances of matrix products, computing the determinant, the rank and the inverse of a matrix, and solving systems of linear equations. As applications of these techniques, we obtain more efficient algorithms for the computation, again in the congested clique model, of the all-pairs shortest paths and the diameter in directed and undirected graphs with small weights, improving over Censor-Hillel et al.’s work. We also obtain algorithms for several other graph-theoretic problems such as computing the number of edges in a maximum matching and the Gallai-Edmonds decomposition of a simple graph, and computing a minimum vertex cover of a bipartite graph.

For overlay networks, the ability to recover from a variety of problems like membership changes or faults is a key element to preserve their functionality. In recent years, various self-stabilizing overlay networks have been proposed that have the advantage of being able to recover from any illegal state. However, the vast majority of these networks cannot give any guarantees on its functionality while the recovery process is going on. We are especially interested in searchability, i.e., the functionality that search messages for a specific identifier are answered successfully if a node with that identifier exists in the network. We investigate overlay networks that are not only self-stabilizing but that also ensure that monotonic searchability is maintained while the recovery process is going on, as long as there are no corrupted messages in the system. More precisely, once a search message from node u to another node v is successfully delivered, all future search messages from u to v succeed as well. Monotonic searchability was recently introduced in OPODIS 2015, in which the authors provide a solution for a simple line topology. We present the first universal approach to maintain monotonic searchability that is applicable to a wide range of topologies. As the base for our approach, we introduce a set of primitives for manipulating overlay networks that allows us to maintain searchability and show how existing protocols can be transformed to use theses primitives. We complement this result with a generic search protocol that together with the use of our primitives guarantees monotonic searchability. As an additional feature, searching existing nodes with the generic search protocol is as fast as searching a node with any other fixed routing protocol once the topology has stabilized.

We consider the Embedded Pattern Formation (epf) problem introduced in [Fujinaga et al., SIAM J. on Comput., 44(3), 2015]. Given a set F of distinct points in the Euclidean plane (called here fixed-points) and a set R of robots such that $$|R|=|F|$$, the problem asks for a distributed algorithm that moves robots so as to occupy all points in F. Initially, each robot occupies a distinct position.Robots operate in standard Look-Compute-Move cycles. In one cycle, a robot perceives the current configuration in terms of the robots’ positions and the fixed-points (Look) according to its own coordinate system, decides whether to move (Compute), and in the positive case it moves (Move). Cycles are performed asynchronously for each robot. Robots are oblivious, anonymous and execute the same algorithm.In the mentioned paper, the problem has been investigated by assuming chirality, that is robots share a common left-right orientation. The obtained solution has been used as a sub-procedure to solve the Pattern Formation problem, without fixed-points but still with chirality.Here we investigate the other branch, that is, we are interested in solving epf without chirality. We fully characterize when the epf problem can be accomplished and we design a deterministic distributed algorithm that solves the problem for all configurations but those identified as unsolvable. Our approach is also characterized by the use of logical predicates in order to formally describe our algorithm as well as its correctness.

We show an $$\varOmega \big (\varDelta ^{\frac{1}{3}-\frac{\eta }{3}}\big )$$ lower bound on the runtime of any deterministic distributed $$\mathcal {O}\big (\varDelta ^{1+\eta }\big )$$-graph coloring algorithm in a weak variant of the $$\mathsf {LOCAL}$$ model.In particular, given a network graph $$G=(V,E)$$, in the weak $$\mathsf {LOCAL}$$ model nodes communicate in synchronous rounds and they can use unbounded local computation. The nodes have no identifiers, but instead, the computation starts with an initial valid vertex coloring. A node can broadcast a single message of unbounded size to its neighbors and receives the set of messages sent to it by its neighbors.The proof uses neighborhood graphs and improves their understanding in general such that it might help towards finding a lower (runtime) bound for distributed graph coloring in the standard $$\mathsf {LOCAL}$$ model.

Software-defined networking (SDN) enables controlling the behavior of a network in software, by managing the forwarding rules installed on switches. However, it can be difficult to ensure that certain properties are preserved during periods of reconfiguration. The widely-accepted notion of per-packet consistency requires every packet to be forwarded using the new configuration or the old configuration, but not a mixture of the two. A (partial) order on switches is a consistent order update if updating the switches in that order guarantees per-packet consistency. A consistent order update is optimal if it allows maximal parallelism, where switches may be updated in parallel if they are incomparable in the order. This paper presents a polynomial-time algorithm for computing optimal consistent order updates. This contrasts with other recent results, which show that for other properties (e.g., loop-freedom and waypoint enforcement), the optimal update problem is np-complete.

This paper studies the complexity of distributed construction of purely additive spanners in the CONGEST model. We describe algorithms for building such spanners in several cases. Because of the need to simultaneously make decisions at far apart locations, the algorithms use additional mechanisms compared to their sequential counterparts.We complement our algorithms with a lower bound on the number of rounds required for computing pairwise spanners. The standard reductions from set-disjointness and equality seem unsuitable for this task because no specific edge needs to be removed from the graph. Instead, to obtain our lower bound, we define a new communication complexity problem that reduces to computing a sparse spanner, and prove a lower bound on its communication complexity using information theory. This technique significantly extends the current toolbox used for obtaining lower bounds for the CONGEST model, and we believe it may find additional applications.

A computation scheme among n parties is fair if no party obtains the computation result unless all other $$n-1$$ parties obtain the same result. A fair computation scheme is optimistic if n honest parties can obtain the computation result without resorting to a trusted third party. We prove, for the first time, a tight lower-bound on the message complexity of optimistic fair computation for n parties among which $$n-1$$ can be malicious in an asynchronous network. We do so by relating the optimal message complexity of optimistic fair computation to the length of the shortest permutation sequence in combinatorics.

We show that many distributed network optimization problems can be solved much more efficiently in structured and topologically simple networks.It is known that solving essentially any global network optimization problem in a general network requires $$\varOmega (\sqrt{n})$$ rounds in the CONGEST model, even if the network diameter is small, e.g., logarithmic. Many networks of interest, however, have more structure which allows for significantly more efficient algorithms. Recently Ghaffari, Haeupler, Izumi and Zuzic [SODA’16,PODC’16] introduced low-congestion shortcuts as a suitable abstraction to capture this phenomenon. In particular, they showed that graphs with diameter D embeddable in a genus-g surface have good shortcuts and that these shortcuts lead to $$\tilde{O}(g D)$$-round algorithms for MST, Min-Cut and other problems.We generalize these results by showing that networks with pathwidth or treewidth k allow for good shortcuts leading to fast $$\tilde{O}(k D)$$ distributed optimization algorithms. We also improve the dependence on genus g from $$\tilde{O}(gD)$$ to $$\tilde{O}(\sqrt{g}D)$$. Lastly, we prove lower bounds which show that the dependence on k and g in our shortcuts is optimal. Overall, this significantly refines and extends the understanding of how the complexity of distributed optimization problems depends on the network topology.

The paper investigates the consensus problem in anonymous, failures prone and asynchronous shared memory systems. It introduces a new class of failure detectors, called anonymity-preserving failure detectors suited to anonymous systems. As its name indicates, a failure detector in this class cannot be relied upon to break anonymity. For example, the anonymous perfect detector AP, which gives at each process an estimation of the number of processes that have failed belongs to this class.The paper then determines the weakest failure detector among this class for consensus. This failure detector, called $$C $$, may be seen as a loose failures counter: (1) after a failure occurs, the counter is eventually incremented, and (2) if two or more processes are non-faulty, it eventually stabilizes.

We present a unified formal framework for expressing mobile robots models, protocols, and proofs, and devise a protocol design/proof methodology dedicated to mobile robots that takes advantage of this formal framework.As a case study, we present the first formally certified protocol for oblivious mobile robots evolving in a two-dimensional Euclidean space. In more details, we provide a new algorithm for the problem of universal gathering mobile oblivious robots (that is, starting from any initial configuration that is not bivalent, using any number of robots, the robots reach in a finite number of steps the same position, not known beforehand) without relying on a common orientation nor chirality. We give very strong guaranties on the correctness of our algorithm by proving formally that it is correct, using the Coq proof assistant.This result demonstrates both the effectiveness of the approach to obtain new algorithms that use as few assumptions as necessary, and its manageability since the amount of developed code remains human readable.

This work bridges the gap between distributed and centralised models of computing in the context of sublinear-time graph algorithms. A priori, typical centralised models of computing (e.g., parallel decision trees or centralised local algorithms) seem to be much more powerful than distributed message-passing algorithms: centralised algorithms can directly probe any part of the input, while in distributed algorithms nodes can only communicate with their immediate neighbours. We show that for a large class of graph problems, this extra freedom does not help centralised algorithms at all: efficient stateless deterministic centralised local algorithms can be simulated with efficient distributed message-passing algorithms. In particular, this enables us to transfer existing lower bound results from distributed algorithms to centralised local algorithms.

When considering n-process asynchronous systems, where up to t processes can fail, and communication is by read/write registers or reliable message-passing, are (from a computability point of view) Byzantine failures “different” from crash failures? This is the question addressed in this paper, which shows that the answer is “no” for systems where $$t<n/3$$.To this end, the paper presents a new distributed simulation whose core is an extended BG simulation suited to asynchronous message-passing systems. More precisely, assuming $$t<\min (n',n/3)$$, it describes a signature-free algorithm that simulates a system of $$n'$$ processes where up to t may crash, on top of a basic system of n processes where up to t may be Byzantine. In addition to extending (in a modular and direct way) the basic BG simulation to Byzantine message-passing systems this simulation also allows crash-tolerant algorithms, designed for asynchronous read/write systems, to be executed on top of asynchronous message-passing systems prone to Byzantine failures.

A distance labeling scheme is an assignment of bit-labels to the vertices of an undirected, unweighted graph such that the distance between any pair of vertices can be decoded solely from their labels. We propose a series of new labeling schemes within the framework of so-called hub labeling (HL, also known as landmark labeling or 2-hop-cover labeling), in which each node u stores its distance to all nodes from an appropriately chosen set of hubs $$S(u) \subseteq V$$. For a queried pair of nodes (u, v), the length of a shortest $$u\!-\!v$$-path passing through a hub node from $$S(u)\cap S(v)$$ is then used as an upper bound on the distance between u and v.We present a hub labeling which allows us to decode exact distances in sparse graphs using labels of size sublinear in the number of nodes. For graphs with at most n nodes and average degree $$\varDelta $$, the tradeoff between label bit size L and query decoding time T for our approach is given by $$L = \mathcal {O}(n \log \log _\varDelta T / \log _\varDelta T)$$, for any $$T \le n$$. Our simple approach is thus the first sublinear-space distance labeling for sparse graphs that simultaneously admits small decoding time (for constant $$\varDelta $$, we can achieve any $$T=\omega (1)$$ while maintaining $$L=o(n)$$), and it also provides an improvement in terms of label size with respect to previous slower approaches.By using similar techniques, we then present a 2-additive labeling scheme for general graphs, i.e., one in which the decoder provides a 2-additive-approximation of the distance between any pair of nodes. We achieve almost the same label size-time tradeoff $$L = \mathcal {O}(n \log ^2 \log T / \log T)$$, for any $$T \le n$$. To our knowledge, this is the first additive scheme with constant absolute error to use labels of sublinear size. The corresponding decoding time is then small (any $$T=\omega (1)$$ is sufficient).We believe all of our techniques are of independent value and provide a desirable simplification of previous approaches.

Distributed cloud applications, including batch processing, streaming, and scale-out databases, generate a significant amount of network traffic and a considerable fraction of their runtime is due to network activity. This paper initiates the study of deterministic algorithms for collocating frequently communicating nodes in a distributed networked systems in an online fashion. In particular, we introduce the Balanced RePartitioning (BRP) problem: Given an arbitrary sequence of pairwise communication requests between n nodes, with patterns that may change over time, the objective is to dynamically partition the nodes into $$\ell $$ clusters, each of size k, at a minimum cost. Every communication request needs to be served: if the communicating nodes are located in the same cluster, the request is served locally, at cost 0; if the nodes are located in different clusters, the request is served remotely using inter-cluster communication, at cost 1. The partitioning can be updated dynamically (i.e., repartitioned), by migrating nodes between clusters at cost $$\alpha $$ per node migration. The goal is to devise online algorithms which find a good trade-off between the communication and the migration cost, i.e., “rent” or “buy”, while maintaining partitions which minimize the number of inter-cluster communications. BRP features interesting connections to other well-known online problems. In particular, we show that scenarios with $$\ell =2$$ generalize online paging, and scenarios with $$k=2$$ constitute a novel online version of maximum matching. We consider settings both with and without cluster-size augmentation. Somewhat surprisingly (and unlike online paging), we prove that any deterministic online algorithm has a competitive ratio of at least k, even with augmentation. Our main technical contribution is an $$O(k \log {k})$$-competitive deterministic algorithm for the setting with (constant) augmentation. This is attractive as, in contrast to $$\ell $$, k is likely to be small in practice. For the case of matching ($$k=2$$), we present a constant competitive algorithm that does not rely on augmentation.

Obstruction-free consensus, ensuring that a process running solo will eventually terminate, is at the core of practical ways to solve consensus, e.g., by using randomization or failure detectors. An obstruction-free consensus algorithm may not terminate in many executions, but it must terminate whenever a process runs solo. Such an algorithm can be evaluated by its solo step complexity, which bounds the worst case number of steps taken by a process running alone, from any configuration, until it decides.This paper presents a lower bound of $$\varOmega (\log n)$$ on the solo step complexity of obstruction-free binary anonymous consensus. The proof constructs a sequence of executions in which more and more distinct variables are about to be written to, and then uses the backtracking covering technique to obtain a single execution in which many variables are accessed.

Most of the popular Transactional Memory (TM) algorithms are known to be safe because they satisfy opacity, the well-known correctness criterion for TM algorithms. Recently, it has been shown that they are even more conservative, and that they satisfy TMS2, a strictly stronger property than opacity. This paper investigates the theoretical and practical implications of relaxing those algorithms in order to allow histories that are not TMS2. In particular, we present four impossibility results on TM implementations that are not TMS2 and are either opaque or strictly serializable, and one practical TM implementation that extends TL2, a high-performance state-of-the-art TM algorithm, to allow non-TMS2 histories. By matching our theoretical findings with the results of our performance evaluation, we conclude that designing and implementing TM algorithms that are not TMS2, but safe, has inherent costs that limit any possible performance gain.

To implement a linearizable shared memory in synchronous message-passing systems it is necessary to wait for a time linear to the uncertainty in the latency of the network for both read and write operations. Waiting only for one of them suffices for sequential consistency. This paper extends this result to crash-prone asynchronous systems, proposing a distributed algorithm that builds a sequentially consistent shared snapshot memory on top of an asynchronous message-passing system where less than half of the processes may crash. We prove that waiting is needed only when a process invokes a read/snapshot right after a write.We also show that sequential consistency is composable in some cases commonly encountered: (1) objects that would be linearizable if they were implemented on top of a linearizable memory become sequentially consistent when implemented on top of a sequential memory while remaining composable and (2) in round-based algorithms, where each object is only accessed within one round.

In this paper, we define k-abortable objects, the first kind of abortable objects [2, 7] that guarantee some degree of progress even under high contention. The definition is simple and natural: intuitively, an operation on a k-abortable object can abort only if k operations from distinct processes succeed during the execution of the aborted operation. We first show that k-abortable objects can easily implement k-lock-free objects, i.e., objects where at least k processes make progress [5], but in contrast to k-lock-free objects, k-abortable objects always return control. We then give an efficient universal construction for wait-free k-abortable objects shared by n processes that takes only O(k) steps per operation. We also give a $$\varOmega (\log k)$$-steps lower bound for universal constructions of k-abortable objects shared by $$n \ge k$$ processes. Since every wait-free k-abortable object can implement its k-lock-free counterpart, our universal construction also provides a universal construction for k-lock-free objects.

This paper provides a theoretical and practical framework for crash-resilient data structures on a machine with persistent (nonvolatile) memory but transient registers and cache. In contrast to certain prior work, but in keeping with “real world” systems, we assume a full-system failure model, in which all transient state (of all processes) is lost on a crash. We introduce the notion of durable linearizability to govern the safety of concurrent objects under this failure model and a corresponding relaxed, buffered variant which ensures that the persistent state in the event of a crash is consistent but not necessarily up to date.At the implementation level, we present a new “memory persistency model,” explicit epoch persistency, that builds upon and generalizes prior work. Our model captures both hardware buffering and fully relaxed consistency, and subsumes both existing and proposed instruction set architectures. Using the persistency model, we present an automated transform to convert any linearizable, nonblocking concurrent object into one that is also durably linearizable. We also present a design pattern, analogous to linearization points, for the construction of other, more optimized objects. Finally, we discuss generic optimizations that may improve performance while preserving both safety and liveness.

We consider the slight variation of the adversarial queuing theory model in which an adversary injects packets with routes into the network subject to the following constraint: For any link e, the total number of packets injected in any time window $$[t,t')$$ and whose route contains e is at most $$\rho (t'-t)+\sigma $$, where $$\rho $$ and $$\sigma $$ are non-negative parameters. Informally, $$\rho $$ bounds the long-term rate of injections and $$\sigma $$ bounds the “burstiness” of injection: $$\sigma =0$$ means that the injection is as smooth as it can be.It is known that greedy scheduling of the packets (under which a link is not idle if there is any packet ready to be sent over it) may result in $$\varOmega (n)$$ buffer size even on an n-node line network and very smooth injections ($$\sigma =0$$). In this paper, we propose a simple non-greedy scheduling policy and show that, in a tree where all packets are destined at the root, no buffer needs to be larger than $$\sigma +2\rho $$ to ensure that no overflows occur, which is optimal in our model. The rule of our algorithm is to forward a packet only if its next buffer is completely empty. The policy is centralized: in a single step, a long “train” of packets may progress together. We show that, in some sense, central coordination is required for our algorithm, and even for the more sophisticated “downhill” algorithm in which each node forwards a packet only if its next buffer is less occupied than its current one. This is shown by presenting an injection pattern with $$\sigma =0$$ for the n-node line that results in $$\varOmega (n)$$ packets in a buffer if local control is used.

We study property testing in the context of distributed computing, under the classical CONGEST model. It is known that testing whether a graph is triangle-free can be done in a constant number of rounds, where the constant depends on how far the input graph is from being triangle-free. We show that, for every connected 4-node graph H, testing whether a graph is H-free can be done in a constant number of rounds too. The constant also depends on how far the input graph is from being H-free, and the dependence is identical to the one in the case of testing triangle-freeness. Hence, in particular, testing whether a graph is $$K_4$$-free, and testing whether a graph is $$C_4$$-free can be done in a constant number of rounds (where $$K_k$$ denotes the k-node clique, and $$C_k$$ denotes the k-node cycle). On the other hand, we show that testing $$K_k$$-freeness and $$C_k$$-freeness for $$k\ge 5$$ appear to be much harder. Specifically, we investigate two natural types of generic algorithms for testing H-freeness, called DFS tester and BFS tester. The latter captures the previously known algorithm to test the presence of triangles, while the former captures our generic algorithm to test the presence of a 4-node graph pattern H. We prove that both DFS and BFS testers fail to test $$K_k$$-freeness and $$C_k$$-freeness in a constant number of rounds for $$k\ge 5$$.

In this paper, we study PUSH-PULL style rumor spreading algorithms in the mobile telephone model, a variant of the classical telephone model in which each node can participate in at most one connection per round; i.e., you can no longer have multiple nodes pull information from the same source in a single round. Our model also includes two new parameterized generalizations: (1) the network topology can undergo a bounded rate of change (for a parameterized rate that spans from no changes to changes in every round); and (2) in each round, each node can advertise a bounded amount of information to all of its neighbors before connection decisions are made (for a parameterized number of bits that spans from no advertisement to large advertisements). We prove that in the mobile telephone model with no advertisements and no topology changes, PUSH-PULL style algorithms perform poorly with respect to a graph’s vertex expansion and graph conductance as compared to the known tight results in the classical telephone model. We then prove, however, that if nodes are allowed to advertise a single bit in each round, a natural variation of PUSH-PULL terminates in time that matches (within logarithmic factors) this strategy’s performance in the classical telephone model—even in the presence of frequent topology changes. We also analyze how the performance of this algorithm degrades as the rate of change increases toward the maximum possible amount. We argue that our model matches well the properties of emerging peer-to-peer communication standards for mobile devices, and that our efficient PUSH-PULL variation that leverages small advertisements and adapts well to topology changes is a good choice for rumor spreading in this increasingly important setting.

Shuffle a deck of n cards numbered 1 through n. Deal out the first c cards into a hand. A player then repeatedly chooses one of the cards from the hand, inserts it into a binary search tree, and then adds the next card from deck to the hand (if the deck is empty). When the player finally runs out of cards, how deep can the search tree be?This problem is motivated by concurrent insertions by c processes of random keys into a binary search tree, where the order of insertions is controlled by an adversary that can delay individual processes. We show that an adversary that uses any strategy based on comparing keys cannot obtain an expected average depth greater than $$O(c + \log n)$$. However, the adversary can obtain an expected tree height of $$\varOmega (c \log (n/c))$$, using a simple strategy of always playing the largest available card.

Mutual exclusion is a fundamental problem in distributed computing. In one well known variant of this problem, which we call priority mutual exclusion, processes have priorities and the requirement is that, whenever the critical section becomes vacant, the next occupant should be the process that has the highest priority among the waiting processes. Instead of first capturing this vague, but intuitively appealing requirement by a rigorously specified condition, earlier research rushed into proposing algorithms. Consequently, as we explain in the paper, none of the existing algorithms meet the reasonable expectations we would have of an algorithm that claims to respect process priorities. This paper fixes this situation by rigorously specifying the priority mutual exclusion problem and designing an efficient algorithm for it. Our algorithm supports an arbitrary number of processes and, when configured to support m priority levels (m can be any natural number), the algorithm has O(m) RMR complexity on both DSM and CC machines.

We study the problem of gossip in dynamic networks controlled by an adversary that can modify the network arbitrarily from one round to another, provided that the network is always connected. In the gossip problem, there are n tokens arbitrarily distributed among the n network nodes, and the goal is to disseminate all the n tokens to every node. Our focus is on token-forwarding algorithms, which do not manipulate tokens in any way other than storing, copying, and forwarding them. An important open question is whether gossip can be realized by a distributed protocol that can do significantly better than an easily achievable bound of $$O(n^2)$$ rounds.In this paper, we study oblivious adversaries, i.e., those that are oblivious to the random choices made by the protocol. We consider Rand-Diff, a natural distributed algorithm in which neighbors exchange a token chosen uniformly at random from the difference of their token sets. We present an $$\tilde{\varOmega }(n^{3/2})$$ lower bound for Rand-Diff under an oblivious adversary. We also present an $$\tilde{\varOmega }(n^{4/3})$$ lower bound under a stronger notion of oblivious adversary for a class of randomized distributed algorithms—symmetric knowledge-based algorithms— in which nodes make token transmission decisions based entirely on the sets of tokens they possess over time. On the positive side, we present a centralized algorithm that completes gossip in $$\tilde{O}(n^{3/2})$$ rounds with high probability, under any oblivious adversary. We also show an $$\tilde{O}(n^{5/3})$$ upper bound for Rand-Diff in a restricted class of oblivious adversaries, which we call paths-respecting, that may be of independent interest.

This paper addresses the problem of non-Bayesian learning over multi-agent networks, where agents repeatedly collect partially informative observations about an unknown state of the world, and try to collaboratively learn the true state. We focus on the impact of the Byzantine agents on the performance of consensus-based non-Bayesian learning. Our goal is to design an algorithm for the non-faulty agents to collaboratively learn the true state through local communication.We propose an update rule wherein each agent updates its local beliefs as (up to normalization) the product of (1) the likelihood of the cumulative private signals and (2) the weighted geometric average of the beliefs of its incoming neighbors and itself (using Byzantine consensus). Under mild assumptions on the underlying network structure and the global identifiability of the network, we show that all the non-faulty agents asymptotically agree on the true state almost surely.

A task is a distributed coordination problem where processes start with private inputs, communicate with one another, and then halt with private outputs. A protocol that solves a task is t-resilient if it tolerates halting failures by t or fewer processes. The t-resilient asynchronous computability theorem stated here characterizes the tasks that have t-resilient protocols in a shared-memory model. This result generalizes the prior (wait-free) asynchronous computability theorem of Herlihy and Shavit to a broader class of failure models, and requires introducing several novel concepts.

A fundamental technique used in the design of shared memory algorithms is tagging, where registers or other shared objects get augmented with additional values, called tags. In this paper, we provide a framework for tagging, and prove upper bounds for the complexity of this problem. We define new types that allow processes to generate tags infinitely often, store them to or retrieve them from other objects, use them safely, and release them when they are not needed any more. We present asymptotically optimally time efficient implementations of those types from objects of bounded size. In particular, our tags need only objects of logarithmic size, and operations on them can be performed in constant step complexity. In addition to the straightforward applications that use tags directly, our implementations can also be used for memory reclamation in a number of algorithms, such as those based on single compare-and-swap universal or read-copy-update.