Time bounds for real-time process control in the presence of timing uncertainty
Hagit Attiya, Nancy Ann Lynch · 2003
A timing-based variant of the mutual-exclusion problem is considered. In this variant, only an upper bound on the time it takes to release the resource is known, and no explicit signal is sent when the resource is released; furthermore, the only mechanism to measure real time is an inaccurate clock, whose tick intervals take time between two constants. A new technique involving shifting and shrinking executions is combined with a careful analysis of the best allocation policy to prove a corresponding lower bound when control is distributed among processes connected by communication lines with an upper bound for message delivery time. These combinatorial results shed some light on modeling and verification issues related to real-time systems.>