Self-assembling Trees

Vincent Danos, Jean Krivine, Fabien Tarissan

Research output: Contribution to journalArticlepeer-review


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
Issue number1
Publication statusPublished - 1 May 2007


  • CCS
  • Distributed Consensus
  • RCCS
  • Self Assembling


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

Cite this