Name
Abstract | ||
|---|---|---|
Termination is an important non-functional property of distributed algorithms. In an event-driven setting, the interesting aspect of termination is the possibility of control flow loops through communication, which this paper aims to investigate.
In practice, it is often difficult to spot the possible communication behaviour of an algorithm at a glance. With a static analysis, the design process can be supported by visualizing possible flow of messages and give hints on possible sources of non-termination.
We propose a termination analysis for distributed algorithms formulated in an event-driven specification language. The idea is to construct a message flow graph describing the possible communication between components (input-action pairs). We show that acyclicity of that graph implies termination. While many interesting algorithms indeed contain cycles, we also suggest ways of detecting cycles which cannot lead to non-termination.
As a practical evaluation, we describe a concrete programming language together with a tool for automated termination analysis.
|
Year | DOI | Venue |
|---|---|---|
2019 | 10.1145/3328905.3329500 | Proceedings of the 13th ACM International Conference on Distributed and Event-based Systems |
Keywords | Field | DocType |
algorithm specification, distributed algorithms, event-driven, message flow, programming languages, static analysis, termination | Computer science,Termination analysis,Distributed algorithm,Distributed computing | Conference |
ISBN | Citations | PageRank |
978-1-4503-6794-3 | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Felix Wiemuth | 1 | 0 | 0.34 |
| Peter Amthor | 2 | 13 | 3.24 |
| Winfried E. Kühnhauser | 3 | 55 | 15.07 |