MobilityReadingGroup

Buffered Communication Analysis in Distributed Multiparty Sessions

Pierre-Malo DENIÉLOU, Nobuko YOSHIDA

Many communication-centred systems today rely on asynchronous messaging among distributed peers to make efficient use of parallel execution and resource access. With such asynchrony, the communication buffers can happen to grow inconsiderately over time. This paper proposes a static verification methodology based on multiparty session types which can efficiently compute the upper bounds on buffer sizes. Our analysis relies on a uniform causality audit of the entire collaboration pattern — an examination that is not always possible from each end-point type. We extend this method to design algorithms that allocate communication channels in order to optimise the memory requirements of session executions. From these analyses, we propose two refinements methods which respect buffer bounds: a global protocol refinement that automatically inserts confirmation messages to guarantee stipulated buffer sizes and a local protocol refinement to optimise asynchronous messaging without buffer overflow. Finally our work is applied to overcome a buffer overflow problem of the multi-buffering algorithm.

@inproceedings{DY2010,
  author = {Pierre-Malo Deniélou and Nobuko Yoshida},
  title = {{Buffered Communication Analysis in Distributed Multiparty Sessions}},
  booktitle = { 21th International Conference on Concurrency Theory},
  series = {LNCS},
  volume = {6269},
  pages = {343--357},
  publisher = {Springer},
  year = 2010
}

@inproceedings{DY2010,
  author = {Pierre-Malo Deniélou and Nobuko Yoshida},
  title = {{Buffered Communication Analysis in Distributed Multiparty Sessions}},
  booktitle = { 21th International Conference on Concurrency Theory},
  series = {LNCS},
  volume = {6269},
  pages = {343--357},
  publisher = {Springer},
  doi = "10.1007/978-3-642-15375-4_24",
  year = 2010
}