  In this paper we consider a variant of population protocols in which agents
are allowed to be connected by edges, known as the constructors model. During
an interaction between two agents the relevant connecting edge can be formed,
maintained or eliminated by the transition function. The contributions of this
paper are manifold.
  -- We propose and analyse a novel type of phase clocks allowing to count
parallel time $\Theta(n\log n)$ in the constructors model. This new type of
clocks can be also implemented in the standard population protocol model
assuming a unique leader is available.
  -- The new clock enables an optimal $O(n\log n)$ parallel time spanning line
construction which improves dramatically on the best previously known $O(n^2)$
parallel time solution.
  -- We define a probabilistic version of bubble-sort in which random
comparisons are allowed only between adjacent numbers in the sequence being
sorted. We show that rather surprisingly this probabilistic bubble-sort
requires $O(n^2)$ comparisons in expectation, i.e., on the same level as its
deterministic counterpart.
  -- We propose the first self-replication protocol allowing to reproduce a
strand (line-segment carrying information) of length $k$ in parallel time
$O(n(k+\log n)).$ This result is based on the probabilistic bubble-sort
argument. This protocol permits also simultaneous replication where $l$ copies
of the strand can be obtained in time $O(n(k+\log n)\log l).$
  All protocols in this paper operate with high probability.
