title: On the performance of a retransmission-based synchronizer.
abstract: Designing algorithms for distributed systems that provide a round abstraction is often simpler than designing for those that do not provide such an abstraction. Further, distributed systems need to tolerate various kinds of failures. The concept of a synchronizer deals with both: It constructs rounds and allows masking of transmission failures. One simple way of dealing with transmission failures is to retransmit a message until it is known that the message was successfully received. We calculate theexact valueof the average rate of a retransmission-based synchronizer in environments with probabilistic message loss, within which the synchronizer shows nontrivial timing behavior. We show how to make this calculation efficient, and present analytical results on the convergence speed. The theoretic results, based on Markov theory, are backed up with Monte Carlo simulations.
authors.affiliation: LIX, École polytechnique, 91128 Palaiseau, France.
authors.forename: Thomas
authors.initials: T
authors.lastname: Nowak
authors.affiliation: ECS Group, TU Wien, 1040 Vienna, Austria.
authors.forename: Matthias
authors.initials: M
authors.lastname: Függer
authors.affiliation: ECS Group, TU Wien, 1040 Vienna, Austria.
authors.forename: Alexander
authors.initials: A
authors.lastname: Kößler
keywords: Markov theory; Probabilistic environment; Round-based algorithms; Simulation; Synchronizer