This work concerns the general issue of combined optimality in terms of time and space complexity. In this context, we study the problem of counting resource-limited and passively mobile nodes in the model of population protocols, in which the space complexity is crucial. The counted nodes are memory-limited anonymous devices (called agents) communicating asynchronously in pairs (according to a fairness condition). Moreover, we assume that these agents are prone to failures so that they cannot be correctly initialized.
This study considers two classical fairness conditions, and for each we investigate the issue of time optimality of (exact) counting given optimal space. First, with randomly interacting agents (probabilistic fairness), we present a ``non-guessing'' time optimal protocol of O(n log n) expected interactions given an optimal space of only one bit (for a population of size n). We prove the time optimality of such protocol.
Then, under weak fairness (where every pair of agents interacts infinitely often), we show that a space optimal (semi-uniform) solution cannot converge faster than in Ω(2n) time, in terms of non-null transitions (i.e, the transitions that affect the states of the interacting agents). This result together with the time complexity analysis of an already known space optimal protocol shows that it is also optimal in time (given the optimal space constraints).
more »
« less
Optimal eventual Byzantine agreement protocols with omission failures
Work on optimal protocols for \emph{Eventual Byzantine Agreement}
(EBA)---protocols that, in a precise sense, decide as soon as possible
in every run and guarantee that all nonfaulty agents decide on the
same value---has focused on full-information protocols} (FIPs), where
agents repeatedly send messages that completely describe their past
observations to every other agent. While it can be shown that, without
loss of generality, we can take an optimal protocol to be an FIP, full information
exchange is impractical to implement for many applications due to the
required message size. We separate protocols into two parts, the information-exchange
protocol and the action protocol, so as to be able to examine the effects of more limited information exchange. We then define a notion of optimality with respect to an information-exchange protocol. Roughly speaking, an action protocol P is
optimal with respect to an information-exchange protocol E if, with P, agents decide as soon as possible among action protocols that exchange information according to E.
We present a knowledge-based EBA program for omission failures all of whose implementations are guaranteed to be correct and are optimal if the information exchange satisfies a certain safety condition. We then construct concrete programs that implement this knowledge-based program in two settings of interest that are shown to satisfy the safety condition. Finally, we show that a small modification of our program results in
an FIP that s both optimal and efficiently implementable, settling an open problem posed by Halpern, Moses, and Waarts (SIAM J. Comput., 2001).
more »
« less
- Award ID(s):
- 1703846
- PAR ID:
- 10414209
- Date Published:
- Journal Name:
- Proceedings of the 42nd Annual ACM Symposium on Principles of Distributed Computing (PODC)
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
more » « less
In five experiments ( N = 1,490), participants were asked to imagine themselves as programmers of self-driving cars who had to decide how to program the car to respond in a potential accident: spare the driver or spare pedestrians. Alternatively, participants imagined that they were a mayor grappling with difficult moral dilemmas concerning COVID-19. Either they, themselves, had to decide how to program the car or which COVID-19 policy to implement (high-agency condition) or they were told by their superior how to act (low-agency condition). After learning that a tragic outcome occurred because of their action, participants reported their felt culpability. Although we expected people to feel less culpable about the outcome if they acted in accordance with their superior’s injunction than if they made the decision themselves, participants actually felt more culpable when they followed their superior’s order. Some possible reasons for this counterintuitive finding are discussed.
-
An interaction protocol specifies a decentralized multiagent system operationally by specifying constraints on messages exchanged by its member agents. Engineering with protocols requires support for a notion of refinement, whereby a protocol may be substituted without loss of correctness by one that refines it. We identify two desiderata for refinement. One, generality: refinement should not restrict enactments by limiting protocols or infrastructures under consideration. Two, preservation: to facilitate modular verification, refinement should preserve liveness and safety. We contribute a novel formal notion of protocol refinement based on enactments. We demonstrate generality by tackling the declarative framework of information protocols. We demonstrate preservation by formally establishing that our notion of refinement is safety and liveness preserving. We show the practical benefits of refinement by implementing a checker. We demonstrate that it is less time-intensive to check refinement (and thereby gain safety and liveness) than to recheck safety and liveness of a composition.more » « less
-
An interaction protocol specifies a decentralized multiagent system operationally by specifying constraints on messages exchanged by its member agents. Engineering with protocols requires support for a notion of refinement, whereby a protocol may be substituted without loss of correctness by one that refines it. We identify two desiderata for refinement. One, generality: refinement should not restrict enactments by limiting protocols or infrastructures under consideration. Two, preservation: to facilitate modular verification, refinement should preserve liveness and safety. We contribute a novel formal notion of protocol refinement based on enactments. We demonstrate generality by tackling the declarative framework of information protocols. We demonstrate preservation by formally establishing that our notion of refinement is safety and liveness preserving. We show the practical benefits of refinement by implementing a checker. We demonstrate that it is less time-intensive to check refinement (and thereby gain safety and liveness) than to recheck safety and liveness of a composition.more » « less
-
Abstract We study both the practical and theoretical efficiency of private information retrieval (PIR) protocols in a model wherein several untrusted servers work to obliviously service remote clients’ requests for data and yet no pair of servers colludes in a bid to violate said obliviousness. In exchange for such a strong security assumption, we obtain new PIR protocols exhibiting remarkable efficiency with respect to every cost metric—download, upload, computation, and round complexity—typically considered in the PIR literature. The new constructions extend a multiserver PIR protocol of Shah, Rashmi, and Ramchandran (ISIT 2014), which exhibits a remarkable property of its own: to fetch a b -bit record from a collection of r such records, the client need only download b + 1 bits total. We find that allowing “a bit more” download (and optionally introducing computational assumptions) yields a family of protocols offering very attractive trade-offs. In addition to Shah et al.’s protocol, this family includes as special cases (2-server instances of) the seminal protocol of Chor, Goldreich, Kushilevitz, and Sudan (FOCS 1995) and the recent DPF-based protocol of Boyle, Gilboa, and Ishai (CCS 2016). An implicit “folklore” axiom that dogmatically permeates the research literature on multiserver PIR posits that the latter protocols are the “most efficient” protocols possible in the perfectly and computationally private settings, respectively. Yet our findings soundly refute this supposed axiom: These special cases are (by far) the least performant representatives of our family, with essentially all other parameter settings yielding instances that are significantly faster.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
