# Performance evaluation of Fischer’s protocol through steady-state analysis of Markov regenerative processes

## S. Martina, M. Paolieri, T. Papini, E. Vicario

**Abstract:** Fischer’s protocol is a well-known timed mechanism through which a set
of processes can synchronize access to a critical section without
relying on atomic test-and-set operations, as might occur in a
distributed environment or on a low-level computing platform. The
protocol is based on a deterministic waiting time that can be defined
so as to guarantee that possible interference due to concurrent
accesses with random bounded delays be resolved with certainty. While
protocol correctness descends from firm lower and upper bounds on
waiting times and random delays, performance attained in
synchronization also depends on continuous distributions of delays.
Performance evaluation of a correct implementation thus requires the
solution of a non-Markovian model whose underlying stochastic process
falls in the class of Markov regenerative processes (MRPs) with
multiple concurrent delays with non-exponential duration. Numerical
solution of this class of models is to a large extent still an open
problem. We provide a twofold contribution. We first introduce a novel
method for the steady-state analysis of MRPs where regenerations are
reached in a bounded number of discrete events, which enlarges the
class amenable to numerical solution by allowing multiple concurrent
timers with non-exponential distributions. The proposed technique is
then applied to Fischer’s protocol by characterizing the latency
overhead due to synchronization, which comprises the first case where
performance of the protocol is quantitatively assessed by jointly
accounting for firm bounds and continuous distributions of delays.

Stochastic ProcessesPerformance ModelsApplications

copy bib | save bib | save pdf | go to publisher

🏠 Home