The Experts below are selected from a list of 7359 Experts worldwide ranked by ideXlab platform

David Eisenstat - One of the best experts on this subject based on the ideXlab platform.

  • Fast computation by population protocols with a leader
    Distributed Computing, 2008
    Co-Authors: Dana Angluin, James Aspnes, David Eisenstat
    Abstract:

    Fast algorithms are presented for performing computations in a probabilistic population model. This is a variant of the standard population protocol model, in which finite-state agents interact in pairs under the control of an adversary scheduler, where all pairs are equally likely to be chosen for each interaction. It is shown that when a unique leader agent is provided in the initial population, the population can simulate a virtual Register Machine with high probability in which standard arithmetic operations like comparison, addition, subtraction, and multiplication and division by constants can be simulated in O ( n log^5 n ) interactions using a simple Register representation or in O ( n log^2 n ) interactions using a more sophisticated representation that requires an extra O ( n log^ O (1) n )-interaction initialization step. The central method is the extensive use of epidemics to propagate information from and to the leader, combined with an epidemic-based phase clock used to detect when these epidemics are likely to be complete. Applications include a reduction of the cost of computing a semilinear predicate to O ( n log^5 n ) interactions from the previously best-known bound of O ( n ^2 log n ) interactions and simulation of a LOGSPACE Turing Machine using O ( n log^2 n ) interactions per step after an initial O ( n log^ O (1) n )-interaction startup phase. These bounds on interactions translate into polylogarithmic time per step in a natural parallel model in which each agent participates in an expected Θ (1) interactions per time unit. Open problems are discussed, together with simulation results that suggest the possibility of removing the initial-leader assumption.

  • Fast computation by population protocols with a leader
    Lecture Notes in Computer Science, 2006
    Co-Authors: Dana Angluin, James Aspnes, David Eisenstat
    Abstract:

    Fast algorithms are presented for performing computations in a probabilistic population model. This is a variant of the standard population protocol model-in which finite-state agents interact in pairs under the control of an adversary scheduler-where all pairs are equally likely to be chosen for each interaction. It is shown that when a unique leader agent is provided in the initial population, the population can simulate a virtual Register Machine in which standard arithmetic operations like comparison, addition, subtraction, and multiplication and division by constants can be simulated in O(n log 4 n) interactions with high probability. Applications include a reduction of the cost of computing a semilinear predicate to O(n log 4 n) interactions from the previously best-known bound of O(n 2 log n) interactions and simulation of a LOGSPACE Turing Machine using the same O(n log 4 n) interactions per step. These bounds on interactions translate into O(log 4 n) time per step in a natural parallel model in which each agent participates in an expected Θ(1) interactions per time unit. The central method is the extensive use of epidemics to propagate information from and to the leader, combined with an epidemic-based phase clock used to detect when these epidemics are likely to be complete.

  • Fast computation by population protocols with a leader
    2006
    Co-Authors: Dana Angluin, James Aspnes, David Eisenstat
    Abstract:

    Fast algorithms are presented for performing computations in a probabilistic population model. This is a variant of the standard population protocol model—in which finite-state agents interact in pairs under the control of an adversary scheduler—where all pairs are equally likely to be chosen for each interaction. It is shown that when a unique leader agent is provided in the initial population, the population can simu-late a virtual Register Machine with high probability in which standard arithmetic operations like compar-ison, addition, subtraction, and multiplication and division by constants can be simulated in O(n log 5 n) interactions using a simple Register representation or in O(n log 2 n) interactions using a more sophis-ticated representation that requires an extra O(n log O(1) n)-interaction initialization step. The central method is the extensive use of epidemics to propagate information from and to the leader, combined with an epidemic-based phase clock used to detect when these epidemics are likely to be complete. Ap-plications include a reduction of the cost of computing a semilinear predicate to O(n log 5 n) interactions from the previously best-known bound of O(n 2 log n) interactions and simulation of a LOGSPACE Tur-ing Machine using the same O(n log 2 n) interactions per step. These bounds on interactions translate into polylogarithmic time per step in a natural parallel model in which each agent participates in an ex-pected Θ(1) interactions per time unit. Open problems are discussed, together with simulation results that suggest the possibility of removing the initial-leader assumption

  • Fast computation by population protocols with a leader
    2006
    Co-Authors: Dana Angluin, James Aspnes, David Eisenstat
    Abstract:

    Fast algorithms are presented for performing computations in a probabilistic population model. This is a variant of the standard population protocol model—in which finite-state agents interact in pairs under the control of an adversary scheduler—where all pairs are equally likely to be chosen for each interaction. It is shown that when a unique leader agent is provided in the initial population, the population can simulate a virtual Register Machine in which standard arithmetic operations like comparison, addition, subtraction, multiplication, and division can be simulated in O(n log 4 n) interactions with high probability. Applications include a reduction of the cost of computing a semilinear predicate to O(n log 4 n) interactions from the previously best-known bound of O(n 2 log n) interactions and simulation of a LOGSPACE Turing Machine using the same O(n log 4 n) interactions per step. These bounds on interactions translate into O(log 4 n) time per step in a natural model in which each agent participates in an expected Θ(1) interactions per time unit. The central method is the extensive use of epidemics to propagate information from and to the leader, combined with an epidemic-based phase clock used to detect when these epidemics are likely to be complete

Dana Angluin - One of the best experts on this subject based on the ideXlab platform.

  • Fast computation by population protocols with a leader
    Distributed Computing, 2008
    Co-Authors: Dana Angluin, James Aspnes, David Eisenstat
    Abstract:

    Fast algorithms are presented for performing computations in a probabilistic population model. This is a variant of the standard population protocol model, in which finite-state agents interact in pairs under the control of an adversary scheduler, where all pairs are equally likely to be chosen for each interaction. It is shown that when a unique leader agent is provided in the initial population, the population can simulate a virtual Register Machine with high probability in which standard arithmetic operations like comparison, addition, subtraction, and multiplication and division by constants can be simulated in O ( n log^5 n ) interactions using a simple Register representation or in O ( n log^2 n ) interactions using a more sophisticated representation that requires an extra O ( n log^ O (1) n )-interaction initialization step. The central method is the extensive use of epidemics to propagate information from and to the leader, combined with an epidemic-based phase clock used to detect when these epidemics are likely to be complete. Applications include a reduction of the cost of computing a semilinear predicate to O ( n log^5 n ) interactions from the previously best-known bound of O ( n ^2 log n ) interactions and simulation of a LOGSPACE Turing Machine using O ( n log^2 n ) interactions per step after an initial O ( n log^ O (1) n )-interaction startup phase. These bounds on interactions translate into polylogarithmic time per step in a natural parallel model in which each agent participates in an expected Θ (1) interactions per time unit. Open problems are discussed, together with simulation results that suggest the possibility of removing the initial-leader assumption.

  • Fast computation by population protocols with a leader
    Lecture Notes in Computer Science, 2006
    Co-Authors: Dana Angluin, James Aspnes, David Eisenstat
    Abstract:

    Fast algorithms are presented for performing computations in a probabilistic population model. This is a variant of the standard population protocol model-in which finite-state agents interact in pairs under the control of an adversary scheduler-where all pairs are equally likely to be chosen for each interaction. It is shown that when a unique leader agent is provided in the initial population, the population can simulate a virtual Register Machine in which standard arithmetic operations like comparison, addition, subtraction, and multiplication and division by constants can be simulated in O(n log 4 n) interactions with high probability. Applications include a reduction of the cost of computing a semilinear predicate to O(n log 4 n) interactions from the previously best-known bound of O(n 2 log n) interactions and simulation of a LOGSPACE Turing Machine using the same O(n log 4 n) interactions per step. These bounds on interactions translate into O(log 4 n) time per step in a natural parallel model in which each agent participates in an expected Θ(1) interactions per time unit. The central method is the extensive use of epidemics to propagate information from and to the leader, combined with an epidemic-based phase clock used to detect when these epidemics are likely to be complete.

  • Fast computation by population protocols with a leader
    2006
    Co-Authors: Dana Angluin, James Aspnes, David Eisenstat
    Abstract:

    Fast algorithms are presented for performing computations in a probabilistic population model. This is a variant of the standard population protocol model—in which finite-state agents interact in pairs under the control of an adversary scheduler—where all pairs are equally likely to be chosen for each interaction. It is shown that when a unique leader agent is provided in the initial population, the population can simu-late a virtual Register Machine with high probability in which standard arithmetic operations like compar-ison, addition, subtraction, and multiplication and division by constants can be simulated in O(n log 5 n) interactions using a simple Register representation or in O(n log 2 n) interactions using a more sophis-ticated representation that requires an extra O(n log O(1) n)-interaction initialization step. The central method is the extensive use of epidemics to propagate information from and to the leader, combined with an epidemic-based phase clock used to detect when these epidemics are likely to be complete. Ap-plications include a reduction of the cost of computing a semilinear predicate to O(n log 5 n) interactions from the previously best-known bound of O(n 2 log n) interactions and simulation of a LOGSPACE Tur-ing Machine using the same O(n log 2 n) interactions per step. These bounds on interactions translate into polylogarithmic time per step in a natural parallel model in which each agent participates in an ex-pected Θ(1) interactions per time unit. Open problems are discussed, together with simulation results that suggest the possibility of removing the initial-leader assumption

  • Fast computation by population protocols with a leader
    2006
    Co-Authors: Dana Angluin, James Aspnes, David Eisenstat
    Abstract:

    Fast algorithms are presented for performing computations in a probabilistic population model. This is a variant of the standard population protocol model—in which finite-state agents interact in pairs under the control of an adversary scheduler—where all pairs are equally likely to be chosen for each interaction. It is shown that when a unique leader agent is provided in the initial population, the population can simulate a virtual Register Machine in which standard arithmetic operations like comparison, addition, subtraction, multiplication, and division can be simulated in O(n log 4 n) interactions with high probability. Applications include a reduction of the cost of computing a semilinear predicate to O(n log 4 n) interactions from the previously best-known bound of O(n 2 log n) interactions and simulation of a LOGSPACE Turing Machine using the same O(n log 4 n) interactions per step. These bounds on interactions translate into O(log 4 n) time per step in a natural model in which each agent participates in an expected Θ(1) interactions per time unit. The central method is the extensive use of epidemics to propagate information from and to the leader, combined with an epidemic-based phase clock used to detect when these epidemics are likely to be complete

James Aspnes - One of the best experts on this subject based on the ideXlab platform.

  • Fast computation by population protocols with a leader
    Distributed Computing, 2008
    Co-Authors: Dana Angluin, James Aspnes, David Eisenstat
    Abstract:

    Fast algorithms are presented for performing computations in a probabilistic population model. This is a variant of the standard population protocol model, in which finite-state agents interact in pairs under the control of an adversary scheduler, where all pairs are equally likely to be chosen for each interaction. It is shown that when a unique leader agent is provided in the initial population, the population can simulate a virtual Register Machine with high probability in which standard arithmetic operations like comparison, addition, subtraction, and multiplication and division by constants can be simulated in O ( n log^5 n ) interactions using a simple Register representation or in O ( n log^2 n ) interactions using a more sophisticated representation that requires an extra O ( n log^ O (1) n )-interaction initialization step. The central method is the extensive use of epidemics to propagate information from and to the leader, combined with an epidemic-based phase clock used to detect when these epidemics are likely to be complete. Applications include a reduction of the cost of computing a semilinear predicate to O ( n log^5 n ) interactions from the previously best-known bound of O ( n ^2 log n ) interactions and simulation of a LOGSPACE Turing Machine using O ( n log^2 n ) interactions per step after an initial O ( n log^ O (1) n )-interaction startup phase. These bounds on interactions translate into polylogarithmic time per step in a natural parallel model in which each agent participates in an expected Θ (1) interactions per time unit. Open problems are discussed, together with simulation results that suggest the possibility of removing the initial-leader assumption.

  • Fast computation by population protocols with a leader
    Lecture Notes in Computer Science, 2006
    Co-Authors: Dana Angluin, James Aspnes, David Eisenstat
    Abstract:

    Fast algorithms are presented for performing computations in a probabilistic population model. This is a variant of the standard population protocol model-in which finite-state agents interact in pairs under the control of an adversary scheduler-where all pairs are equally likely to be chosen for each interaction. It is shown that when a unique leader agent is provided in the initial population, the population can simulate a virtual Register Machine in which standard arithmetic operations like comparison, addition, subtraction, and multiplication and division by constants can be simulated in O(n log 4 n) interactions with high probability. Applications include a reduction of the cost of computing a semilinear predicate to O(n log 4 n) interactions from the previously best-known bound of O(n 2 log n) interactions and simulation of a LOGSPACE Turing Machine using the same O(n log 4 n) interactions per step. These bounds on interactions translate into O(log 4 n) time per step in a natural parallel model in which each agent participates in an expected Θ(1) interactions per time unit. The central method is the extensive use of epidemics to propagate information from and to the leader, combined with an epidemic-based phase clock used to detect when these epidemics are likely to be complete.

  • Fast computation by population protocols with a leader
    2006
    Co-Authors: Dana Angluin, James Aspnes, David Eisenstat
    Abstract:

    Fast algorithms are presented for performing computations in a probabilistic population model. This is a variant of the standard population protocol model—in which finite-state agents interact in pairs under the control of an adversary scheduler—where all pairs are equally likely to be chosen for each interaction. It is shown that when a unique leader agent is provided in the initial population, the population can simu-late a virtual Register Machine with high probability in which standard arithmetic operations like compar-ison, addition, subtraction, and multiplication and division by constants can be simulated in O(n log 5 n) interactions using a simple Register representation or in O(n log 2 n) interactions using a more sophis-ticated representation that requires an extra O(n log O(1) n)-interaction initialization step. The central method is the extensive use of epidemics to propagate information from and to the leader, combined with an epidemic-based phase clock used to detect when these epidemics are likely to be complete. Ap-plications include a reduction of the cost of computing a semilinear predicate to O(n log 5 n) interactions from the previously best-known bound of O(n 2 log n) interactions and simulation of a LOGSPACE Tur-ing Machine using the same O(n log 2 n) interactions per step. These bounds on interactions translate into polylogarithmic time per step in a natural parallel model in which each agent participates in an ex-pected Θ(1) interactions per time unit. Open problems are discussed, together with simulation results that suggest the possibility of removing the initial-leader assumption

  • Fast computation by population protocols with a leader
    2006
    Co-Authors: Dana Angluin, James Aspnes, David Eisenstat
    Abstract:

    Fast algorithms are presented for performing computations in a probabilistic population model. This is a variant of the standard population protocol model—in which finite-state agents interact in pairs under the control of an adversary scheduler—where all pairs are equally likely to be chosen for each interaction. It is shown that when a unique leader agent is provided in the initial population, the population can simulate a virtual Register Machine in which standard arithmetic operations like comparison, addition, subtraction, multiplication, and division can be simulated in O(n log 4 n) interactions with high probability. Applications include a reduction of the cost of computing a semilinear predicate to O(n log 4 n) interactions from the previously best-known bound of O(n 2 log n) interactions and simulation of a LOGSPACE Turing Machine using the same O(n log 4 n) interactions per step. These bounds on interactions translate into O(log 4 n) time per step in a natural model in which each agent participates in an expected Θ(1) interactions per time unit. The central method is the extensive use of epidemics to propagate information from and to the leader, combined with an epidemic-based phase clock used to detect when these epidemics are likely to be complete

Liu Siqi - One of the best experts on this subject based on the ideXlab platform.

  • A Performance Survey on Stack-based and Register-based Virtual Machines
    2016
    Co-Authors: Fang Ruijie, Liu Siqi
    Abstract:

    Virtual Machines have been widely adapted for high-level programming language implementations and for providing a degree of platform neutrality. As the overall use and adaptation of virtual Machines grow, the overall performance of virtual Machines has become a widely-discussed topic. In this paper, we present a survey on the performance differences of the two most widely adapted types of virtual Machines - the stack-based virtual Machine and the Register-based virtual Machine - using various benchmark programs. Additionally, we adopted a new approach of measuring performance by measuring the overall dispatch time, amount of dispatches, fetch time, and execution time while running benchmarks on custom-implemented, lightweight virtual Machines. Finally, we present two lightweight, custom-designed, Turing-equivalent virtual Machines that are specifically designed in benchmarking virtual Machine performance - the "Conceptum" stack-based virtual Machine, and the "Inertia" Register-based virtual Machine. Our result showed that while on average the Register Machine spends 20.39% less time in executing benchmarks than the stack Machine, the stack-based virtual Machine is still faster than the virtual Machine regarding the instruction fetch time.Comment: Short paper for evaluating performance differences between a stack-based and a Register-based virtual machin

Jean-yves Marion - One of the best experts on this subject based on the ideXlab platform.

  • On tiered small jump operators
    Logical Methods in Computer Science, 2009
    Co-Authors: Jean-yves Marion
    Abstract:

    Predicative analysis of recursion schema is a method to characterize complexity classes like the class FPTIME of polynomial time computable functions. This analysis comes from the works of Bellantoni and Cook, and Leivant by data tiering. Here, we refine predicative analysis by using a ramified Ackermann's construction of a non-primitive recursive function. We obtain a hierarchy of functions which characterizes exactly functions, which are computed in O(n^k) time over Register Machine model of computation. For this, we introduce a strict ramification principle. Then, we show how to diagonalize in order to obtain an exponential function and to jump outside deterministic polynomial time. Lastly, we suggest a dependent typed lambda-calculus to represent this construction.

  • On Tiered Small Jump Operators
    2009
    Co-Authors: Jean-yves Marion
    Abstract:

    Predicative analysis of recursion schema is a method to characterize complexity classes like the class FPTIME of polynomial time computable functions. This analysis comes from the works of Bellantoni and Cook, and Leivant by data tiering. Here, we refine predicative analysis by using a ramified Ackermann’s construction of a non-primitive recursive function. We obtain a hierarchy of functions which characterizes exactly functions, which are computed in O(n k) time over Register Machine model of computation. For this, we introduce a strict ramification principle. Then, we show how to diagonalize in order to obtain an exponential function and to jump outside ∪kDTIME(n k). Lastly, we suggest a dependent typed lambda-calculus to represent this construction