4 results on '"Eftekhari, Mahsa"'
Search Results
2. Computation in population protocols: exact majority, uniform computation, and the dynamic model
- Author
-
Eftekhari, Mahsa
- Subjects
Computer science ,Distributed Computing ,Population protocols - Abstract
We study population protocols, a model of distributed computing appropriate for modeling well-mixed chemical reaction networks and other physical systems where agents exchange information in pairwise interactions, but have no control over their schedule of interaction partners.Concretely, *population protocols*are asynchronous, complete networks that consist of computational entities called *agents*with no control over the schedule of interactions with other agents.In a population of $n$ agents,repeatedly a random pair of agents are chosen to interact,each observing the state of the other agent before updating its own state.Population protocols are equivalent to the model of chemical reaction networks, describing abstract chemical reactions such as $A+B \rightarrow C+D$, when the latter is subject to the restriction that all reactions have two reactants and two products, and all rate constants are 1.In this thesis, we demonstrate an algorithmic advance for the exact majority problem: starting in a population of $n$ agents, each with one of two opinions $A$ or $B$, the agents must determine whether there are more $A$, more $B$, or a tie. The proposed algorithm is \emph{nonuniform}: assume that the agents are initialized with an approximate estimate of $n$(specifically, a value that is $\geq \log n$).We introduce *uniform* population protocols:networks of anonymous agents whose pairwise interactions are chosen at random,where each agent uses an *identical* transition algorithm that does not depend on the population size $n$.Moreover, we study almost optimal protocols that solve static counting problem: the *counting* problem is that of designing a protocol so that $n$ agents, all starting in the same state, eventually converge to states where each agent encodes in its state an exact or approximate description of population size $n$.Finally, we introduce population protocols with dynamic size and finish this thesis with a novel counting protocol robust to an adversary who can add or remove agents. more...
- Published
- 2022
Catalog
3. Dynamic size counting in population protocols
- Author
-
Doty, David and Eftekhari, Mahsa
- Subjects
FOS: Computer and information sciences ,Theory of computation → Models of computation ,F.1 ,size counting ,Loosely-stabilizing ,Computer Science - Distributed, Parallel, and Cluster Computing ,Computer Science - Data Structures and Algorithms ,Data Structures and Algorithms (cs.DS) ,F.2.2 ,68M18, 68W15 ,Distributed, Parallel, and Cluster Computing (cs.DC) ,population protocols ,Theory of computation → Distributed algorithms - Abstract
The population protocol model describes a network of anonymous agents that interact asynchronously in pairs chosen at random. Each agent starts in the same initial state s. We introduce the dynamic size counting problem: approximately counting the number of agents in the presence of an adversary who at any time can remove any number of agents or add any number of new agents in state s. A valid solution requires that after each addition/removal event, resulting in population size n, with high probability each agent "quickly" computes the same constant-factor estimate of the value log₂(n) (how quickly is called the convergence time), which remains the output of every agent for as long as possible (the holding time). Since the adversary can remove agents, the holding time is necessarily finite: even after the adversary stops altering the population, it is impossible to stabilize to an output that never again changes. We first show that a protocol solves the dynamic size counting problem if and only if it solves the loosely-stabilizing counting problem: that of estimating log n in a fixed-size population, but where the adversary can initialize each agent in an arbitrary state, with the same convergence time and holding time. We then show a protocol solving the loosely-stabilizing counting problem with the following guarantees: if the population size is n, M is the largest initial estimate of log n, and s is the maximum integer initially stored in any field of the agents' memory, we have expected convergence time O(log n + log M), expected polynomial holding time, and expected memory usage of O(log²(s) + (log log n)²) bits. Interpreted as a dynamic size counting protocol, when changing from population size n_prev to n_next, the convergence time is O(log n_next + log log n_prev)., LIPIcs, Vol. 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022), pages 13:1-13:18 more...
- Published
- 2022
4. Exact size counting in uniform population protocols in nearly logarithmic time
- Author
-
Doty, David, Eftekhari, Mahsa, Michail, Othon, Spirakis, Paul G., and Theofilatos, Michail
- Subjects
FOS: Computer and information sciences ,Computer Science::Multiagent Systems ,Computer Science - Computational Complexity ,Computer Science - Distributed, Parallel, and Cluster Computing ,TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY ,Distributed, Parallel, and Cluster Computing (cs.DC) ,Computational Complexity (cs.CC) ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
We study population protocols: networks of anonymous agents that interact under a scheduler that picks pairs of agents uniformly at random. The _size counting problem_ is that of calculating the exact number $n$ of agents in the population, assuming no leader (each agent starts in the same state). We give the first protocol that solves this problem in sublinear time. The protocol converges in $O(\log n \log \log n)$ time and uses $O(n^{60})$ states ($O(1) + 60 \log n$ bits of memory per agent) with probability $1-O(\frac{\log \log n}{n})$. The time complexity is also $O(\log n \log \log n)$ in expectation. The time to converge is also $O(\log n \log \log n)$ in expectation. Crucially, unlike most published protocols with $\omega(1)$ states, our protocol is _uniform_: it uses the same transition algorithm for any population size, so does not need an estimate of the population size to be embedded into the algorithm. A sub-protocol is the first uniform sublinear-time leader election population protocol, taking $O(\log n \log \log n)$ time and $O(n^{18})$ states. The state complexity of both the counting and leader election protocols can be reduced to $O(n^{30})$ and $O(n^{9})$ respectively, while increasing the time to $O(\log^2 n)$. more...
- Published
- 2018
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.