We analyze the convergence of the k-opinion Undecided State Dynamics (USD) in the population protocol model. For k=2 opinions it is well known that the USD reaches consensus with high probability within O(n log n) interactions. Proving that the process also quickly solves the consensus problem for k > 2 opinions has remained open, despite analogous results for larger k in the related parallel gossip model. In this paper we prove such convergence: under mild assumptions on k and on the initial number of undecided agents we prove that the USD achieves plurality consensus within O(kn log n) interactions with high probability, regardless of the initial bias. Moreover, if there is an initial additive bias of at least Ω (√n log n) we prove that the initial plurality opinion wins with high probability, and if there is a multiplicative bias the convergence time is further improved. Note that this is the first result for k > 2 for the USD in the population protocol model. Furthermore, it is the first result for the unsynchronized variant of the USD with k > 2 which does not need any initial bias.

Abstract. We introduce extension-based proofs, a class of impossibility proofs that includes valency arguments. They are modelled as an interaction between a prover and a protocol. Using proofs based on combinatorial topology, it has been shown that it is impossible to deterministically solve [Formula: see text]-set agreement among [Formula: see text] processes or approximate agreement on a cycle of length 4 among [Formula: see text] processes in a wait-free manner in asynchronous models where processes communicate using objects that can be constructed from shared registers. However, it was unknown whether proofs based on simpler techniques were possible. We show that these impossibility results cannot be obtained by extension-based proofs in the iterated snapshot model and, hence, extension-based proofs are limited in power.

Network resource reservation systems are being developed and deployed, driven by the demand and substantial benefits of providing performance predictability for modern distributed applications. However, existing systems suffer limitations: They either are inefficient in finding the optimal resource reservation, or cause private information (e.g., from the network infrastructure) to be exposed (e.g., to the user). In this paper, we design BoxOpt, a novel system that leverages efficient oracle construction techniques in optimization and learning theory to automatically, and swiftly learn the optimal resource reservations without exchanging any private information between the network and the user. In BoxOpt, we first model the simple reservation interface adopted in most reservation systems as a resource membership oracle. Second, we develop an efficient algorithm that constructs a resource separation oracle by a linear number of calls on resource membership oracle. Third, we develop a generic framework to construct a resource optimization oracle by iteratively calling the resource separation oracle, and then develop three novel, efficient algorithms under this generic framework, the best of which computes the optimal resource reservation by a linear number of calls on resource separation oracle. As such, BoxOpt can discover the optimal resource reservation with O(n2) calls on the resource membership oracle. We implement a prototype of BoxOpt with and demonstrate its efficiency and efficacy via extensive experiments using real network topology and a 7-day trace from a large operational federation network. Results show that (1) BoxOpt has a 100% correctness ratio by comparing with a state-of-the-art optimization solver, and (2) for 90% of requests, BoxOpt learns the optimal resource reservation within 10 seconds.

Population protocols are a class of algorithms for modeling distributed computation in networks of finite-state agents communicating through pairwise interactions. Their suitability for analyzing numerous chemical processes has motivated the adaptation of the original population protocol framework to better model these chemical systems. In this paper, we further the study of two such adaptations in the context of solving approximate majority: persistent-state agents (or catalysts) and spontaneous state changes (or leaks). Based on models considered in recent protocols for populations with persistent-state agents, we assume a population with $n$ catalytic input agents and $m$ worker agents, and the goal of the worker agents is to compute some predicate over the states of the catalytic inputs. We call this model the Catalytic Input (CI) model. For $m = Θ(n)$, we show that computing the exact majority of the input population with high probability requires at least $Ω(n^2)$ total interactions, demonstrating a strong separation between the CI model and the standard population protocol model. On the other hand, we show that the simple third-state dynamics of Angluin et al. for approximate majority in the standard model can be naturally adapted to the CI model: we present such a constant-state protocol for the CI model that solves approximate majority in $O(n \log n)$ total steps w.h.p. when the input margin is $Ω(\sqrt{n \log n})$. We then show the robustness of third-state dynamics protocols to the transient leaks events introduced by Alistarh et al. In both the original and CI models, these protocols successfully compute approximate majority with high probability in the presence of leaks occurring at each step with probability $β\leq O\left(\sqrt{n \log n}/n\right)$, exhibiting a resilience to leaks similar to that of Byzantine agents in previous works.

We introduce extension-based proofs, a class of impossibility proofs that includes valency arguments. They are modelled as an interaction between a prover and a protocol. Using proofs based on combinatorial topology, it has been shown that it is impossible to deterministically solve k-set agreement among n > k ≥ 2 processes in a wait-free manner. However, it was unknown whether proofs based on simpler techniques were possible. We explain why this impossibility result cannot be obtained by an extension-based proof and, hence, extension-based proofs are limited in power.

The standard population protocol model assumes that when two agents interact, each observes the entire state of the other. We initiate the study of message complexity for population protocols, where an agent’s state is divided into an externally-visible message and externally-hidden local state. We consider the case of O(1) message complexity. When time is unrestricted, we obtain an exact characterization of the stably computable predicates based on the number of internal states s(n): If s(n) = o(n) then the protocol computes semilinear predicates (unlike the original model, which can compute non-semilinear predicates with s(n) = O(log n)), and otherwise it computes a predicate decidable by a nondeterministic O(n log s(n))-space-bounded Turing machine. We then introduce novel O(polylog(n)) expected time protocols for junta/leader election and general purpose broadcast correct with high probability, and approximate and exact population size counting correct with probability 1. Finally, we show that the main constraint on the power of bounded-message-size protocols is the size of the internal states: with unbounded internal states, any computable function can be computed with probability 1 in the limit by a protocol that uses only 1-bit messages.

It is impossible to deterministically solve wait-free consensus in an asynchronous system. The classic proof uses a valency argument, which constructs an infinite execution by repeatedly extending a finite execution. We introduce extension-based proofs, a class of impossibility proofs that are modelled as an interaction between a prover and a protocol and that include valency arguments.

We consider the problem of implementing randomized wait-free consensus from max registers under the assumption of an oblivious adversary. We show that max registers solve m-valued consensus for arbitrary m in expected O(log^* n) steps per process, beating the Omega(log m/log log m) lower bound for ordinary registers when m is large and the best previously known O(log log n) upper bound when m is small. A simple max-register implementation based on double-collect snapshots translates this result into an O(n log n) expected step implementation of m-valued consensus from n single-writer registers, improving on the best previously-known bound of O(n log^2 n) for single-writer registers.

High-Ievel programming and programmable data paths are two key capabilities of software-defined networking (SDN). A fundamental problem linking these two capabilities is whether a given high-level SDN program can be realized onto a given low-level SDN datapath structure. Considering all high-level programs that can be realized onto a given datapath as the programming capacity of the datapath, we refer to this problem as the SDN data path programming capacity problem. In this paper, we conduct the first study on the SDN datapath programming capacity problem, in the general setting of high-level, datapath oblivious, algorithmic SDN programs and state-of-art multi-table SDN data path pipelines. In particular, considering datapath-oblivious SDN programs as computations and datapath pipelines as computation capabilities, we introduce a novel framework called SDN characterization junctions, to map both SDN programs and datapaths into a unifying space, deriving the first rigorous result on SDN datapath programming capacity. We not only prove our results but also conduct realistic evaluations to demonstrate the tightness of our analysis.

Population protocols are a popular model of distributed computing, in which n agents with limited local state interact randomly, and cooperate to collectively compute global predicates. Inspired by recent developments in DNA programming, an extensive series of papers, across different communities, has examined the computability and complexity characteristics of this model. Majority, or consensus, is a central task in this model, in which agents need to collectively reach a decision as to which one of two states A or B had a higher initial count. Two metrics are important: the time that a protocol requires to stabilize to an output decision, and the state space size that each agent requires to do so. It is known that majority requires Ω(log log n) states per agent to allow for fast (poly-logarithmic time) stabilization, and that O(log2 n) states are sufficient. Thus, there is an exponential gap between the space upper and lower bounds for this problem. This paper addresses this question. On the negative side, we provide a new lower bound of Ω(log n) states for any protocol which stabilizes in O(n1–c) expected time, for any constant c > 0. This result is conditional on monotonicity and output assumptions, satisfied by all known protocols. Technically, it represents a departure from previous lower bounds, in that it does not rely on the existence of dense configurations. Instead, we introduce a new generalized surgery technique to prove the existence of incorrect executions for any algorithm which would contradict the lower bound. Subsequently, our lower bound also applies to general initial configurations, including ones with a leader. On the positive side, we give a new algorithm for majority which uses O(log n) states, and stabilizes in O(log2 n) expected time. Central to the algorithm is a new leaderless phase clock technique, which allows agents to synchronize in phases of Θ(n log n) consecutive interactions using O(log n) states per agent, exploiting a new connection between population protocols and power-of-two-choices load balancing mechanisms. We also employ our phase clock to build a leader election algorithm with a state space of size O(log n), which stabilizes in O(log2 n) expected time.

Many fundamental problems in shared-memory distributed computing, including mutual exclusion [James E. Burns and Nancy A. Lynch, 1993], consensus [Leqi Zhu, 2016], and implementations of many sequential objects [Prasad Jayanti et al., 2000], are known to require linear space in the worst case. However, these lower bounds all work by constructing particular executions for any given algorithm that may be both very long and very improbable. The significance of these bounds is justified by an assumption that any space that is used in some execution must be allocated for all executions. This assumption is not consistent with the storage allocation mechanisms of actual practical systems. We consider the consequences of adopting a per-execution approach to space complexity, where an object only counts toward the space complexity of an execution if it is used in that execution. This allows us to show that many known randomized algorithms for fundamental problems in shared-memory distributed computing have expected space complexity much lower than the worst-case lower bounds, and that many algorithms that are adaptive in time complexity can also be made adaptive in space complexity. For the specific problem of mutual exclusion, we develop a new algorithm that illustrates an apparent trade-off between low expected space complexity and low expected RMR complexity. Whether this trade-off is necessary is an open problem. For some applications, it may be helpful to pay only for objects that are updated, as opposed to those that are merely read. We give a data structure that requires no space to represent objects that are not updated at the cost of a small overhead on those that are.

We consider the problem of consensus in the challenging classic model. In this model, the adversary is adaptive; it can choose which processors crash at any point during the course of the algorithm. Further, communication is via asynchronous message passing: there is no known upper bound on the time to send a message from one processor to another, and all messages and coin flips are seen by the adversary. We describe a new randomized consensus protocol with expected message complexity $$O( n^2 \log ^2 n )$$ when fewer than n / 2 processes may fail by crashing. This is an almost-linear improvement over the best previously known protocol, and within logarithmic factors of a known $$\Omega ( n^2 )$$ message lower bound. The protocol further ensures that no process sends more than $$O( n \log ^3 n )$$ messages in expectation, which is again within logarithmic factors of optimal. We also present a generalization of the algorithm to an arbitrary number of failures t, which uses expected $$O( n t + t^2 \log ^{2} t )$$ total messages. Our approach is to build a message-efficient, resilient mechanism for aggregating individual processor votes, implementing the message-passing equivalent of a weak shared coin. Roughly, in our protocol, a processor first announces its votes to small groups, then propagates them to increasingly larger groups as it generates more and more votes. To bound the number of messages that an individual process might have to send or receive, the protocol progressively increases the weight of generated votes. The main technical challenge is bounding the impact of votes that are still “in flight” (generated, but not fully propagated) on the final outcome of the shared coin, especially since such votes might have different weights. We achieve this by leveraging the structure of the algorithm, and a technical argument based on martingale concentration bounds. Overall, we show that it is possible to build an efficient message-passing implementation of a shared coin, and in the process (almost-optimally) solve the classic consensus problem in the asynchronous message-passing model.

We suggest a template that reveals the structure of many consensus algorithms as a generic procedure. The template builds on a new object, vacillate-adopt-commit which is an extension of the well known adopt-commit object. In addition we extend Aspnes's conciliator object to a new object that we call a reconciliator. The consensus algorithm template works in rounds of alternating vacillate-adopt-commit and reconciliator operations. The vacillate-adopt-commit object observes the processors' preferences and suggests a preference output with a measure of confidence vacillate, adopt or commit) on the preference. The reconciliator ensures termination, by providing new preferences for the processors. We show how several key consensus algorithms exactly fit our template. Here we demonstrate the decomposition of Ben-Or's randomized algorithm. The decomposition of the Phase King Byzantine and the Paxos algorithm are given in the full paper [1]. We analyze and compare our template based on vacillate-adopt-commit and reconciliator objects to previous work [3,5], suggesting a decomposition of consensus based on adopt-commit and conciliator objects. We claim that the three return values of vacillate-adopt-commit more accurately describe existing algorithms.

Population protocols are required to converge to the correct answer, and are subject to a fairness condition that guarantees eventual progress, but generally have no internal mechanism for detecting when this progress has occurred. We define an extension to the standard population protocol that provides each agent with a clock signal that indicates when the agent has waited long enough. To simplify the model, we represent "long enough" as an infinite time interval, and treat a clocked population protocol as operating over transfinite time. This gives a clean theoretical model that we show how to translate back into finite real-world executions where the clock ticks whenever the underlying protocol is looping or stuck.

Population protocols are a popular model of distributed computing, in which randomly-interacting agents with little computational power cooperate to jointly perform computational tasks. Inspired by developments in molecular computation, and in particular DNA computing, recent algorithmic work has focused on the complexity of solving simple yet fundamental tasks in the population model, such as leader election (which requires convergence to a single agent in a special “leader” state), and majority (in which agents must converge to a decision as to which of two possible initial states had higher initial count). Known results point towards an inherent trade-off between the time complexity of such algorithms, and the space complexity, i.e. size of the memory available to each agent. In this paper, we explore this trade-off and provide new upper and lower bounds for majority and leader election. First, we prove a unified lower bound, which relates the space available per node with the time complexity achievable by a protocol: for instance, our result implies that any protocol solving either of these tasks for n agents using O(log log n) states must take Ω(n/polylogn) expected time. This is the first result to characterize time complexity for protocols which employ super-constant number of states per node, and proves that fast, poly-logarithmic running times require protocols to have relatively large space costs. On the positive side, we give algorithms showing that fast, poly-logarithmic convergence time can be achieved using O (log2 n) space per node, in the case of both tasks. Overall, our results highlight a time complexity separation between O (log log n) and Θ(log2 n) state space size for both majority and leader election in population protocols, and introduce new techniques, which should be applicable more broadly.

Population protocols are a popular model of distributed computing, in which randomly-interacting agents with little computational power cooperate to jointly perform computational tasks. Inspired by developments in molecular computation, and in particular DNA computing, recent algorithmic work has focused on the complexity of solving simple yet fundamental tasks in the population model, such as leader election (which requires stabilization to a single agent in a special "leader" state), and majority (in which agents must stabilize to a decision as to which of two possible initial states had higher initial count). Known results point towards an inherent trade-off between the time complexity of such algorithms, and the space complexity, i.e. size of the memory available to each agent. In this paper, we explore this trade-off and provide new upper and lower bounds for majority and leader election. First, we prove a unified lower bound, which relates the space available per node with the time complexity achievable by a protocol: for instance, our result implies that any protocol solving either of these tasks for $n$ agents using $O( \log \log n )$ states must take $Ω( n / \rm{polylog} n )$ expected time. This is the first result to characterize time complexity for protocols which employ super-constant number of states per node, and proves that fast, poly-logarithmic running times require protocols to have relatively large space costs. On the positive side, we give algorithms showing that fast, poly-logarithmic stabilization time can be achieved using $O( \log^2 n )$ space per node, in the case of both tasks. Overall, our results highlight a time complexity separation between $O(\log \log n)$ and $Θ( \log^2 n )$ state space size for both majority and leader election in population protocols, and introduce new techniques, which should be applicable more broadly.

Concurrent objects play a key role in the design of applications for multicore architectures, making it imperative to precisely understand their complexity requirements. For some objects, it is known that implementations can be significantly more efficient when their usage is restricted. However, apart from the specific restriction of one-shot implementations, where each process may apply only a single operation to the object, very little is known about the complexities of objects under general restrictions. This paper draws a more complete picture by defining a large class of objects for which an operation applied to the object can be “perturbed” $L$ consecutive times, and by proving lower bounds on their space complexity and on the time complexity of deterministic implementations of such objects. This class includes bounded-value max registers, limited-use approximate and exact counters, and limited-use collect and compare-and-swap objects; $L$ depends on the number of times the object can be accessed or the maximum value it can support. For $n$-process implementations that use only historyless primitives, we prove $\Omega( \min( L, n ))$ space complexity lower bounds, which hold for both deterministic and randomized implementations. For deterministic implementations, we prove lower bounds of $\Omega(\min(\log L, n))$ on the worst-case step complexity of an operation. When arbitrary primitives can be used, we prove that either some operation incurs $\Omega(\min(\log L, n))$ memory stalls or some operation performs $\Omega(\min(\log L, n))$ steps. In addition to our deterministic time lower bounds, the paper establishes lower bounds on the expected step complexity of restricted-use randomized versions of many of these objects in a weak oblivious adversary model.

This issue of SICOMP contains seven specially selected papers from STOC 2013, the Forty-Fifth Annual ACM Symposium on the Theory of Computing, which was held June 1 through 4, 2013, in Palo Alto, California. The papers here were chosen to represent the range and quality of the STOC program. These papers have been revised and extended by their authors and subjected to the standard thorough the reviewing process of SICOMP. The program committee for STOC 2013 consisted of an executive committee made up of Boaz Barak, Irit Dinur, Leslie Goldberg, Giuseppe F. Italiano, Sampath Kannan, Neeraj Kayal, Michael Mitzenmacher, and Miklos Santha, supervising a broader program committee made up of Scott Aaronson, Susanne Albers, Benny Applebaum, James Aspnes, Per Austrin, Avrim Blum, Anne Broadbent, Peter Bürgisser, John Byers, Amit Chakrabarti, Shuchi Chawla, Bernard Chazelle, Xi Chen, Julia Chuzhoy, Graham Cormode, Artur Czumaj, Constantinos Daskalakis, Zeev Dvir, Jeff Erickson, Lance Fortnow, Craig Gentry, Anna Gilbert, Sudipto Guha, Mohammed Taghi Hajiaghayi, Moritz Hardt, Avinatan Hassidim, Monika Henzinger, Maurice Herlihy, Nicole Immorlica, Russell Impagliazzo, Piotr Indyk, Yuval Ishai, Mark Jerrum, Yael Kalai, Tali Kaufman, Haim Kaplan, Jonathan Kelner, Valerie King, Samir Khuller, Robert Kleinberg, Elias Koutsoupias, Robert Krauthgamer, Pinyan Lu, Aleksander Madry, Dániel Marx, Peter Bro Miltersen, Moni Naor, Ilan Newman, Rina Panigrahy, Prasad Raghavendra, Andrea Richa, Michael Schapira, Rocco Servedio, Amir Shpilka, Cliff Stein, David Steurer, Mikkel Thorup, Virginia Vassilevska Williams, Eric Vigoda, Ryan Williams, Ronald de Wolf, and David Zuckerman. The program chair was Joan Feigenbaum. Included in this issue are the following papers: ``An $o(n)$ Monotonicity Tester for Boolean Functions over the Hypercube," by Deeparnab Chakrabarty and C. Seshadhri, provides a randomized tester for near-monotone functions requiring sublinear queries. ``Answering $n^{2+o(1)}$ Counting Queries with Differential Privacy Is Hard," by Jonathan Ullman, gives a nearly tight bound on the number of counting queries that can be answered while preserving privacy. ``Natural Proofs Versus Derandomization," by Ryan Williams, demonstrates surprising connections between natural proofs, derandomization, and weak circuit lower bounds. ``Approximating $k$-median via Pseudo-Approximation," by Shi Li and Ola Svensson, improves the approximation ratio for $k$-median from $3+\epsilon$ to $1 + \sqrt{3} + \epsilon$, the first improvement in a decade. ``Maintaining Shortest Paths under Deletions in Weighted Directed Graphs," by Aaron Bernstein, improves on previous algorithms for maintaining all-pairs approximate shortest paths. ``The Geometry of Differential Privacy: The Sparse and Approximate Cases," by Aleksandar Nikolov, Kunal Talwar, and Li Zhang, characterizes the trade-offs between accuracy and privacy for a rich class of database queries. ``Superlinear Advantage for Exact Quantum Algorithms," by Andris Ambainis, gives the first example of a function that can be computed with a sublinear number of queries compared to the corresponding deterministic algorithm. We thank the authors, the STOC 2013 program committee, the STOC 2013 external reviewers, and the SICOMP referees for all of their hard work.

The population protocol model provides theoretical foundations for analyzing the properties emerging from simple and pair wise interactions among a very large number n of anonymous agents. The problem tackled in this paper is the following one: is there an efficient population protocol that exactly counts the difference k between the number of agents that initially and independently set their state to "A" and the one that initially set it to "B", assuming that each agent only uses a finite set of states? We propose a solution which guarantees with any high probability that after O(log n) interactions any agent outputs the exact value of k. Simulation results illustrate our theoretical analysis.

This article presents a novel implementation of a snapshot object for n processes, with O (log 2 b log n ) step complexity for update operations and O (log b ) step complexity for scan operations, where b is the number of updates. The algorithm uses only reads and writes. For polynomially many updates, this is an exponential improvement on previous snapshot algorithms, which have linear step complexity. It overcomes the existing Ω( n ) lower bound on step complexity by having the step complexity depend on the number of updates. The key to this implementation is the construction of a new object consisting of a pair of max registers that supports a scan operation.

Task allocation is a classic distributed problem in which a set of p potentially faulty processes must cooperate to perform a set of tasks. This paper considers a new dynamic version of the problem, in which tasks are injected adversarially during an asynchronous execution. We give the first asynchronous shared-memory algorithm for dynamic task allocation, and we prove that our solution is optimal within logarithmic factors. The main algorithmic idea is a randomized concurrent data structure called a dynamic to-do tree, which allows processes to pick new tasks to perform at random from the set of available tasks, and to insert tasks at random empty locations in the data structure. Our analysis shows that these properties avoid duplicating work unnecessarily. On the other hand, since the adversary controls the input as well the scheduling, it can induce executions where lots of processes contend for a few available tasks, which is inefficient. However, we prove that every algorithm has the same problem: given an arbitrary input, if OPT is the worst-case complexity of the optimal algorithm on that input, then the expected work complexity of our algorithm on the same input is O(OPT log3 m), where m is an upper bound on the number of tasks that are present in the system at any given time.

This article presents the first tight bounds on the time complexity of shared-memory renaming, a fundamental problem in distributed computing in which a set of processes need to pick distinct identifiers from a small namespace. We first prove an individual lower bound of Ω( k ) process steps for deterministic renaming into any namespace of size subexponential in k , where k is the number of participants. The bound is tight: it draws an exponential separation between deterministic and randomized solutions, and implies new tight bounds for deterministic concurrent fetch-and-increment counters, queues, and stacks. The proof is based on a new reduction from renaming to another fundamental problem in distributed computing: mutual exclusion. We complement this individual bound with a global lower bound of Ω( k log ( k / c )) on the total step complexity of renaming into a namespace of size ck , for any c ≥ 1. This result applies to randomized algorithms against a strong adversary, and helps derive new global lower bounds for randomized approximate counter implementations, that are tight within logarithmic factors. On the algorithmic side, we give a protocol that transforms any sorting network into a randomized strong adaptive renaming algorithm, with expected cost equal to the depth of the sorting network. This gives a tight adaptive renaming algorithm with expected step complexity O (log k ), where k is the contention in the current execution. This algorithm is the first to achieve sublinear time, and it is time-optimal as per our randomized lower bound. Finally, we use this renaming protocol to build monotone-consistent counters with logarithmic step complexity and linearizable fetch-and-increment registers with polylogarithmic cost.

Renaming is a classic distributed coordination task in which a set of processes must pick distinct identifiers from a small namespace. In this paper, we consider the time complexity of this problem when the namespace is linear in the number of participants, a variant known as loose renaming. We give a non-adaptive algorithm with O( log log n ) (individual) step complexity, where n is a known upper bound on contention, and an adaptive algorithm with step complexity O((log log k)2 ), where k is the actual contention in the execution. We also present a variant of the adaptive algorithm which requires O( k log log k ) total process steps. All upper bounds hold with high probability against a strong adaptive adversary.

Two new algorithms are given for randomized consensus in a shared-memory model with an oblivious adversary. Each is based on a new construction of a conciliator, an object that guarantees termination and validity, but that only guarantees agreement with constant probability. The first conciliator assumes unit-cost snapshots and achieves agreement among n processes with probability 1-μ in O(log* n + log(1/μ)) steps for each process. The second uses ordinary multi-writer registers, and achieves agreement with probability 1-μ in O(log log n + log(1/μ)) steps. Combining these constructions with known results gives randomized consensus for arbitrarily many possible input values using unit-cost snapshots in O(log* n) expected steps and randomized consensus for up to O(log n log log n) possible input values using ordinary registers in O(log log n) expected steps.

This paper presents a novel implementation of a snapshot object for n processes, with O(log2blogn) step complexity for update operations and O(logb) step complexity for scan operations, where b is the number of updates. The algorithm uses only reads and writes.

Concurrent objects play a key role in the design of applications for multi-core architectures, making it imperative to precisely understand their complexity requirements. For some objects, it is known that implementations can be significantly more efficient when their usage is restricted. However, apart from the specific restriction of one-shot implementations, where each process may apply only a single operation to the object, very little is known about the complexities of objects under general restrictions.

This article presents constructions of useful concurrent data structures, including max registers and counters, with step complexity that is sublinear in the number of processes, n . This result avoids a well-known lower bound by having step complexity that is polylogarithmic in the number of values the object can take or the number of operations applied to it. The key step in these implementations is a method for constructing a max register , a linearizable, wait-free concurrent data structure that supports a write operation and a read operation that returns the largest value previously written. For fixed m , an m -valued max register is constructed from one-bit multi-writer multi-reader registers at a cost of at most ⌈log m ⌉ atomic register operations per write or read. An unbounded max register is constructed with cost O (min(log v , n )) to read or write a value v . Max registers are used to transform any monotone circuit into a wait-free concurrent data structure that provides write operations setting the inputs to the circuit and a read operation that returns the value of the circuit on the largest input values previously supplied. One application is a simple, linearizable, wait-free counter with a cost of O (min(log n log v , n )) to perform an increment and O (min(log v , n )) to perform a read, where v is the current value of the counter. For polynomially-many increments, this becomes O (log 2 n ), an exponential improvement on the best previously known upper bounds of O ( n ) for exact counting and O ( n 4/5+ϵ ) for approximate counting. Finally, it is shown that the upper bounds are almost optimal. It is shown that for deterministic implementations, even if they are only required to satisfy solo-termination, min(⌈log m ⌉, n -1) is a lower bound on the worst-case complexity for an m -valued bounded max register, which is exactly equal to the upper bound for m ≤ 2 n -1 , and min( n -1, ⌈ log m ⌉ - log(⌈ log m ⌉ + k )) is a lower bound for the read operation of an m -valued k -additive-accurate counter, which is a bounded counter in which a read operation is allowed to return a value within an additive error of ± k of the number of increment operations linearized before it. Furthermore, even in a solo-terminating randomized implementation of an n -valued max register with an oblivious adversary and global coins, there exist simple schedules in which, with high probability, the worst-case step complexity of a read operation is Ω(log n /log log n ) if the write operations have polylogarithmic step complexity.

We study the complexity of renaming, a fundamental problem in distributed computing in which a set of processes need to pick distinct names from a given namespace. We prove an individual lower bound of Ω( k ) process steps for deterministic renaming into any namespace of size sub-exponential in k, where k is the number of participants. This bound is tight: it draws an exponential separation between deterministic and randomized solutions, and implies new tight bounds for deterministic fetch-and-increment registers, queues and stacks. The proof of the bound is interesting in its own right, for it relies on the first reduction from renaming to another fundamental problem in distributed computing: mutual exclusion. We complement our individual bound with a global lower bound of Ω(k log (k/c)) on the total step complexity of renaming into a namespace of size ck, for any c ≥ 1. This applies to randomized algorithms against a strong adversary, and helps derive new global lower bounds for randomized approximate counter and fetch-and-increment implementations, all tight within logarithmic factors.

We give two new randomized algorithms for strong renaming, both of which work against an adaptive adversary in asynchronous shared memory. The first uses repeated sampling over a sequence of arrays of decreasing size to assign unique names to each of n processes with step complexity O(log3 n). The second transforms any sorting network into a strong adaptive renaming protocol, with an expected cost equal to the depth of the sorting network. Using an AKS sorting network, this gives a strong adaptive renaming algorithm with step complexity O(log k), where k is the contention in the current execution. We show this to be optimal based on a classic lower bound of Jayanti. We also show that any such strong renaming protocol can be used to build a monotone-consistent counter with logarithmic step complexity (at the cost of adding a max register) or a linearizable fetch-and-increment register (at the cost of increasing the step complexity by a logarithmic factor).

We give matching upper and lower bounds of Θ(min(log m/log log m, n)) for the space and individual step complexity of a wait-free m-valued adopt-commit object implemented using multi-writer registers for n anonymous processes. While the upper bound is deterministic, the lower bound holds for randomized adopt-commit objects as well. Our results are based on showing that adopt-commit objects are equivalent up to small additive constants, to a simpler class of objects that we call weak conflict detectors.

We define two new classes of shared-memory objects: ratifiers, which detect agreement, and conciliators, which ensure agreement with some probability. We show that consensus can be solved by an alternating sequence of these objects, and observe that most known randomized consensus algorithms have this structure.

We consider the problem of minimizing contention in static dictionary data structures, where the contention on each cell is measured by the expected number of probes to that cell given an input that is chosen from a distribution that is not known to the query algorithm (but that may be known when the data structure is built). When all positive queries are equally probable, and similarly all negative queries are equally probable, we show that it is possible to construct a data structure using linear space s, a constant number of queries, and with contention O(1/s) on each cell, corresponding to a nearly-flat load distribution. All of these quantities are asymptotically optimal. For arbitrary query distributions, the lack of knowledge of the query distribution by the query algorithm prevents perfect load leveling in this case: we present a lower bound, based on VC-dimension, that shows that for a wide range of data structure problems, achieving contention even within a polylogarithmic factor of optimal requires a cell-probe complexity of Ω(log log n).

A new randomized asynchronous shared-memory data structure is given for implementing an approximate counter that can be incremented once by each of n processes in a model that allows up to n -1 crash failures. For any fixed ϵ, the counter achieves a relative error of δ with high probability, at the cost of O (((1/δ) log n ) O (1/ϵ) ) register operations per increment and O ( n 4/5+ϵ ((1/δ) log n ) O (1/ϵ) ) register operations per read. The counter combines randomized sampling for estimating large values with an expander for estimating small values. This is the first counter implementation that is sublinear the number of processes and works despite a strong adversary scheduler that can observe internal states of processes. An application of the improved counter is an improved protocol for solving randomized shared-memory consensus, which reduces the best previously known individual work complexity from O ( n log n ) to an optimal O ( n ), resolving one of the last remaining open problems concerning consensus in this model.

A method is given for constructing a max register, a linearizable, wait-free concurrent data structure that supports a write operation and a read operation that returns the largest value previously written. For fixed m, an m-valued max register can be constructed from one-bit multi-writer multi-reader registers at a cost of at most [lg m] atomic register operations per write or read. The construction takes the form of a binary search tree: applying classic techniques for building unbalanced search trees gives an unbounded max register with cost O(min(log v, n)) to read or write a value v, where n is the number of processes.

A new randomized asynchronous shared-memory data structure is given for implementing an approximate counter that can be incremented up to n times. For any fixed ∊, the counter achieves a relative error of δ with high probability at the cost of O(((1/δ)log n)O(1/∊)) register operations per increment and O(n4/5+∊((1/δ)log n)O(1/∊)) register operations per read. The counter combines randomized sampling for estimating large values with an expander for estimating small values. This is the first sublinear solution to this problem that works despite a strong adversary scheduler that can observe internal states of processes. An application of the improved counter is an improved protocol for solving randomized shared-memory consensus, which reduces the best previously known individual work complexity from O(n log n) to an optimal O(n), resolving one of the last remaining open problems concerning consensus in this model.

This paper presents a new randomized algorithm for achieving consensus among asynchronous processes that communicate by reading and writing shared registers, in the presence of a strong adversary. The fastest previously known algorithm requires a process to perform an expected O(n log2 n) read and write operations in the worst case. In our algorithm, each process executes at most an expected O(n log n) read and write operations. It is shown that shared-coin algorithms can be combined together to yield an algorithm with O(n log n) individual work and O(n2) total work.

This article studies self-stabilization in networks of anonymous, asynchronously interacting nodes where the size of the network is unknown. Constant-space protocols are given for Dijkstra-style round-robin token circulation, leader election in rings, two-hop coloring in degree-bounded graphs, and establishing consistent global orientation in an undirected ring. A protocol to construct a spanning tree in regular graphs using O (log D ) memory is also given, where D is the diameter of the graph. A general method for eliminating nondeterministic transitions from the self-stabilizing implementation of a large family of behaviors is used to simplify the constructions, and general conditions under which protocol composition preserves behavior are used in proving their correctness.

Skip graphs are a novel distributed data structure, based on skip lists, that provide the full functionality of a balanced tree in a distributed system where resources are stored in separate nodes that may fail at any time. They are designed for use in searching peer-to-peer systems, and by providing the ability to perform queries based on key ordering, they improve on existing search tools that provide only hash table functionality. Unlike skip lists or other tree data structures, skip graphs are highly resilient, tolerating a large fraction of failed nodes without losing connectivity. In addition, simple and straightforward algorithms can be used to construct a skip graph, insert new nodes into it, search it, and detect and repair errors within it introduced due to node failures.

We consider the model of population protocols introduced by Angluin et al. [2], in which anonymous finite-state agents stably compute a predicate of their inputs via two-way interactions in the all-pairs family of communication networks. We prove that all predicates stably computable in this model (and certain generalizations of it) are semilinear, answering a central open question about the power of the model.

We propose a new model for exact learning of acyclic circuits using experiments in which chosen values may be assigned to an arbitrary subset of wires internal to the circuit, but only the value of the circuit's single output wire may be observed. We give polynomial time algorithms to learn (1) arbitrary circuits with logarithmic depth and constant fan-in and (2) Boolean circuits of constant depth and unbounded fan-in over AND, OR, and NOT gates. Thus, both AC0 and NC1 circuits are learnable in polynomial time in this model. Negative results show that some restrictions on depth, fan-in and gate types are necessary: exponentially many experiments are required to learn AND/OR circuits of unbounded depth and fan-in; it is NP-hard to learn AND/OR circuits of unbounded depth and fan-in 2; and it is NP-hard to learn circuits of bounded depth and unbounded fan-in over AND, OR, and threshold gates, even when the target circuit is known to contain at most one threshold gate and that threshold gate has threshold 2. We also consider the effect of adding an oracle for behavioral equivalence. In this case there are polynomial-time algorithms to learn arbitrary circuits of constant fan-in and unbounded depth and to learn Boolean circuits with arbitrary fan-in and unbounded depth over AND, OR, and NOT gates. A corollary is that these two classes are PAC-learnable if experiments are available.

In this paper, we provide a theoretical foundation for the problem of network localization in which some nodes know their locations and other nodes determine their locations by measuring the distances to their neighbors. We construct grounded graphs to model network localization and apply graph rigidity theory to test the conditions for unique localizability and to construct uniquely localizable networks. We further study the computational complexity of network localization and investigate a subclass of grounded graphs where localization can be computed efficiently. We conclude with a discussion of localization in sensor networks where the sensors are placed randomly.

An asynchronous algorithm is described for rapidly constructing an overlay network in a peer-to-peer system where all nodes can in principle communicate with each other directly through an underlying network, but each participating node initially has pointers to only a handful of other participants. The output of the mechanism is a linked list of all participants sorted by their identifiers, which can be used as a foundation for building various linear overlay networks such as Chord or skip graphs. Assuming the initial pointer graph is weakly-connected with maximum degree d and the length of a node identifier is W, the mechanism constructs a binary search tree of nodes of depth O(W) in expected O(W log n) time using expected O((d+W)nlog n) messages of size O(W) each. Furthermore, the algorithm has low contention: at any time there are only O(d) undelivered messages for any given recipient. A lower bound of Ω(d + log n) is given for the running time of any procedure in a related synchronous model that yields a sorted list from a degree-d weakly-connected graph of n nodes. We conjecture that this lower bound is tight and could be attained by further improvements to our algorithms.

We prove that with high probability a skip graph contains a 4-regular expander as a subgraph, and estimate the quality of the expansion via simulations. As a consequence skip graphs contain a large connected component even after an adversarial deletion of nodes. We show how the expansion property could be used to sample a node in the skip graph in a highly efficient manner. We also show that the expansion property could be used to load balance the skip graph quickly. Finally it is shown that the skip graph could serve as an unstructured P2P system, thus it is a good candidate for a hybrid P2P system.

We explore the computational power of networks of small resource-limited mobile agents. We define two new models of computation based on pairwise interactions of finite-state agents in populations of finite but unbounded size. With a fairness condition on interactions, we define the concept of stable computation of a function or predicate, and give protocols that stably compute functions in a class including Boolean combinations of threshold-k, parity, majority, and simple arithmetic. We prove that all stably computable predicates are in NL. With uniform random sampling of pairs to interact, we define the model of conjugating automata and show that any counter machine with O(1) counters of capacity O(n) can be simulated with high probability by a protocol in a population of size n. We prove that all predicates computable with high probability in this model are in P ∩ RL. Several open problems and promising future directions are discussed.

We describe a load-balancing mechanism for assigning elements to servers in a distributed data structure that supports range queries. The mechanism ensures both load-balancing with respect to an arbitrary load measure specified by the user and geographical locality, assigning elements with similar keys to the same server. Though our mechanism is specifically designed to improve the performance of skip graphs, it can be adapted to provide deterministic, locality-preserving load-balancing to any distributed data structure that orders machines in a ring or line.

We consider the problem of designing an overlay network and routing mechanism that permits finding resources efficiently in a peer-to-peer system. We argue that many existing approaches to this problem can be modeled as the construction of a random graph embedded in a metric space whose points represent resource identifiers, where the probability of a connection between two nodes depends only on the distance between them in the metric space. We study the performance of a peer-to-peer system where nodes are embedded at grid points in a simple metric space: a one-dimensional real line. We prove upper and lower bounds on the message complexity of locating particular resources in such a system, under a variety of assumptions about failures of either nodes or the connections between them. Our lower bounds in particular show that the use of inverse power-law distributions in routing, as suggested by Kleinberg [5], is close to optimal. We also give heuristics to efficiently maintain a network supporting efficient routing as nodes enter and leave the system. Finally, we give some experimental results that suggest promising directions for future work.

A randomized algorithm is given that solves the wait-free consensus problem for a shared-memory model with infinitely many processes. The algorithm is based on a weak shared coin algorithm that uses weighted voting to achieve a majority outcome with at least constant probability that cannot be disguised even if a strong adversary is allowed to destroy infinitely many votes. The number of operations performed by process i is a polynomial function of i. Additional algorithms are given for solving consensus more efficiently in models with an unknown upper bound b on concurrency or an unknown upper bound n on the number of active processes; under either of these restrictions, it is also shown that the problem can be solved even with infinitely many anonymous processes by prefixing each instance of the shared coin with a naming algorithm that breaks symmetry with high probability. For many of these algorithms, matching lower bounds are proved that show that their per-process work is nearly optimal as a function of i, b, or n. The case of n active processes gives an algorithm for anonymous, adaptive consensus that requires only O(n log2 n) per-process work, which is within a constant factor of the best previously known non-adaptive algorithm for a strong adversary. Finally, it is shown that standard universal constructions based on consensus continue to work with infinitely many processes with only slight modifications. This shows that in infinite distributed systems, as in finite ones, with randomness all things are possible.

It is well known that the consensus problem cannot be solved deterministically in an asynchronous environment, but that randomized solutions are possible. We propose a new model, called noisy scheduling, in which an adversarial schedule is perturbed randomly, and show that in this model randomness in the environment can substitute for randomness in the algorithm. In particular, we show that a simplified, deterministic version of Chandra's wait-free shared-memory consensus algorithm [16] solves consensus in time at most logarithmic in the number of active processes. The proof of termination is based on showing that a race between independent delayed renewal processes produces a winner quickly. In addition, we show that the protocol finishes in constant time using quantum and priority-based scheduling on a uniprocessor, suggesting that it is robust against the choice of model over a wide range.

We examine a class of collective coin-flipping games that arises from randomized distributed algorithms with halting failures. In these games, a sequence of local coin flips is generated, which must be combined to form a single global coin flip . An adversary monitors the game and may attempt to bias its outcome by hiding the result of up to t local coin flips. We show that to guarantee at most constant bias, ω( t 2 ) local coins are needed, even if (a) the local coins can have arbitrary distributions and ranges, (b) the adversary is required to decide immediately wheter to hide or reveal each local coin, and (c) the game can detect which local coins have been hidden. If the adversary is permitted to control the outcome of the coin except for cases whose probability is polynomial in t , ω( t 2 /log 2 t ) local coins are needed. Combining this fact with an extended version of the well-known Fischer-Lynch-Paterson impossibility proof of deterministic consensus, we show that given an adaptive adversary, any t -resilient asynchronous consensus protocol requires ω( t 2 /log 2 t ) local coin flips in any model that can be simulated deterministically using atomic registers. This gives the first nontrivial lower bound on the total work required by wait-free consensus and is tight to within logarithmic factors.

We examine a chse of collective coin-j?ipping game8 that arises from randomized distributed algorithms with halting failures.In these games, a sequence of local coin flips is generated, which must be combined to form a single global coin flip.An adversary monitors the game and may attempt to b-its outcome by hhiing the result of up ta t local coin tlipa.We show that to guarantee at moat constant bias, fl(t2) local coins are needed, even if (a) the local coins can have arbitrary distributions and ranges, (b) the adversary is required to decide immediately whether to hide or reveal each local coin, and (c) the game cart detect which local coins have been hidden.If the adversary ia permitted to control the outcome of the coin except for cases whose probability is pdynomid in t,f2(t2 /log2 t) local coins are needed.Combtig this fact with an extended veraion of the well-known Fiecher-Lynch-Pateraort impossibility proof of determirtis tic consensus, we show that given an adaptive adversary, arty t-resilient asynchronous consensus protocol requires 0(t2/ log2 t) local coin fips in arty model that can be simulated deterministically using atomic registers.This gives the first non-trivial lower bound on the totaJ work required by wait-free consensus and is tight to within logarithmic factors.

In this paper we study the problem of on-line allocation of routes to virtual circuits (both point-to-point and multicast ) where the goal is to route all requests while minimizing the required bandwidth. We concentrate on the case of Permanent virtual circuits (i.e., once a circuit is established it exists forever), and describe an algorithm that achieves on O (log n ) competitive ratio with respect to maximum congestin, where n is the number of nodes in the network. Informally, our results show that instead of knowing all of the future requests, it is sufficient to increase the bandwidth of the communication links by an O (log n ) factor. We also show that this result is tight, that is, for any on-line algorithm there exists a scenario in which Ω(log n ) increase in bandwidth is necessary in directed networks. We view virtual circuit routing as a generalization of an on-line load balancing problem, defined as follows: jobs arrive on line and each job must be assigned to one of the machines immediately upon arrival. Assigning a job to a machine increases the machine's load by an amount that depends both on the job and on the machine. The goal is to minimize the maximum load. For the related machines case, we describe the first algorithm that achieves constant competitive ratio. for the unrelated case (with n machines), we describe a new method that yields O (log n )-competitive algorithm. This stands in contrast to the natural greed approach, whose competitive ratio is exactly n .

In the collect problem [32], n processors in a shared-memory system must each learn the values of n registers.We give a randomized algorithm that solves the coMect problem in O(n log3 n) total read and write operations with high probability, even if timing is under the control of a contentoblivious adversary (a slight weakening of the usual adap tive adversary).This improves on both the trivial upper bound of O(n2) steps and the best previously known bound of 0(n3/2 log n) steps, and is close to the lower bound of Q(rz log ta) steps.Furthermore, we show how this algorithm can be used to obtain a multi-use cooperative collect protocol that is O(log3 n)-competitive in the latency model of Ajtai et rd.[3] and O(nl /2 logsiz n)-competitive in the throughput model of Aspnes and Waarts [10]; in both cases we show that the competitive ratios are within a polylogarithmic factor of optimal.

We define a novel measure of competitive performance for distributed algorithms based on throughput, the number of tasks that an a3gorithm can carry out in a fixed amount of work.An important property of the throughput measure is that it is modular: we define a notion of relative competitiveness with the property that a k-relatively competitive implementation of an object T using a subroutine U, combined with an l-competitive implement ation of U, gives a M-competitive algorithm for T. We prove the throughput-competitiveness of an algorithm for a fundamental building block of many well-known distributed algorithms: the cooperative collect primitive.ThE permits a straightforward construction of competitive versions of these algorithms-the first examples of algorithms obtained through a general method for modular construction of competitive distributed algorithms.Moreover, we provide a lower bound that shows that the throughput competitiveness of the cooperative collect algorithm we study is nearly optimal Thus, we see our paper aa making two main contributions: one is the introduction of a modular measurement for competitiveness, whose interest is justified by the throughput competitiveness of the cooperative collect algorithms; and the other is a technique for proving throughput competitiveness, which may apply to other distributed problems.

This paper presents a new randomized algorithm for achieving consensus among asynchronous processors that communicate by reading and writing shared registers. The fastest previously known algorithm requires a processor to perform an expected $O(n^2 \log n)$ read and write operations in the worst case. In our algorithm, each processor executes at most an expected $O(n\log ^2 n)$ read and write operations, which is close to the trivial lower bound of $\Omega (n)$. All previously known polynomial-time consensus algorithms were structured around a shared-coin protocol [J. Algorithms, 11(1990), pp. 441–446] in which each processor repeatedly adds random $ \pm 1$ votes to a common pool. Consequently, in all of these protocols, the worst-case expected bound on the number of read and write operations done by a single processor is asymptotically no better than the bound on the total number of read and write operations done by all of the processors together. We succeed in breaking this tradition by allowing the processors to cast votes of increasing weights. This grants the adversary greater control since he can choose from up to n different weights (one for each processor) when determining the weight of the next vote to be cast. We prove that our shared-coin protocol is nevertheless correct using martingale arguments.

We introduce a theory of competitive analysis for distributed algorithms. The first steps in this direction were made in the seminal papers of Y. Bartal et al. (1992), and of B. Awerbuch et al. (1992), in the context of data management and job scheduling. In these papers, as well as in other subsequent sequent work, the cost of a distributed algorithm is compared to the cost of an optimal global-control algorithm. In this paper we introduce a more refined notion of competitiveness for distributed algorithms, one that reflects the performance of distributed algorithms more accurately. In particular, our theory allows one to compare the cost of a distributed on-line algorithm to the cost of an optimal distributed algorithm. We demonstrate our method by studying the cooperative collect primitive, first abstracted by M. Saks, N. Shavit, and H. Woll (1991). We provide the first algorithms that allow processes to cooperate to finish their work in fewer steps. Specifically, we present two algorithms (with different strengths), and provide a competitive analysis for each one.>

No abstract available.

Many fundamental multi-processor coordination problems can be expressed as counting problems : Processes must cooperate to assign successive values from a given range, such as addresses in memory or destinations on an interconnection network. Conventional solutions to these problems perform poorly because of synchronization bottlenecks and high memory contention. Motivated by observations on the behavior of sorting networks, we offer a new approach to solving such problems, by introducing counting networks , a new class of networks that can be used to count. We give two counting network constructions, one of depth log n (1 + log n )/2 using n log (1 + log n )/4 “gates,” and a second of depth log 2 n using n log 2 n /2 gates. These networks avoid the sequential bottlenecks inherent to earlier solutions and substantially lower the memory contention. Finally, to show that counting networks are not merely mathematical creatures, we provide experimental evidence that they outperform conventional synchronization techniques under a variety of circumstances.

In this paper we study an idealized problem of on-line allocation of routes to virtual circuits where the goal is to minimize the required bandwidth.For the case where virtual circuits continue to exist forever, we describe an algorithm that achieves an O (log n) competitive ratio, where n is the number of nodes in the network.Informally, our results show that instead of knowing all of the future requests, it is sufficient to increase the bandwidth of the communication links by an O(log n) factor.We also show that this result is tight, i.e. for any on-line algorithm there exists a scenario in which O(log n) increase in bandwidth is necessary.We view virtual circuit routing as a generalization of an on-line scheduling problem, and hence a major part of the paper focuses on development of algorithms for non-preemptive on-line scheduling for related and unrelated machines.Specialization of routing to scheduling leads us to concentrate on scheduling in the case where jobs must be assigned immediately upon arrival; assigning a job to a machine increases this machine's load by an amount that depends both on the job and on the machine.The goal is to minimize the maximum load.For the related machines case, we describe the first algorithm that achieves constant competitive ratio.For the unrekzted case (with n machines), we describe a new method that yields O(log n)-competitive algorithm.This stands in contrast to the natural greedy approach, which we show has only a ~(n) competitive ratio.The virtual circuit routing result follows as a generalization of the unrelated machines case.

The paper presents a new randomized algorithm for achieving consensus among asynchronous processors that communicate by reading and writing shared registers. The fastest previously known algorithm requires a processor to perform an expected O(n/sup 2/ log n) read and write operations in the worst case. In the algorithm, each processor executes at most an expected O(n log/sup 2/ n) read and write operations, which is close to the trivial lower bound of Omega (n). All previously known polynomial-time consensus algorithms were structured around a shared coin protocol in which each processor repeatedly adds random +or-1 votes to a common pool. Consequently, in all of these protocols, the worst case expected bound on the number of read and write operations done by a single processor is asymptotically no better than the bound on the total number of read and write operations done by all of the processors together. The authors succeed in breaking this tradition by allowing the processors to cast votes of increasing weights. This grants the adversary greater control since he can choose from up to n different weights (one for each processor) when determining the w i ht of the next vote to be cast. They prove that the shared coin protocol is correct nevertheless using martingale arguments.>

We consider the problem of approximating a Boolean function f : f0; 1g n ! f0; 1g by the sign of an integer polynomial p of degree k. For us, a polynomial p(x) predicts the value of f(x) if, whenever p(x) 0, f(x) = 1, and whenever p(x) ! 0, f(x) = 0. A low-degree polynomial p is a good approximator for f if it predicts f at almost all points. Given a positive integer k, and a Boolean function f , we ask, "how good is the best degree k approximation to f?" We introduce a new lower bound technique which applies to any Boolean function. We show that the lower bound technique yields tight bounds in the case f is parity. Minsky and Papert [10] proved that a perceptron can not compute parity; our bounds indicate exactly how well Yale University, Dept. of Computer Science, P.O. Box 208285, New Haven CT 06520-8285. y Email: [email protected]. z Email: [email protected]. Supported in part by NSF grants CCR-8808949 and CCR-8958528. x Carnegie-Mellon University, Schoo...

Many fundamental multi-processor coordination problems can be expressed as counting problems: processes must cooperate to assign successive values from a given range, such as addresses in memory or destinations on an interconnection network. Conventional solutions to these problems perform poorly because of synchronization bottlenecks and high memory contention. Motivated by observations on the behavior of sorting networks, we o er a completely new approach to solving such problems. We introduce a new class of networks called counting networks, i.e., networks that can be used to count. We give a counting network construction of depth log 2 n using n log 2 n \\gates, " avoiding the sequential bottlenecks inherent to former solutions, and having a provably lower contention factor on its gates. Finally, to show that counting networks are not merely mathematical creatures, we provide experimental evidence that they outperform conventional synchronization techniques under a variety of circumstances.

An algorithm is presented which solves the randomized consensus problem [7] for shared memory.The algorithm uses O(p2 + n) worst-case expected operations on a set of three shared O(log n)-bit counters, where p is the number of active processors and n is the total number of processors; it thus requires less space than previous polynomial-time consensus protocols [4,6], and is faster when not all of the processors participate in the protocol.A modified version of the protocol yields a weak shared coin whose bias is guaranteed to be in the range l/2 f 6 regardless of scheduler behavior, and which is the first such protocol for the shared-memory model to guarantee that all processors agree on the outcome of the coin.

A wad-free implementation of a data object in shared memory is one that guarantees that any process can complete any operation in a finite number of steps, re-gardless of the execution speeds of the other processes. Much of the literature on wait-free synchronization has focused on the construction of atomic registers, which are memory locations that can be read 01 written in-stantaneously by concurrent processes. This model, in which a set of asynchronous processes communicate through shared atomic registers, is sometimes known as asynchronous PRAM. It is known, however, that the asynchronous PRAM model is not sufficiently powerful to construct wait-free implementations of many simple data types such as lists, queues, stacks, test-and-set reg-isters, and others. In this paper, we give an algebraic characterization of a large class of objects that do have wait-free implementations in asynchronous PRAM, as well as a general algorithm for implementing them. 1