The class of extension-based proofs encompasses traditional valency arguments. It has been shown that they are insufficient to establish the impossibility of (n-1)-set agreement among n ≥ 3 processes in an asynchronous system with crash failures. We generalize this definition to k-exhaustive extension-based proofs, in which a prover can learn the maximum length of all executions involving a set of at most k processes from a specified configuration (which may be infinite). An upper bound on the length of these executions enables the prover to determine the outputs of all these executions. When k = n, this enables the prover to perform an exhaustive search of all reachable configurations, so it knows everything about the protocol. On the other hand, extension based proofs are as powerful as 1-exhaustive extension-based proofs. For any task with no deterministic, wait-free solution among n ≥ 2 processes, we show that there is an (n-1)-exhaustive extension-based proof of its impossibility. This is done using a new characterization of such tasks. In contrast, we prove that for 1 ≤ k ≤ n-2, there is no k-exhaustive extension-based proof of the impossibility of (n-1)-set agreement.

This paper studies distributed-computing tasks through the lens of space complexity in the read/write wait-free model, defined as the number of multi-reader-multi-writer atomic read/write registers needed to solve a task using a wait-free algorithm. Surprisingly, even though the read/write wait-free model is at the foundation of distributed computing, previous work on space complexity has focused on synchronization primitives stronger than read/write registers or on weaker progress conditions. The paper reveals that the read/write wait-free model offers a rich space-complexity landscape: (1) assuming non-anonymous processes, it shows that there is an infinite hierarchy of tasks of increasing space complexity; (2) it shows that space complexity separates anonymous from non-anonymous memory; (3) regardless of process or register anonymity, it exhibits a task of space complexity two, which is the minimal non-trivial space complexity; (4) finally, it shows that subcases of the adopt-commit task have different space complexity in non-anonymous memory under bounded wait-freedom.

Not knowing if something can be done and doing it = research.

Delporte-Gallet et al. show that, in a system of n processes, it is both necessary and sufficient to use n multi-writer multi-reader (MWMR) registers, that are not pre-allocated, to emulate with non-blocking progress n single-writer multi-reader (SWMR) registers that are uniquely pre-allocated. They conclude with the significant result that n MWMR registers are sufficient to solve any task solvable read-write wait-free. However, they mistakenly claim—likely inadvertently—that n MWMR registers are also necessary to solve any task solvable read-write wait-free (a counterexample is the splitter task, which is solvable for any number of processes with just 2 MWMR registers).

In the fully-anonymous (shared-memory) model, inspired by a biological setting, processors have no identifiers and memory locations are anonymous, meaning there is no pre-existing agreement among processors on any naming of the memory locations. In this work, we ask fundamental questions about the fully-anonymous model in the hope to obtain a better understanding of the role of naming and anonymity in distributed computing.

In a permissionless system like Ethereum, participation may fluctuate dynamically as some participants unpredictably go offline and some others come back online. In such an environment, traditional Byzantine fault-tolerant consensus algorithms may stall - even in the absence of failures - because they rely on the availability of fixed-sized quorums. The sleepy model formally captures the main requirements for solving consensus under dynamic participation, and several algorithms solve consensus with probabilistic safety in this model assuming that, at any time, more than half of the online participants are well behaved. However, whether safety can be ensured deterministically under these assumptions, especially with constant latency, remained an open question. Assuming a constant adversary, we answer in the positive by presenting a consensus algorithm that achieves deterministic safety and constant latency in expectation. In the full version of this paper, we also present a second algorithm which obtains both deterministic safety and liveness, but is likely only of theoretical interest because of its high round and message complexity. Both algorithms are striking in their simplicity.

International payments are slow and expensive, in part because of multi-hop payment routing through heterogeneous banking systems. Stellar is a new global payment network that can directly transfer digital money anywhere in the world in seconds. The key innovation is a secure transaction mechanism across untrusted intermediaries, using a new Byzantine agreement protocol called SCP. With SCP, each institution specifies other institutions with which to remain in agreement; through the global interconnectedness of the financial system, the whole network then agrees on atomic transactions spanning arbitrary institutions, with no solvency or exchange-rate risk from intermediary asset issuers or market makers. We present SCP's model, protocol, and formal verification; describe the Stellar payment network; and finally evaluate Stellar empirically through benchmarks and our experience with several years of production use.

In a previous note (arXiv:1712.01367 [cs.DC]) , we observed a safety violation in Zyzzyva and a liveness violation in FaB. In this manuscript, we sketch fixes to both. The same view-change core is applied in the two schemes, and additionally, applied to combine them and create a single, enhanced scheme that has the benefits of both approaches.

The consensus hierarchy classifies shared an object according to its consensus number, which is the maximum number of processes that can solve consensus wait-free using the object. The question of whether this hierarchy is precise enough to fully characterize the synchronization power of deterministic shared objects was open until 2016, when Afek et al. showed that there is an infinite hierarchy of deterministic objects, each weaker than the next, which is strictly between i and i+1-processors consensus, for i >= 2. For i=1, the question whether there exist a deterministic object whose power is strictly between read-write and 2-processors consensus, remained open. We resolve the question positively by exhibiting an infinite hierarchy of simple deterministic objects which are equivalent to set-consensus tasks, and thus are stronger than read-write registers, but they cannot implement consensus for two processes. Still our paper leaves a gap with open questions.

We present two algorithms for the Group Mutual Exclusion (GME) Problem that satisfy the properties of Mutual Exclusion , Starvation Freedom, Bounded Exit, Concurrent Entry and First Come First Served . Both our algorithms use only simple read and write instructions, have O ( N ) Shared Space complexity and O ( N ) Remote Memory Reference (RMR) complexity in the Cache Coherency (CC) model. Our first algorithm is developed by generalizing the well-known Lamport's Bakery Algorithm for the classical mutual exclusion problem, while preserving its simplicity and elegance. However, it uses unbounded shared registers. Our second algorithm uses only bounded registers and is developed by generalizing Taubenfeld's Black and White Bakery Algorithm to solve the classical mutual exclusion problem using only bounded shared registers. We show that contrary to common perception our algorithms are the first to achieve these properties with this combination of complexities.

A natural way to measure the power of a distributed-computing model is to characterize the set of tasks that can be solved in it. In general, however, the question of whether a given task can be solved in a given model is undecidable, even if we only consider the wait-free shared-memory model. In this paper, we address this question for restricted classes of models and tasks. We show that the question of whether a collection C of (l, j)-set consensus objects, for various l (the number of processes that can invoke the object) and j (the number of distinct outputs the object returns), can be used by n processes to solve wait-free k-set consensus is decidable. Moreover, we provide a simple O(n^2) decision algorithm, based on a dynamic programming solution to the Knapsack optimization problem. We then present an adaptive wait-free set-consensus algorithm that, for each set of participating processes, achieves the best level of agreement that is possible to achieve using C. Overall, this gives us a complete characterization of a read-write model defined by a collection of set-consensus objects through its set-consensus power.

The wait-free read-write memory model has been characterized as an iterated Immediate Snapshot (IS) task. The IS task is affine — it can be defined as a (sub)set of simplices of the standard chromatic subdivision. In this paper, we highlight the phenomenon of a "natural" model that can be captured by an iterated affine task and, thus, by a subset of runs of the iterated immediate snapshot model. We show that the read-write memory model in which, additionally, k-set-consensus objects can be used is "natural" by presenting the corresponding simple affine task captured by a subset of 2-round IS runs. As an "unnatural" example, the model using the abstraction of Weak Symmetry Breaking (WSB) cannot be captured by a set of IS runs and, thus, cannot be represented as an affine task. Our results imply the first combinatorial characterization of models equipped with abstractions other than read-write memory that applies to generic tasks.

For all integers m ≥ 2, we construct an infinite sequence of deterministic objects of consensus number m with strictly increasing computational power. In particular, this refutes the Common2 Conjecture, which claimed that every deterministic object of consensus number 2 has a deterministic, wait-free implementation from 2-consensus objects and registers in a system with any finite number of processes.

Adaptive renaming can be viewed as a coordination task involving a set of asynchronous agents, each aiming at grabbing a single resource out of a set of resources totally ordered by their desirability. We consider a generalization of adaptive renaming to take into account scenarios in which resources are not independent.

We consider the models of distributed computation defined as subsets of the runs of the iterated immediate snapshot model. Given a task T and a model M, we provide topological conditions for T to be solvable in M. When applied to the wait-free model, our conditions result in the celebrated Asynchronous Computability Theorem (ACT) of Herlihy and Shavit.

In the musical chairs game $MC(n,m)$, a team of $n$ players plays against an adversarial scheduler. The scheduler wins if the game proceeds indefinitely, while termination after a finite number of rounds is declared a win of the team. At each round of the game each player occupies one of the $m$ available chairs. Termination (and a win of the team) is declared as soon as each player occupies a unique chair. Two players that simultaneously occupy the same chair are said to be in conflict. In other words, termination (and a win for the team) is reached as soon as there are no conflicts. The only means of communication throughout the game is this: At every round of the game, the scheduler selects an arbitrary nonempty set of players who are currently in conflict, and notifies each of them separately that it must move. A player who is thus notified changes its chair according to its deterministic program. As we show, for $m\ge 2n-1$ chairs the team has a winning strategy. Moreover, using topological arguments we show that this bound is tight. For $m\leq 2n-2$ the scheduler has a strategy that is guaranteed to make the game continue indefinitely and thus win. We also have some results on additional interesting questions. For example, if $m \ge 2n-1$ (so that the team can win), how quickly can they achieve victory?

We motivate and propose a new way of thinking about failure detectors which allows us to define, quite surprisingly, what it means to solve a distributed task wait-free using a failure detector. In our model, the system is composed of computation processes that obtain inputs and are supposed to produce outputs and synchronization processes that are subject to failures and can query a failure detector. Under the condition that correct synchronization processes take sufficiently many steps, they provide the computation processes with enough advice to solve the given task wait-free: every computation process outputs in a finite number of its own steps, regardless of the behavior of other computation processes. Every task can thus be characterized by the weakest failure detector that allows for solving it, and we show that every such failure detector captures a form of set agreement. We then obtain a complete classification of tasks, including ones that evaded comprehensible characterization so far, such as renaming or weak symmetry breaking.

In the k-set agreement problem, each processor starts with a private input value and eventually decides on an output value. At most k distinct output values may be chosen, and every processor's output value must be one of the proposed values. We consider a synchronous message passing system, and we prove a tight bound of $\lfloor f/k\rfloor+2$ rounds of communication for all processors to decide in every run in which at most f processors fail. The lower bound proof proceeds through a simulation of a synchronous solution to k-set agreement in message passing, in an asynchronous shared memory system in which $k-1$ processors may fail, and which was proven to be impossible using topological approaches. In contrast to past complexity results on set agreement, our lower bound proof is purely algorithmic. It does not use any direct topological argument but uses instead the impossibility of asynchronous set agreement to encapsulate the needed topology. We thus derive an adaptive complexity lower bound for a message passing system from a static impossibility in a shared memory system.

The condition of t-resilience stipulates that an n-process program is only obliged to make progress when at least n-t processes are correct. Put another way, the live sets, the collection of process sets such that progress is guaranteed if at least one of the sets is correct, are all sets with at least n-t processes.

A failure detector is a distributed oracle that provides processes in a distributed system with hints about failures. The notion of a weakest failure detector captures the exact amount of synchrony needed for solving a given distributed computing problem.

A distributed task T on n processors is an input/output relation between a collection of processors' inputs and outputs. While all tasks are solvable if no processor may ever crash, the FLP result revealed that the possibility of a failure of just a single processor precludes a solution to the task of consensus. That is consensus is not solvable 1-resiliently. Yet, some nontrivial tasks are wait-free solvable, i.e. n-1-resiliently. What tasks are solvable if at most t

An important issue in fault-tolerant asynchronous computing is the respective power of an object type with respect to another object type. This question has received a lot of attention, mainly in the context of the consensus problem where a major advance has been the introduction of the consensus number notion that allows ranking the synchronization power of base object types (atomic registers, queues, test&set objects, compare&swap objects, etc.) with respect to the consensus problem. This has given rise to the well-known Herlihy's hierarchy. Due to its very definition, the consensus number notion is irrelevant for studying the respective power of object types that are too weak to solve consensus for an arbitrary number of processes (these objects are usually called subconsensus objects). Considering an asynchonous system made up of n processes prone to crash, this paper addresses the power of such object types, namely, the k-test&set object type, the k-set agreement object type, and the adaptive M-renaming object type for M = 2p - [P/N] and M = min(2p - 1,p + k - 1), where p < n is the number of processes that want to acquire a new name. It investigates their respective power stating the necessary and sufficient conditions to build objects of any of these types from objects of any of the other types. More precisely, the paper shows that (1) these object types define a strict hierarchy when k ne1,n - 1, (2) they all are equivalent when k = n - 1, and (3) they all are equivalent except k-set agreement that is stronger when k = 1 ne n - 1 (a side effect of these results is that that the consensus number of the renaming problem is 2.)

Common2, the family of objects that implement and are wait-free implementable from 2 consensus objects, is extended inhere in two ways: First, the stack object is added to the family --- an object that was conjectured not to be in the family. Second, Common2 is investigated in the unbounded concurrency model, whereas until now it was considered only in an n-process model.We show that fetch-and-add, test-and-set, and stack are in Common2 even with respect to this stronger notion of wait-free implementation. This necessitated the wait-free implementation of immediate snapshots in the unbounded concurrency model, which was previously not known to be possible.In addition to extending Common2, the introduction of unbounded-concurrency may help in resolving the Common2 membership problem: If, as conjectured, queue is not implementable for a-priori known concurrency n, then it is definitely not implementable for unbounded concurrency. Proving the latter should be easier than proving the former. In addition we conjecture that the swap object, that has an n-process implementation, does not have an unbounded concurrency implementation.

Set agreement, where processors decisions constitute a set of outputs, is notoriously harder to analyze than consensus where the decisions are restricted to a single output. This is because the topological questions that underly set agreement are not about simple connectivity as in consensus. Analyzing set agreement inspired the discovery of the relation between topology and distributed algorithms, and consequently the impossibility of asynchronous set agreement.Yet, the application of topological reasoning has been to the static case, that of asynchronous and synchronous tasks. It is not known yet for example, how to characterize starvation-free solvability of non-terminating tasks. Non-terminating tasks are dynamic entities with no defined end. In a similar vain, early deciding synchronous set agreement, in which the number of rounds it takes a processor to decide adapts to the actual number of failures, falls in this category of dynamic entities.This paper develops a simulation technique that brings to bear topological results to deal with the dynamic situation that arises with early decisions. The novelty of the new simulation is the ability of simulators to look back at the transcript of past rounds of the simulation to influence their current behavior.Using our new technique, we not only re-derive past results, but we propose and prove a lower bound to synchronous early stopping set agreement. We then provide an algorithm to match the lower bound. Our technique uses the BG simulation, in the most creative way it was used to-date, to obtain a rather simple reduction from a static asynchronous impossibility. This reduction is a simple alternative to yet unknown topological argument, and in fact may suggest the way of finding such an argument.

Recent advances in storage technology have enabled systems like Storage Area Networks, where disks are attached directly to the network, rather than being under the control of a single process. In such an environment there is no a priori bound on the number of processes that may access the network attached disks, and so uniform implementations are desirable, that is, implementations that do not rely on the number of processes. We investigate how to use network attached disks, where some disks may crash, as a shared communication medium. To do so, we model disk blocks as Multi-Writer Multi-Reader (MWMR) shared memory registers that may fail by crashing. We study whether a finite number of such fail-prone registers can be used to uniformly implement various types of fail-flee target registers: wait-free atomic, atomic, and wait-free sequentially consistent. For each of these types, we determine the implementability of Multi-Writer Multi-Reader registers, Multi-Writer Single-Reader registers (MWSR), Single-Writer Multi-Reader registers (SWMR) and Single-Writer Single-Reader registers (SWSR). For example, we show that there is no uniform atomic implementation of a MWMR register using finitely many base registers, even if the implementation need not be wait-free. On the positive side we show that with infinitely many base registers then all types of registers can be implemented. This opens the question of how to translate uniform shared memory protocols that use MWMR registers to use network attached disks.

The Herlihy-Shavit (HS) conditions characterizing the solvability of asynchronous tasks over n processors have been a milestone in the development of the theory of distributed computing. Yet, they were of no help when researcher sought algorithms that do not depend on n. To help in this pursuit we investigate the uniform solvability of an infinite uniform sequence of tasks T/sub 0/, T/sub 1/, T/sub 2/,..., where T/sub i/ is a task over processors p/sub 0/, p/sub 1/,...,p/sub i/, and T/sub i/ extends T/sub i-1/. We say that such a sequence is uniformly solvable if there exit protocols to solve each T/sub i/ and the protocol for T/sub i/ extends the protocol for T/sub i-1/. This paper establishes that although each T/sub i/ may be solvable, the uniform sequence is not necessarily uniformly solvable. We show this by proposing a novel uniform sequence of solvable tasks and proving that the sequence is not amenable to a uniform solution. We then extend the HS conditions for a task over n processors, to uniform solvability in a natural way. The technique we use to accomplish this is to generalize the alternative algorithmic proof, by Borowsky and Gafni, of the HS conditions, by showing that the infinite uniform sequence of task of Immediate Snapshots is uniformly solvable. A side benefit of the technique is a widely applicable methodology for the development of uniform protocols.

We present a generic module, called Fast Collect. Fast Collect is an implementation of single-writer multi-reader (SWMR) shared-memory in an asynchronous system in which a processor updates its cell and then reads in any order all the other cells. Our simple implementation of Fast Collect uses some multiwriter multi-reader (MWMR) variables and one local Boolean per processor, such that eventually, in the absence of contention, i.e. if only a single processor repeatedly performs collect, the amortized cost per each collect is a constant. With the example of Disk Paxos we show how Fast Collect can be used as a building block in wait-free algorithms.

We study wait-free computation using (read/write) shared memory under a range of assumptions on the arrival pattern of processes. We distinguish first between bounded and infinite arrival patterns, and further distinguish these models by restricting the number of arrivals minus departures, the concurrency. Under the condition that no process takes infinitely many steps without terminating, for any finite bound k > 0, we show that bounding concurrency reveals a strict hierarchy of computational models: a model in which concurrency is bounded by k + 1 is strictly weaker than the model in which concurrency is bounded by k, for all k ≱ 1. A model in which concurrency is bounded in each run, but no bound holds for all runs, is shown to be weaker than a k-bounded model for any k. The unbounded model is shown to be weaker still—in this model, finite prefixes of runs have bounded concurrency, but runs are admitted for which no finite bound holds over all prefixes. Hence, as the concurrency grows, the set of solvable problems strictly shrinks. Nevertheless, on the positive side, we demonstrate that many interesting problems (collect, snapshot, renaming) are solvable even in the infinite arrival, unbounded concurrency model.

Various timing-based mutual exclusion algorithms have been proposed that guarantee mutual exclusion if certain timing assumptions hold. In this paper, we examine how these algorithms behave when the time for the basic operations is governed by probability distributions. In particular, we are concerned with how often such algorithms succeed in allowing a processor to obtain a critical region and how this success rate depends on the random variables involved. We explore this question in the case where operation times are governed by exponential and gamma distributions, using both theoretical analysis and simulations.

Abstract. Various timing-based mutual exclusion algorithms have been proposed that guarantee mutual exclusion if certain timing assumptions hold. In this paper, we examine how these algorithms behave when the time for the basic operations is governed by probability distributions. In particular, we are concerned withhow often suchalgorithms succeed in allowing a processor to obtain a critical region and how this success rate depends on the random variables involved. We explore this question in the case where operation times are governed by exponential and gamma distributions, using both theoretical analysis and simulations.

We show that no algorithm exists for deciding whether a finite task for three or more processors is wait-free solvable in the asynchronous read-write shared-memory model. This impossibility result implies that there is no constructive (recursive) characterization of wait-free solvable tasks. It also applies to other shared-memory models of distributed computing, such as the comparison-based model.

Article Round-by-round fault detectors (extended abstract): unifying synchrony and asynchrony Share on Author: Eli Gafni Computer Science Department, University of California, Los Angeles, Los Angeles, CA Computer Science Department, University of California, Los Angeles, Los Angeles, CAView Profile Authors Info & Claims PODC '98: Proceedings of the seventeenth annual ACM symposium on Principles of distributed computingJune 1998 Pages 143–152https://doi.org/10.1145/277697.277724Online:01 June 1998Publication History 106citation686DownloadsMetricsTotal Citations106Total Downloads686Last 12 Months48Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

In a seminal paper, Chandra and Toueg showed how unreliable failure detectors could allows processors to achieve consensus in asynchronous message passing systems. Since then, other researchers have developed consensus algorithms for other systems or based on different failure detectors. Each algorithm was developed and proven independently. This paper shows how a consensus algorithm for any of the standard models can be automatically converted to run in any other. These results show more clearly how the different system models and failure detectors can be related. In addition, they may permit the development of new results for new models also through transformations. 1 Introduction The problem of achieving consensus among processors in a distributed system is fundamental in distributed computing. Unfortunately, consensus cannot be achieved in the presence of failures in completely asynchronous systems, either those with message passing [8,9] or those with shared memory [7,8,12]. Thi...

No abstract available.

No abstract available.

ongoing investigation into the computability power of proces-

This paper addresses the question of distributively computing over a strongly connected unidirectional data communication network. In unidirectional networks the existence of a communication link from one node to another does not imply the existence of a link in the opposite direction. The strong connectivity means that from every node there is a directed path to any other node. The authors assume an arbitrary topology network in which the strong connectivity is the only restriction. Four models are considered, synchronous and asynchronous, and for each node space availability, which grows as either $O(1)$ bits or $O(\log n)$ bits per incident link, where n is the total number of nodes in the network, is considered. First algorithms for two basic problems in distributed computing in data communication networks, traversal, and election, are provided. Each of these basic protocols produces two directed spanning trees rooted at a distinguished node in the network, one called in-tree, leading to the root, and the other, out-tree, leading from the root. Given these trees, the authors efficiently transform bidirectional algorithms to run on unidirectional networks, and in particular solve other problems such as the broadcast and echo [E. J. CHANG, Decentralized Algorithms in Distributed Systems, Ph.D. thesis, University of Toronto. October 19791 in a way that is more efficient $O(n^2 )$ messages) than direct transformation (which yields $O(nm)$ messages algorithm). The communication cost of the traversal and election algorithms is $O(nm + n^2 \log n)$ bits ($O(nm)$ messages and time), where m is the total number of links in the network. The traversal algorithms for unidirectional networks of finite automata achieve the same cost $O(nm + n^2 \log n)$ bits ($O(nm)$ messages and time) bits) in the asynchronous case, while in the synchronous case the communication cost of the algorithm is ($O(nm)$ bits.

This article presents a solution to the first-come, first-enabled ℓ-exclusion problem of Fischer et al. [1979]. Unlike their solution, this solution does not use powerful read-modify-write synchronization primitives and requires only bounded shared memory. Use of the concurrent timestamp system of Dolev and Shavir [1989] is key in solving the problem within bounded shared memory.

Article Generalized FLP impossibility result for t-resilient asynchronous computations Share on Authors: Elizabeth Borowsky View Profile , Eli Gafni View Profile Authors Info & Claims STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of ComputingJune 1993 Pages 91–100https://doi.org/10.1145/167088.167119Published:01 June 1993 253citation1,341DownloadsMetricsTotal Citations253Total Downloads1,341Last 12 Months82Last 6 weeks6 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

This paper introduces a general formulation of atomic snapshot memory , a shared memory partitioned into words written ( updated ) by individual processes, or instantaneously read ( scanned ) in its entirety. This paper presents three wait-free implementations of atomic snapshot memory. The first implementation in this paper uses unbounded (integer) fields in these registers, and is particularly easy to understand. The second implementation uses bounded registers. Its correctness proof follows the ideas of the unbounded implementation. Both constructions implement a single-writer snapshot memory, in which each word may be updated by only one process, from single-writer, n -reader registers. The third algorithm implements a multi-writer snapshot memory from atomic n -writer, n -reader registers, again echoing key ideas from the earlier constructions. All operations require Θ( n 2 ) reads and writes to the component shared registers in the worst case. — Authors' Abstract

This paper presents a simple and efficient building block, called slide, for constructing communication protocols in dynamic networks whose topology frequently changes. We employ slide to derive (1) an end-to-end communication protocol with optimal amortized message complexity, and (2) a general method to efficiently and systematically combine dynamic and static algorithms. (Dynamic algorithms are designed for dynamic networks, and static algorithms work in networks with stable topology.)

The problem of applying static distributed algorithms in an eventually connected network is addressed.We propose a new technique, bootstrap resynchronization,

This paper addresses the problem of distributively electing a leader in both synchronous and asynchronous complete networks. $O(n\log n)$ messages synchronous and asynchronous algorithms are presented. The time complexity of the synchronous algorithm is $O(\log n)$, while that of the asynchronous algorithm is $O(n)$. In the synchronous case, a lower bound of $\Omega (n\log n)$ on the message complexity is proven. It is also proven that any message-optimal synchronous algorithm requires $\Omega (\log n)$ time. In proving these bounds, the type of operations performed by nodes are not restricted. The bounds thus apply to general algorithms and not just to comparison-based algorithms.

An atomic snapshot memory is a shared data structure allowing concurrent processes to store information in a collection of shared registers, all of which may be read in a single atomic scan operation.This paper presents three wait-free implementations of atomic snapshot memory.Two constructions implement wait-free single-writer atomic snapshot memory from wait-free atomic single-writer, n-reader registers.A third construction implements a wait-free n-writer atomic snapshot memory from n-writer, n-reader registers.The first implementation uses unbounded

An algorithm and two lower bounds are presented for the problem of constructing and maintaining routing schemes in dynamic networks. The algorithm distributively assigns addresses to nodes and constructs routing tables in a dynamically growing tree. The resulting scheme routes data messages over the shortest path between any source and destination, assigns addresses of O(log/sup 2/n) bits to each node, and uses in its routing table O(log/sup 3/n) bits of memory per incident link, where n is the final number of nodes in the tree. The amortized communication cost of the algorithm is O(log n) messages per node. Also given are two lower bounds on the tradeoff between the quality of routing schemes (i.e. their stretch factor) and their amortized communication cost in general dynamic networks.>

Let G be a connected undirected graph in which each node corresponds to a process and two nodes are connected by an edge if the corresponding processes share a resource. We consider distributed computations in which processes are constantly demanding all of their resources in order to operate, and in which neighboring processes may not operate concurrently. We advocate that such a system is general enough for representing a large class of resource-sharing systems under heavy load. We employ a distributed scheduling mechanism based on acyclic orientations of G and investigate the amount of concurrency that it provides. We show that this concurrency is given by a number akin to G 's chromatic and multichromatic numbers, and that, among scheduling schemes which require neighbors in G to alternate in their turns to operate, ours is the one that potentially provides the greatest concurrency. However, we also show that the decision problem corresponding to optimizing concurrency is NP -complete.

Designers of autonomous distributed algorithms ( i.e., algorithms whose complete input is available before the start of execution) customarily refer to temporal ordering in describing the behavior of their algorithms-statements like "after A, task B is performed."In the absence of an explicit termination detection for A built into the algorithm such a statement should be puzzling.However, the available proof methodologies do not seem to hinge on such statements.This paper provides firm theoretical ground for such as-

This paper addresses the problem of end-toend communication over a dynamically changing network in which the sender and the receiver are not forever separated.We present several end-to-end communication protocols whose space complexity at each node is independent of either the input length or the network size.Although the time complexity of these protocols is bounded, their communication complexity is either unbounded, or exponential if an acyclic orientation of the network is given.To bound the communication complexity of the protocols, in the absence of an acyclic orientation, we assume either knowledge of the total number of nodes in the network, or that nodes have unique ids.These bounded communication-complexity protocols thus require O(logn) space per incident link at each node.In sum, we dispel the myth 'Supported by NSF Presidential Young

Most of the research in concurrency control has been based on the existence of strong synchronization primitives such as test and set. Following Lamport, recent research promoting the use of weaker primitives, “safe” rather than “atomic,” has resulted in construction of atomic registers from safe ones, in the belief that they would be useful tools for process synchronization. We argue that the properties provided by atomic operations may be too powerful, masking core difficulties of problems and leading to inefficiency. We therefore advocate a different approach, to skip the intermediate step of achieving atomicity, and solve problems directly from safe registers. Though it has been shown that “test and set” cannot be implemented from safe registers, we show how to achieve a fair solution to l-exclusion, a classical concurrency control problem previously solved assuming a very powerful form of atomic “test and set”. We do so using safe registers alone and without introducing atomicity. The solution is based on the construction of a simple novel non-atomic synchronization primitive.

This paper addresses the problem of how to adapt an algorithm designed for fixed topology networks to produce the intended results, when run in a network whose topology changes dynamically, in spite of encountering topological changes during its execution. We present a simple and unified procedure, called a reset procedure, which, when combined with the static algorithm, achieves this adaptation. The communication and time complexities of the reset procedure, per topological change, are independent of the number of topological changes and are linearly bounded by the size of the subset of the network which participates in the algorithm.

Many communication networks use adaptive shortest path routing. By this we mean that each network link is periodically assigned a length that depends on its congestion level during the preceding period, and all traffic generated between length updates is routed along a shortest path corresponding to the latest link lengths. We show that in certain situations, typical of networks involving a large number of small users and utilizing virtual circuits, this routing method performs optimally in an asymptotic sense. In other cases, shortest path routing can be far from optimal.

Article Free Access Share on Time and message bounds for election in synchronous and asynchronous complete networks Authors: Yehuda Afek Computer Science Department, University of California, Los Angeles, CA Computer Science Department, University of California, Los Angeles, CAView Profile , Eli Gafni Computer Science Department, University of California, Los Angeles, CA Computer Science Department, University of California, Los Angeles, CAView Profile Authors Info & Claims PODC '85: Proceedings of the fourth annual ACM symposium on Principles of distributed computingAugust 1985 Pages 186–195https://doi.org/10.1145/323596.323613Published:01 August 1985Publication History 27citation528DownloadsMetricsTotal Citations27Total Downloads528Last 12 Months38Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article Improvements in the time complexity of two message-optimal election algorithms Share on Author: Eli Gafni Computer Science Department, University of California, Los Angeles, CA Computer Science Department, University of California, Los Angeles, CAView Profile Authors Info & Claims PODC '85: Proceedings of the fourth annual ACM symposium on Principles of distributed computingAugust 1985 Pages 175–185https://doi.org/10.1145/323596.323612Online:01 August 1985Publication History 63citation412DownloadsMetricsTotal Citations63Total Downloads412Last 12 Months9Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

This paper presents distributed algorithms for election and traversal in strongly connected unidirectional networks. A unidirectional network consists of nodes which are processors connected by unidirectional communication links. Initially, processors differ by their identifier but are otherwise similar. The election algorithm distinguishes a single processor from all other processors. The election algorithm requires O(log n) bits of memory in each processor and has communication complexity of O(n • m+n2log n) bits. In the traversal algorithm one node initiates a token which visits all the nodes of the network and returns to the initiator. The traversal algorithm is derived from the election algorithm. It achieves the same communication complexity and uses only O(1) bits of memory in each processor.

We propose a class of algorithms for finding an optimal quasi-static routing in a communication network. The algorithms are based on Gallager's method [1] and provide methods for iteratively updating the routing table entries of each node in a manner that guarantees convergence to a minimum delay routing. Their main feature is that they utilize second derivatives of the objective function and may be viewed as approximations to a constrained version of Newton's method. The use of second derivatives results in improved speed of convergence and automatic stepsize scaling with respect to level of traffic input. These advantages are of crucial importance for the practical implementation of the algorithm using distributed computation in an environment where input traffic statistics gradually change.

We consider a network which routes on a virtual-circuit. Each virtual-circuit is associated with a session. Virtual-circuit is assigned to a session at the time the session is initiated. We address the dynamic case where new sessions arrive and old sessions terminate. We formulate an optimal control problem to deduce which virtual-circuit an incoming session will be assigned to. We then discuss various approximations to the problem and show that the heuristic rule, "route on the shortest marginal delay path", is close to optimal in an asympotic sense.

We consider the problem of maintaining communication between the nodes of a data network and a central station in the presence of frequent topological changes as, for example, in mobile packet radio networks. We argue that flooding schemes have significant drawbacks for such networks, and propose a general class of distributed algorithms for establishing new loop-free routes to the station for any node left without a route due to changes in the network topology. By virtue of built-in redundancy, the algorithms are typically activated very infrequently and, even when they are, they do not involve any communication within the portion of the network that has not been materially affected by a topological change.