Reconciling Distributed Computing Models and Real-Time Systems

摘要: This paper 1 presents a simple real-time dis- tributed computing model for message-passing systems, which reconciles the distributed and real- time systems perspective: By just replacing instantaneous steps with of non-zero duration, we obtain that both facilitates schedul- ing analysis retains compatibility classic techniques results. So far, have developed general simulations validity con- ditions transforming algorithms from syn- chronous (without clock drift) to our vice versa, started investigating whether/which properties real are inaccurately or even wrongly captured when resorting zero step-time models. One example is (1) complexity lower bound optimal deterministic internal synchroniza- tion, turned out be ( n) in model. Motivation Executions typically modeled as sequences atomic executed time. With this assumption, it does not make differ- ence, example, whether messages arrive at processor simultaneously nicely staggered time: The processed instantaneously they arrive. abstraction hence very convenient analysis, wealth algorithms, impossibility results bounds been models em- ploy assumption (2). In however, neither in- stantaneous nor arbitrarily preemptable: A step triggered by message arriving middle execu- tion some other usually delayed until current computation nished. queuing phenomenons, depend only on actual mes- sage arrival pattern but also queuing/scheduling cipline employed. community has established powerful analyzing such effects (5), resulting worst-case response times end-to-end delays can computed. briey surveys com- puting introduced (3), times, admits without invalidating standard comput- Apart making amenable allows address teresting question