
handle: 1974/32917
The concept of real time has different meanings in the systems and theory communities. Thus, the existing formal real-time models do not capture all the practically relevant aspects of such computations. This article proposes a new definition that, we believe, allows a unified treatment of all practically meaningful variants of realtime computations. We use the developed formalism to mode two important features of real-time algorithms, namely the presence of deadlines and the real-time arrival of input data. We also emphasize the expressive power of our model by using it to formalize aspects from the areas of real-time database systems and ad hoc networks. We offer formulations of the recognition problem for real-time database systems and of the routing problem in ad hoc networks. Finally, we suggest a variant of our formalism that is suited for modelling parallel distributed real-time algorithms. We believe that the proposed formalism is a first step towards a unified and realistic complexity theory for real-time parallel computations.
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 6 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
