Depletable Channels: Dynamics and Behaviour

Pietro Cenciarelli, Daniele Gorla and Ivano Salvo

Paper appeared in the 17th International Symposium on Fundamentals of Computation Theory (FCT 2009), Wroclaw (Poland) September 2-4, 2009.
Full version.

Abstract:

A simple model of multi-hop communication in ad-hoc networks is considered. Similar models are often adopted for studying energy efficiency and load balancing of different routing protocols. We address an orthogonal question never considered by the networking community: whether, regardless of specific protocols, two networks may be considered as equivalent from the viewpoint of the communication service they provide. Some of the concepts are burrowed from the theory of concurrency: we define a trace-based behavioural semantics for networks and equate two nets that exhibit identical sets of traces; we then characterize trace equivalence by means of intrinsic features of the equated nets; by exploiting such a characterization, we finally study the computational complexity of the proposed equivalence.

@InProceedings{CGS:FCT09,
  author    =   {P. Cenciarelli, D. Gorla and I. Salvo},
  title     =   {Depletable Channels: Dynamics and Behaviour},
  editor    =   {M. Kutylowski, M. Gebala and W. Charatonik},
  booktitle =   {Proceedings of the 17th International Symposium on Fundamentals of Computation Theory (FCT'09)},
  series    =   {LNCS},
  volume    =   {5966},
  pages     =   {50--61},
  year      =   {2009},
  publisher =   {Springer},
}