Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

Attiya, Hagit (Ed.)The standard population protocol model assumes that when two agents interact, each observes the entire state of the other agent. We initiate the study of the message complexity for population protocols, where the state of an agent is divided into an externallyvisible message and an internal component, where only the message can be observed by the other agent in an interaction. 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 a semilinear predicate (unlike the original model, which can compute nonsemilinear predicates with s(n) = O(log n)), and otherwise it computes a predicate decidable by a nondeterministic O(n log s(n))spacebounded Turing machine. We then consider time complexity, introducing 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 boundedmessagesize 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 onebit messages.more » « less

null (Ed.)Thirdstate dynamics (Angluin et al. 2008; Perron et al. 2009) is a wellknown process for quickly and robustly computing approximate majority through interactions between randomlychosen pairs of agents. In this paper, we consider this process in a new model with persistentstate catalytic inputs, as well as in the presence of transient leak faults. Based on models considered in recent protocols for populations with persistentstate agents (Dudek et al. 2017; Alistarh et al. 2017; Alistarh et al. 2020), we formalize a Catalytic Input (CI) model comprising n input agents and m worker agents. For m = Θ(n), we show that computing the parity of the input population with high probability requires at least Ω(n2) total interactions, demonstrating a strong separation between the CI and standard population protocol models. On the other hand, we show that the thirdstate dynamics can be naturally adapted to this new model to solve approximate majority in O(n log n) total steps with high probability when the input margin is Ω(√(n log n)), which preserves the time and space efficiency of the corresponding protocol in the original model. We then show the robustness of thirdstate dynamics protocols to the transient leak faults considered by (Alistarh et al. 2017; Alistarh et al 2020). In both the original and CI models, these protocols successfully compute approximate majority with high probability in the presence of leaks occurring at each time step with probability β ≤ O(√(n log n}/n). The resilience of these dynamics to adversarial leaks exhibits a subtle connection to previous results involving Byzantine agents.more » « less

We consider the problem of implementing randomized waitfree consensus from max registers under the assumption of an oblivious adversary. We show that max registers solve mvalued 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 maxregister implementation based on doublecollect snapshots translates this result into an O(n log n) expected step implementation of mvalued consensus from n singlewriter registers, improving on the best previouslyknown bound of O(n log^2 n) for singlewriter registers.more » « less

It is impossible to deterministically solve waitfree 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 extensionbased proofs, a class of impossibility proofs that are modelled as an interaction between a prover and a protocol and that include valency arguments. Using proofs based on combinatorial topology, it has been shown that it is impossible to deterministically solve kset agreement among n > k ≥ 2 processes in a waitfree manner. However, it was unknown whether proofs based on simpler techniques were possible. We show that this impossibility result cannot be obtained by an extensionbased proof and, hence, extensionbased proofs are limited in power.more » « less

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. We implement a prototype of BoxOpt and demonstrate its efficiency and efficacy via extensive experiments using real network topology and trace. Results show that (1) BoxOpt has a 100% correctness ratio, and (2) for 95% of requests, BoxOpt learns the optimal resource reservation within 13 seconds.more » « less