102,139 research outputs found
Time, Clocks and Efficiency of Population Protocols (Invited Paper)
No full textThe model of population protocols is used to study distributed processes based on pairwise interactions between simple anonymous agents drawn from a large population of size n. The order in which agents meet in pairs is determined by the random scheduler, s.t., each consecutive pair is chosen uniformly at random. After each interaction the state of the relevant agents are amended according to the predefined transition function (the actual code of the algorithm) which governs the considered process. The state space of agents is often fixed and the size n is not known in advance, i.e., not hard-coded in the transition function. We assume that a population protocol starts in the predefined initial configuration of agents' states representing the input. And if successful, the protocol stabilises in a final configuration of states forming the output representing the solution to the considered problem.
The time complexity of a population protocol refers to the number of interactions required to stabilise this protocol in a final configuration. We also define parallel time as the time complexity divided by n. Note that the parallel time of the system and the expected local time of each agent, i.e., the number of interactions observed by each agent, are correlated. Several mechanisms, known as phase clocks, have been developed to measure parallel time more accurately than counting local interactions. Most of the clocks target counting Θ(log n) parallel time required to fully synchronise all agents in the population. There are leader (and junta) based phase clocks which utilise a fixed number of states [D. Angluin et al., 2008; L. Gąsieniec and G. Stachowiak, 2021]. This type of clocks allows also counting any poly-logarithmic time while preserving fix state utilisation. The other type refers to leaderless clocks utilising Θ(log n) states [D. Alistarh et al., 2018; D. Doty et al., 2021]. This type allows approximate counting of parallel time as fixed resolution clocks [D. Doty et al., 2021] or oscillators [D. Alistarh et al., 2018]. Another clock type introduced recently in [L. Gąsieniec et al., 2021] enables counting Θ(nlog n) parallel time utilising a fixed number of states and either leaders or connections in the network constructor model.
We also discuss parallel efficiency of population protocols referring to protocols operating in Θ(polylog n) parallel time, we propose extensions of the population protocol model leading to further improvement in state and time utilisation, and we state some open problems
Deterministic non-adaptive contention resolution on a shared channel
No full textIn a multiple access channel, autonomous stations are able to transmit and listen to a shared device. A fundamental problem, called contention resolution, is to allow any station to successfully deliver its message by resolving the conflicts that arise when several stations transmit simultaneously. Despite a long history on such a problem, most of the results deal with the static setting when all stations start simultaneously, while many fundamental questions remain open in the realistic scenario when stations can join the channel at arbitrary times. In this paper, we explore the impact that three major channel features (asynchrony among stations, knowledge of the number of contenders and possibility of switching off stations after a successful transmission) can have on the time complexity of non-adaptive deterministic algorithms. We establish upper and lower bounds allowing to understand which parameters permit time-efficient contention resolution and which do not.(c) 2022 Elsevier Inc. All rights reserved
Deterministic Contention Resolution without Collision Detection: Throughput vs Energy
No full textThis paper studies the Contention resolution problem on a shared channel (also known as a multiple access channel). A set of n stations are connected to a common device and are able to communicate by transmitting and listening. Each station may have a message to broadcast. At any round, a transmission is successful if and only if exactly one station is transmitting at that round. Simultaneous transmissions interfere one another and, as a result, the respective messages are lost. The Contention resolution is the fundamental problem of scheduling the transmissions into rounds in such a way that any station delivers successfully its message on the channel.We consider a general dynamic distributed setting. We assume that the stations can join (or be activated on) the channel at arbitrary times (dynamic scenario). This has to be contrasted with the simplified static scenario, in which all stations are assumed to be activated simultaneously. We also assume that the stations are not able to detect whether a collision among simultaneous transmissions occurred (model without collision detection). Finally, there is no global clock in the system: each station measures the time using its own local clock which starts when the station is activated and is possibly out of sync with respect to the other stations.We study non-adaptive deterministic distributed algorithms for the contention resolution problem and assess their efficiency both in terms of channel utilization (also called throughput) and energy consumption.While this topic has been quite extensively examined for randomized algorithms, this is, to the best of our knowledge, the first paper to discuss to which extent deterministic contention resolution algorithms can be efficient in terms of both channel utilization and energy consumption.Our results imply an exponential separation gap between static and dynamic setting with respect to channel utilization. We also show that the knowledge of the number of participating stations k (or an upper bound on it) has a substantial impact on the energy consumption
Brief Announcement: Deterministic Contention Resolution on a Shared Channel
No full textA shared channel, also called multiple-access channel, is one of the fundamental communication models. Autonomous entities communicate over a shared medium, and one of the main challenges is how to efficiently resolve collisions occurring when more than one entity attempts to access the channel at the same time. In this work we explore the impact of asynchrony, knowledge (or linear estimate) of the number of contenders, and acknowledgments, on both latency and channel utilization for the Contention resolution problem with non-adaptive deterministic algorithms
New Clocks, Optimal Line Formation and Self-Replication Population Protocols
No full textIn this paper we consider a known variant of the standard population protocol model in which agents are allowed to be connected by edges, referred to as the network constructor model. During an interaction between two agents the relevant connecting edge can be formed, maintained or eliminated by the transition function. Since pairs of agents are chosen uniformly at random the status of each edge is updated every Θ(n2) interactions in expectation which coincides with Θ(n) parallel time. This phenomenon provides a natural lower bound on the time complexity for any non-trivial network construction designed for this variant. This is in contrast with the standard population protocol model in which efficient protocols operate in O(poly log n) parallel time. The main focus of this paper is on efficient manipulation of linear structures including formation, self-replication and distribution (including pipelining) of complex information in the adopted model. We propose and analyze a novel edge based phase clock counting parallel time Θ(n log n) in the network constructor model, showing also that its leader based counterpart provides the same time guarantees in the standard population protocol model. Note that all currently known phase clocks can count parallel time not exceeding O(poly log n). We prove that any spanning line formation protocol requires Ω(n log n) parallel time if high probability guaranty is imposed. We also show that the new clock enables an optimal O(n log n) parallel time spanning line construction, which improves dramatically on the best currently known O(n2) parallel time protocol, solving the main open problem in the considered model [24]. We propose a new probabilistic bubble-sort algorithm in which random comparisons and transfers are limited to the adjacent positions in the sequence. Utilising a novel potential function reasoning we show that rather surprisingly this probabilistic sorting procedure requires O(n2) comparisons in expectation and whp, and is on par with its deterministic counterpart. We propose the first population protocol allowing self-replication of a strand of an arbitrary length k (carrying k-bit message of size independent of the state space) in parallel time O(n(k + log n)). The bit pipelining mechanism and the time complexity analysis of self-replication process mimic those used in the probabilistic bubble-sort argument. The new protocol permits also simultaneous self-replication, where l copies of the strand can be created in parallel in time O(n(k+log n) log l). We also discuss application of the strand self-replication protocol to pattern matching. All protocols are always correct and provide time guarantees with high probability defined as 1−n−η, for a constant η > 0
Subquadratic non-adaptive threshold group testing
No full textWe consider threshold group testing – a generalization of group testing, which asks to identify a set of positive individuals in a population, by performing tests on pools of elements. Each test is represented by a subset Q of individuals and its output is yes if Q contains at least one positive element and no otherwise. Threshold group testing is the natural generalization, introduced by P. Damaschke in 2005, arising when we are given a threshold t>0 and the answer to a test Q is yes if Q contains at least t positives and no otherwise. We give upper and lower bounds for this general problem, showing a complexity separation with the classical group testing. Next, we introduce a further generalization in which the goal is minimizing not only the number of tests, but also the number of thresholds which is related to the accuracy of the tests
Brief Announcement: New Clocks, Fast Line Formation and Self-Replication Population Protocols
No full textIn this paper we consider a known variant of the standard population protocol model in which agents can be connected by edges, referred to as the network constructor model. During an interaction between two agents the relevant connecting edge can be formed, maintained or eliminated by the transition function. The state space of agents is fixed (constant size) and the size n of the population is not known, i.e., not hard-coded in the transition function.
Since pairs of agents are chosen uniformly at random the status of each edge is updated every Θ(n²) interactions in expectation which coincides with Θ(n) parallel time. This phenomenon provides a natural lower bound on the time complexity for any non-trivial network construction designed for this variant. This is in contrast with the standard population protocol model in which efficient protocols operate in O(polylog n) parallel time.
The main focus in this paper is on efficient manipulation of linear structures including formation, self-replication and distribution (including pipelining) of complex information in the adopted model.
- We propose and analyse a novel edge based phase clock counting parallel time Θ(nlog n) in the network constructor model, showing also that its leader based counterpart provides the same time guaranties in the standard population protocol model. Note that all currently known phase clocks can count parallel time not exceeding O(polylog n).
- The new clock enables a nearly optimal O(nlog n) parallel time spanning line construction (a key component of universal network construction), which improves dramatically on the best currently known O(n²) parallel time protocol, solving the main open problem in the considered model [O. Michail and P. Spirakis, 2016].
- We propose a new probabilistic bubble-sort algorithm in which random comparisons and transfers are allowed only between the adjacent positions in the sequence. Utilising a novel potential function reasoning we show that rather surprisingly this probabilistic sorting (via conditional pipelining) procedure requires O(n²) comparisons in expectation and whp, and is on par with its deterministic counterpart.
- We propose the first population protocol allowing self-replication of a strand of an arbitrary length k (carrying a k-bit message of size independent of the state space) in parallel time O(n(k+log n)). The pipelining mechanism and the time complexity analysis of the strand self-replication protocol mimic those used in the probabilistic bubble-sort. The new protocol permits also simultaneous self-replication, where l copies of the strand can be created in time O(n(k+log n)log l). Finally, we discuss application of the strand self-replication protocol to pattern matching. Our protocols are always correct and provide time guaranties with high probability defined as 1-n^{-η}, for a constant η > 0
Data for article: Enhanced second harmonic generation performance in PPLN crystal using integrated fiber microlenses
No full textFiles include the data presented in the manuscript entitled: "Enhanced second harmonic generation performance in PPLN crystal using integrated fiber microlenses" by S. Matczak, D. Stachowiak and G. Soboń.Figure 2a presents the optical spectrum of the femtosecond laser used in the experiment.Figure 3 presents the measured second harmonic average power for different PPLN QPM periods in the reference bulk optics configurations.Figure 5 presents numerical calculations of beam propagation in air and in the PPLN crystal.Figure 6 presents the measured second harmonic average power for different PPLN QPM periods in a setup with the fabricated microlenses.Figure 7 presents the output characteristic of the femtosecond laser after the PPLN nonlinear crystal: (a) SHG spectra corresponding to all nine QPM periods, (b) corresponding pulse autocorrelations measurement with fitted pulse duration.</p
- …
