University of Sussex
Browse

File(s) not publicly available

A Theory of System Behaviour in the Presence of Node and Link Failures .

presentation
posted on 2023-06-08, 07:27 authored by Adrian Francalanza, Matthew Hennessy
We develop a behavioural theory of distributed programs in the presence of failures such as nodes crashing and links breaking. The framework we use is that of Dp, a language in which located processes, or agents, may migrate between dynamically created locations. In our extended framework, these processes run on a distributed network, in which individual nodes may crash in fail-stop fashion or the links between these nodes may become permanently broken. The original language, Dp, is also extended by a ping construct for detecting and reacting to these failures. We define a bisimulation equivalence between these systems, based on labelled actions which record, in addition to the effect actions have on the processes, the effect on the actual state of the underlying network and the view of this state known to observers. We prove that the equivalence is fully abstract, in the sense that two systems will be differentiated if and only if, in some sense, there is a computational context, consisting of a surrounding network and an observer, which can see the difference.

History

Publication status

  • Published

Publisher

Springer Verlag

Volume

3653/2

Page range

368-382

Pages

15.0

Presentation Type

  • paper

Event name

Concur 2005 - Concurrency Theory

Event type

conference

ISBN

3-540-28309-9

Department affiliated with

  • Informatics Publications

Notes

Originality: First systematic formal treatment of agent behaviour in the presence of network communication failures. Rigour: Uses formal methods, including labelled transition systems and bisimulation equivalence. Significance: First paper on the interaction between node failures and link failures. Impact: Work beginning to appear, which uses our formal treatment of failures in different settings. Outlet: Top international conference in concurrency theory, with acceptance rate around 25%. 14 citations in Google Scholar. Final version will appear in Information and Computation.

Full text available

  • No

Peer reviewed?

  • Yes

Legacy Posted Date

2012-02-06

Usage metrics

    University of Sussex (Publications)

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC