Abstract
We consider the problem of simulating traditional population protocols under
weaker models of communication, which include one-way interactions (as opposed
to two-way interactions) and omission faults (i.e., failure by an agent to read
its partner's state during an interaction), which in turn may be detectable or
undetectable. We focus on the impact of a leader, and we give a complete
characterization of the models in which the presence of a unique leader in the
system allows the construction of simulators: when simulations are possible, we
give explicit protocols; when they are not, we give proofs of impossibility.
Specifically, if each agent has only a finite amount of memory, the simulation
is possible only if there are no omission faults. If agents have an unbounded
amount of memory, the simulation is possible as long as omissions are
detectable. If an upper bound on the number of omissions involving the leader
is known, the simulation is always possible, except in the one-way model in
which one side is unable to detect the interaction.
Users
Please
log in to take part in the discussion (add own reviews or comments).