Abstract A novel long-lived distributed problem, called Team Formation (TF) , is introduced together with a message- and time-efficient randomized algorithm. The problem is defined over the asynchronous model with a complete communication graph, using bounded size messages, where a certain fraction of the nodes may experience a generalized, strictly stronger, version of initial failures. The goal of a TF algorithm is to assemble tokens injected by the environment, in a distributed manner, into teams of size $$\sigma $$ σ , where $$\sigma $$ σ is a parameter of the problem. The usefulness of TF is demonstrated by using it to derive efficient algorithms for many distributed problems. Specifically, we show that various (one-shot as well as long-lived) distributed problems reduce to TF. This includes well-known (and extensively studied) distributed problems such as several versions of leader election and threshold detection. For example, we are the first to break the linear message complexity bound for asynchronous implicit leader election. We also improve the time complexity of message-optimal algorithms for asynchronous explicit leader election. Other distributed problems that reduce to TF are new ones, including matching players in online gaming platforms, a generalization of gathering, constructing a perfect matching in an induced subgraph of the complete graph, and more. To complement our positive contribution, we establish a tight lower bound on the message complexity of TF algorithms.

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.

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).

A novel long-lived distributed problem, called Team Formation (TF), is introduced together with a message- and time-efficient randomized algorithm. The problem is defined over the asynchronous model with a complete communication graph, using bounded size messages, where a certain fraction of the nodes may experience a generalized, strictly stronger, version of initial failures. The goal of a TF algorithm is to assemble tokens injected by the environment, in a distributed manner, into teams of size σ, where σ is a parameter of the problem. The usefulness of TF is demonstrated by using it to derive efficient algorithms for many distributed problems. Specifically, we show that various (one-shot as well as long-lived) distributed problems reduce to TF. This includes well-known (and extensively studied) distributed problems such as several versions of leader election and threshold detection. For example, we are the first to break the linear message complexity bound for asynchronous implicit leader election. We also improve the time complexity of message-optimal algorithms for asynchronous explicit leader election. Other distributed problems that reduce to TF are new ones, including matching players in online gaming platforms, a generalization of gathering, constructing a perfect matching in an induced subgraph of the complete graph, and more. To complement our positive contribution, we establish a tight lower bound on the message complexity of TF algorithms.

Many exceptionally high-quality doctoral dissertations were submitted for the 2022 Principles of Distributed Computing Doctoral Dissertation Award. After careful long deliberation, the award committee decided to share the award among two:

Assuming that there is an a priori agreement between processes on the names of shared memory locations, as is done in almost all the publications on concurrent shared memory algorithms, is tantamount to assuming that agreement has already been solved at a lower level. It is intriguing to figure out how coordination can be achieved without relying on such lower-level agreement. To better understand the new model, we first design new algorithms for several important problems, such as mutual exclusion, consensus, election, and renaming. Then, we prove space lower bounds, impossibility results, and resolve two foundational long-standing open problems in the context of anonymous memory systems. Using these results, we identify fundamental differences between the standard shared memory model and the strictly weaker anonymous shared memory model. Besides enabling us to understand better the intrinsic limits for coordinating the actions of asynchronous processes, the new model has been shown to be useful in modeling biologically inspired distributed computing methods, especially those based on ideas from molecular biology.

Group mutual exclusion (GME), introduced by Joung in 1998, is a natural synchronization problem that generalizes the classical mutual exclusion and readers and writers problems. In GME a process requests a session before entering its critical section; processes are allowed to be in their critical sections simultaneously provided they have requested the same session. We present a GME algorithm that (1) is the first to achieve a constant Remote Memory Reference (RMR) complexity for both cache coherent and distributed shared memory machines; and (2) is the first that can be accessed by arbitrarily many dynamically allocated processes and with arbitrarily many session names. Neither of the existing GME algorithms satisfies either of these two important properties. In addition, our algorithm has constant space complexity per process and satisfies the two strong fairness properties, first-come-first-served and first-in-first-enabled. Our algorithm uses an atomic instruction set supported by most modern processor architectures, namely: read, write, fetch-and-store and compare-and-swap.

An anonymous shared memory REG can be seen as an array of atomic registers such that there is no a priori agreement among the processes on the names of the registers. As an example a very same physical register can be known as REG[x] by a process p and as REG[y] (where y ≠ x) by another process q. Moreover, the register known as REG[a] by a process p and the register known as REG[b] by a process q can be the same physical register. It is assumed that each process has a unique identifier that can only be compared for equality. This article is on solving the d-election problem, in which it is required to elect at least one and at most d leaders, in such an anonymous shared memory system. We notice that the 1-election problem is the familiar leader election problem. Let n be the number of processes and m the size of the anonymous memory (number of atomic registers). The article shows that the condition gcd(m, n) ≤ d is necessary and sufficient for solving the d-election problem, where communication is through read/write or read+modify+write registers. The algorithm used to prove the sufficient condition relies on Bezout's Identity - a Diophantine equation relating numbers according to their Greatest Common Divisor. Furthermore, in the process of proving the sufficient condition, it is shown that 1-leader election can be solved using only a single read/write register (which refutes a 1989 conjecture stating that three non-anonymous registers are necessary), and that the exact d-election problem, where exactly d leaders must be elected, can be solved if and only if gcd(m, n) divides d.

The notion of an anonymous shared memory, introduced by Taubenfeld in PODC 2017, considers that processes use different names for the same memory location. As an example, a location name A used by a process p and a location name B ≠ A used by another process q can correspond to the very same memory location X, and similarly for the names B used by p and A used by q which may (or may not) correspond to the same memory location Y ≠ X. In this context, the PODC paper presented a 2-process symmetric deadlock-free mutual exclusion (mutex) algorithm and a necessary condition on the size m of the anonymous memory for the existence of such an n-process algorithm. This condition states that m must be belongs to M(n) {1} where M(n)= {m: ∀ ℓ: (1) < ℓ ≤ n: gcd(ℓ,m)=1). Symmetric means here that,process identities define a specific data type which allows a process to check only if two identities are equal or not.

The Dijkstra Prize Committee has decided to grant the 2018 Edsger W. Dijkstra Prize in Distributed Computing to Bowen Alpern and Fred B. Schneider for their paper:

Two local-spinning queue-based mutual exclusion algorithms are presented that have several de- sired properties: (1) their exit codes are wait-free, (2) they satisfy FIFO fairness, (3) they have constant RMR complexity in both the CC and the DSM models, (4) it is not assumed that the number of processes, n, is a priori known, that is, processes may appear or disappear intermit- tently, (5) they use only O(n) shared memory locations, and (6) they make no assumptions on what and how memory is allocated. The algorithms are inspired by J. M. Mellor-Crummey and M. L. Scott famous MCS queue- based algorithm [13] which, except for not having a wait-free exit code, satisfies similar properties. A drawback of the MCS algorithm is that executing the exit code (i.e., releasing a lock) requires spinning – a process executing its exit code may need to wait for the process that is behind it in the queue to take a step before it can proceed. The two new algorithms overcome this drawback while preserving the simplicity and elegance of the original algorithm. Our algorithms use exactly the same atomic instruction set as the original MCS algorithm, namely: read, write, fetch-and-store and compare-and-swap. In our second algorithm it is possible to recycle memory locations so that if there are L mutual exclusion locks, and each process accesses at most one lock at a time, then the algorithm needs only O(L + n) space, as compared to O(Ln) needed by our first algorithm.

Assuming that there is an a priori agreement between processes on the names of shared memory locations, as done in almost all the publications on shared memory algorithms, is tantamount to assuming that agreement has already been solved at the lower-level. From a theoretical point of view, it is intriguing to figure out how coordination can be achieved without relying on such lower-level agreement. In order to better understand the new model, we have designed new algorithms without relying on such a priori lower-level agreement, and proved space lower bounds and impossibility results for several important problems, such as mutual exclusion, consensus, election and renaming. Using these results, we identify fundamental differences between the standard model where there is a lower-level agreement about the shared register's names and the strictly weaker model where there is no such agreement.

We consider an asynchronous shared memory system of n processes where processes may experience weak crash failures. A crash m-failure is a crash failure of a process that may occurs only while the point contention is at most m. It is known that there is no consensus algorithm for n processes using registers that can tolerate even a single crash n-failure. Is there a consensus algorithm for n processes using registers that can tolerate a single crash (n-1)-failure? It is known that there is no k-set consensus algorithm for n>k processes using registers that can tolerate k crash n-failures. How may crash (n-\ell)-failures can a k-set consensus algorithm using registers tolerate, as a function of n, k and l. Answers to these questions follow from our results regarding the ability to tolerate weak crash failures.

A notion of a universal construction suited to distributed computing has been introduced by M. Herlihy in his celebrated paper "Wait-free synchronization" (ACM TOPLAS, 1991). A universal construction is an algorithm that can be used to wait-free implement any object defined by a sequential specification. Herlihy's paper shows that the basic system model, which supports only atomic read/write registers, has to be enriched with consensus objects to allow the design of universal constructions.

The traditional notion of fault tolerance requires that all the correct participating processes eventually terminate, and thus, is not sensitive to the number of correct processes that should properly terminate as a result of failures. Intuitively, an algorithm that in the presence of any number of faults always guarantees that all the correct processes except maybe one properly terminate, is more resilient to faults than an algorithm that in the presence of a single fault does not even guarantee that a single correct process ever terminates. However, according to the standard notion of fault tolerance both algorithms are classified as algorithms that can not tolerate a single fault.

Wait-freedom and obstruction-freedom have received a lot of attention in the literature. These are symmetric progress conditions in the sense that they consider all processes as being "equal". Wait-freedom has allowed to rank the synchronization power of objects in presence of process failures, while (the weaker) obstruction-freedom allows for simpler and more efficient object implementations.

A new type of shared object, called timed register, is proposed and used to design indulgent timing-based algorithms. A timed register generalizes the notion of an atomic register as follows: if a process invokes two consecutive operations on the same timed register which are a read followed by a write, then the write operation is executed only if it is invoked at most d time units after the read operation, where d is defined as part of the read operation. In this context, a timing-based algorithm is an algorithm whose correctness relies on the existence of a bound Δ such that any pair of consecutive constrained read and write operations issued by the same process on the same timed register are separated by at most Δ time units. An indulgent algorithm is an algorithm that always guarantees the safety properties, and ensures the liveness property as soon as the timing assumptions are satisfied. The usefulness of this new type of shared object is demonstrated by presenting simple and elegant indulgent timing-based algorithms that solve the mutual exclusion, l-exclusion, adaptive renaming,test&set, and consensus problems. Interestingly, timed registers are universal objects in systems with process crashes and transient timing failures (i.e., they allow building any concurrent object with a sequential specification). The paper also suggests connections with schedulers and contention managers.

Timing failures refer to a situation where the environment in which a system operates does not behave as expected regarding the timing assumptions, that is, the timing constraints are not met. In the immense body of work on the designing fault-tolerant systems, the type of failures that are usually considered are, process failures, link failures, messages loss and memory failures; and it is usually (implicitly) assumed that there are no timing failures. In this paper we investigate the ability to recover automatically from transient timing failures. We introduce and formally define the concept of algorithms that are resilient to timing failures, and demonstrate the importance of the new concept by presenting consensus and mutual exclusion algorithms, using atomic registers only, that are resilient to timing failures.

No abstract available.

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.

Article Sequentially consistent versus linearizable counting networks Share on Authors: Marios Mavronicolas Department of Computer Science and Engineering, University of Connecticut, Storrs, CT Department of Computer Science and Engineering, University of Connecticut, Storrs, CTView Profile , Michael Merritt AT&T Labs - Research, 180 Park Avenue, Florham Park, NJ AT&T Labs - Research, 180 Park Avenue, Florham Park, NJView Profile , Gadi Taubenfeld The Open University, 16 Klausner St., Tel-Aviv 61392, Israel The Open University, 16 Klausner St., Tel-Aviv 61392, IsraelView Profile Authors Info & Claims PODC '99: Proceedings of the eighteenth annual ACM symposium on Principles of distributed computingMay 1999 Pages 133–142https://doi.org/10.1145/301308.301342Online:01 May 1999Publication History 5citation224DownloadsMetricsTotal Citations5Total Downloads224Last 12 Months1Last 6 weeks0 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

The problem of computing with faulty shared bits is addressed. The focus is on constructing a reliable test&set bit from a collection of test&set bits of which some may be faulty. Faults are modeled by allowing operations on the faulty bits to return a special distinguished value, signaling that the operation may not have taken place. Such faults are called omission faults. Some of the constructions are required to be gracefully degrading for omission. That is, if the bound on the number of component bits which fail is exceeded, the constructed bit may suffer faults, but only faults which are no more severe than those of the components; and the constructed bit behaves as intended if the number of component bits which fail does not exceed that bound. Several efficient constructions are presented, and bounds on the space required are given. Our constructions for omission faults also apply to other fault models.

We consider the problem of implementing atomic operations on multiple shared memory objects, in systems which directly support only single-object atomic operations.Our motivation is to design algorithms that exhibit both low contention between concurrent operations and a high level of concurrency, by disentangling long chains of conflicting operations.That is, operations that access widely disjoint parts of a data structure, or are widely separated in time, should not interfere with each other.The algorithm reported here extends and is based on the work of Attiya and Dagan [A D96], where a nonblocking solution is presented for two-object atomic operations.For any number, k, we present a wait-free solution for atomically accessing up to k objects.Notions of local contention and local step complexity are defined, and it is shown that the solution has low local contention and local step complexity.Relations between multi-objects and the familiar resource allocation problem are explored-the algorithm presented also provides a solution to the resource allocation problem. Int roduct ionConsider a data structure stored in shared memory and accessed concurrently by n processes.The shared data structure is abstracted w an array of memory locations.To perform its operation, a process needs to get exclusive access to the set of locations necessary to carry out qComputer

We consider concurrent systems in which there is an unknown upper bound on memory access time. Such a model is inherently different from the asynchronous model, where no such bound exists, and also from timing-based models, where such a bound exists and is known a priori. The appeal of our model lies in the fact that while it abstracts from implementation details, it is a better approximation of real concurrent systems than the asynchronous model. Furthermore, it is stronger than the asynchronous model, enabling us to design algorithms for problems that are unsolvable in the asynchronous model. Two basic synchronization problems, consensus and mutual exclusion, are investigated in a shared-memory environment that supports atomic read/write registers. We show that $\Theta(\Delta\frac{\log \Delta}{\log\log \Delta})$ is an upper and lowerbound on the time complexity of consensus, where $\Delta$ is the (unknown) upper bound on memory access time. For the mutual exclusion problem, we design an efficient algorithm that takes advantage of the fact that some upper bound on memory access time exists. The solutions for both problems are even more efficient in the absence of contention, in which case their time complexity is a constant.

Article The power of multi-objects (extended abstract) Share on Authors: Yehuda Afek Computer Science Dept., Tel-Aviv Univ., Israel 69978, and AT&T Bell Labs. Computer Science Dept., Tel-Aviv Univ., Israel 69978, and AT&T Bell Labs.View Profile , Michael Merritt AT&T Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJ AT&T Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJView Profile , Gadi Taubenfeld The Open Univ., 16 Klausner st., P.O.B. 39328, Tel-Aviv 61392, Israel, and AT&T Bell Labs. The Open Univ., 16 Klausner st., P.O.B. 39328, Tel-Aviv 61392, Israel, and AT&T Bell Labs.View Profile Authors Info & Claims PODC '96: Proceedings of the fifteenth annual ACM symposium on Principles of distributed computingMay 1996 Pages 213–222https://doi.org/10.1145/248052.248096Published:01 May 1996 6citation173DownloadsMetricsTotal Citations6Total Downloads173Last 12 Months0Last 6 weeks0 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

The problem of computing with faulty shared bits is addressed. The focus is on constructing a reliable tests and the constructed bit behaves as intended if the number of component bits which fail does not exceed that bound. Several efficient constructions are presented, and bounds on the space required are given. Our constructions for omission faults also apply to other fault models.

We study a new problem—the wakeup problem—that seems to be fundamental in distributed computing. We present efficient solutions to the problem and show how these solutions can be used to solve the consensus problem, the leader-election problem, and other related problems. The main question we try to answer is “How much memory is needed to solve the wakeup problem?” We assume a model that captures important properties of real systems that have been largely ignored by previous work on cooperative problems.

This paper investigates the effects of the failure of shared objects on distributed systems.First the notion of a faulty shared object is introduced.Then upper and lower bounds on the space complexity of implementing reliable shared objects are provided, Shared object failures are modeled as instantaneous and arbitraty changes to the state of the object.Several constructions of nonfaulty wait-free shared objects from a set of shared objects, some of which may suffer any number of faults, are presented.Three of these constructions are: (1) A reliable atomic read/write register from 20~+ 8 atomic read/write registers ~of which may be faulty, (2) a reliable test& set register for n processes from n + 10 primitive test & set registers, one of which may be faulty, and 3n + 13 reliable atomic registers, and (3) a reliable consensus object from 2f + 1 read-modify-write registers when f of these may be faulty.Using these constructions a universal construction of any linearizable shared object from a set of either A preliminary version of the results presented in this paper appeared in

Worst-case time complexity is a measure of the maximumtime needed to solve a problem over all runs. Contention-free time complexity indicates the maximum time needed when a process executes by itself, without competition from other processes. Since contention is rare in well-designed systems, it is important to design algorithms which perform well in the absence of contention. We study the contention-free time complexity of shared memory algorithms using two measures: step complexity, which counts the number of accesses to shared registers; and register complexity, which measures the number of different registers accessed. Depending on the system architecture, one of the two measures more accurately reflects the elapsed time. We provide lower and upper bounds for the contention-free step and register complexity of solving the mutual exclusion problem as a function of the number of processes and the size of the largest register that can be accessed in one atomic step. We also present bo...

We consider concurrent systems in which there is an unknown upper bound on memory access time. Such a model is inherently different from asynchronous model where no such bound exists, and also from timing-based models where such a bound exists and is known a priori. The appeal of our model lies in the fact that while it abstracts from implementation details, it is a better approximation of real concurrent systems compared to the asynchronous model. Furthermore, it is stronger than the asynchronous model enabling us to design algorithms for problems that are unsolvable in the asynchronous model. Two basic synchronization problems, consensus and mutual exclusion, are investigated in a shared memory environment that supports atomic read/write registers. We show that \\Theta(\\Delta log \\Delta log log \\Delta ) is an upper and lower bound on the time complexity of consensus, where \\Delta is the (unknown) upper bound on memory access time. For the mutual exclusion problem, we design an effic...

A counting protocol (mod m) consists of shared memory bits -referred to as the counter -and of a procedure for incrementing the counter value by 1 (mod m).The procedure may be executed by many processes concurrently.It is required to satisfy a very weak correctness requirement, namely: the counter is required to show a correct value only in quiescent states -states in which no process is incrementing the counter.Special cases of counting protocols are "counting networks" [AHS91] and "concurrent counters" [MTY92].We consider the problem of implementing a wait-free counting protocol, assuming that the basic atomic operation of a process is a read-modify-write on a single bit.Let ~lip(.%)be the maximum number of times a single increment operation changes the counter bits in a counting protocol Pr.Our main result is: In any waitfree counting protocol Pr which counts modulo m, m divides 2f~@tp'J.Thus, flip(Pr) z log m and m is a power of 2. This result provides interesting generalizations of lower bounds and impossibility results for counting and smoothing networks, Recently there was much interest in the implementation of counters in a concurrent environment where many processes may try to access the

This paper addresses problems which arise in the synchronization and coordination of distributed systems which employ unreliable shared memory. We present algorithms which solve the consensus problem, and which simulate reliable shared-memory objects, despite the fact that the available memory objects (e.g. read/write registers, test-and-set registers, read-modify-write registers) may be faulty.

Our purpose is to implement clocks and, in general, counters in a shared memory environment. A concurrent counter is a counter that can be incremented and read, possibly at the same time by many processes. We study counters that achieve high level of concurrency and thus are likely to reduce memory contention; require only weak atomicity and thus are easy to implement; do not depend on the initial state of the memory and hence are more robust to memory changes; and are wait-free - one process cannot prevent another process from finishing its increment or read operations - and thus can tolerate any number of process failures. We concentrate on providing upper and lower bounds on the space complexity of the counters studied.

A fast mutual exclusion algorithm where only five accesses to the shared memory are needed in order to enter a critical section in the absence of contention is presented. In the presence of contention, the winning process may need to delay itself for 3* Delta time units, where Delta is an upper bound on the time taken by the slowest process to execute a statement involving an access to the shared memory. It is also proven that there is not two (or more) process mutual exclusion algorithm with an upper bound on the number of times a winning process needs to access the shared memory in order to enter its critical section in the presence of contention. However, under the assumption that busy-waiting counts as just one step, the authors present, for every fixed parameter k, an algorithm with the property that from a state where no process tries to enter its critical section, as long as the number of contenders does not exceed k, the time complexity of the winning process is a linear function of k. Finally, the ideas from the mutual exclusion algorithm are used to implement a fast and simple consensus algorithm.>

Article Knowledge in shared memory systems (preliminary version) Share on Authors: Michael Merritt L&T Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJ L&T Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJView Profile , Gadi Taubenfeld L&T Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJ L&T Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJView Profile Authors Info & Claims PODC '91: Proceedings of the tenth annual ACM symposium on Principles of distributed computingJuly 1991 Pages 189–200https://doi.org/10.1145/112600.112617Online:01 July 1991Publication History 8citation183DownloadsMetricsTotal Citations8Total Downloads183Last 12 Months5Last 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

We present three axioms capturing the nature of asynchronous message passing systems and five axioms defining resilient consensus protocols. We prove that there does not exist an asynchronous resilient consensus protocol by showing that the set of eight axioms is inconsistent.

We study a new problem, the wakeup problem, that seems to be very fundamental in distributed computing.We present efficient solutions to the problem and show how these solutions can be used to solve the consensus problem, the leader election problem, and other related problems.The main question we try to answer is, how much memory is needed to solve the wakeup problem?We assume a model that captures important properties of real systems that have been largely ignored by previous work on cooperative problems.

We present a deterministic leader election protocol that can tolerate up to n−1 undetectable initial failures, where n is the number of processes. We assume an asynchronous shared memory model that supports only single writer and multi readers regular registers

The importance of the notion of knowledge in reasoning about distributed systems has been recently pointed out by several works. It has been argued that a distributed computation can be understood and analyzed by considering how it affects the state of knowledge of the system. We show that there are a variety of definitions which can reasonably be applied to what a process can know about he global state. We also move beyond the semantic definitions, and present the first proof methods for proving knowledge asser-tions. Both shared memory and message passing models are considered. 1.