Self-assembling Trees

Vincent Danos, Jean Krivine, Fabien Tarissan

Research output: Contribution to journalArticlepeer-review

Abstract

RCCS is a variant of Milner's CCS where processes are allowed a controlled form of backtracking. It turns out that the RCCS reinterpretation of a CCS process is equivalent, in the sense of weak bisimilarity, to its causal transition system in CCS. This can be used to develop an efficient method for designing distributed algorithms, which we illustrate here by deriving a distributed algorithm for assembling trees. Such a problem requires solving a highly distributed consensus, and a comparison with a traditional CCS-based solution shows that the code we obtain is shorter, easier to understand, and easier to prove correct by hand, or even to verify.
Original languageEnglish
Pages (from-to)19-32
Number of pages14
JournalElectronic Notes in Theoretical Computer Science
Volume175
Issue number1
DOIs
Publication statusPublished - 1 May 2007

Keywords

  • CCS
  • Distributed Consensus
  • RCCS
  • Self Assembling

Fingerprint Dive into the research topics of 'Self-assembling Trees'. Together they form a unique fingerprint.

Cite this