Interactions between internet users are mediated by their devices and the
common support infrastructure in data centres. Keeping track of causality
amongst actions that take place in this distributed system is key to provide a
seamless interaction where effects follow causes. Tracking causality in large
scale interactions is difficult due to the cost of keeping large quantities of
metadata; even more challenging when dealing with resource-limited devices. In
this paper, we focus on keeping partial knowledge on causality and address
deduction from that knowledge.
We provide the first proof-theoretic causality modelling for distributed
partial knowledge. We prove computability and consistency results. We also
prove that the partial knowledge gives rise to a weaker model than classical
causality. We provide rules for offline deduction about causality and refute
some related folklore. We define two notions of forward and backward
bisimilarity between devices, using which we prove two important results.
Namely, no matter the order of addition/removal, two devices deduce similarly
about causality so long as: (1) the same causal information is fed to both. (2)
they start bisimilar and erase the same causal information. Thanks to our
establishment of forward and backward bisimilarity, respectively, proofs of the
latter two results work by simple induction on length.
%0 Journal Article
%1 Haeri2016Worlds
%A Haeri, Seyed H.
%A Van Roy, Peter
%A Baquero, Carlos
%A Meiklejohn, Christopher
%D 2016
%J Electronic Proceedings in Theoretical Computer Science
%K 68q85-models-and-methods-for-concurrent-and-distributed-computing
%P 113--127
%R 10.4204/eptcs.223.8
%T Worlds of Events: Deduction with Partial Knowledge about Causality
%U http://dx.doi.org/10.4204/eptcs.223.8
%V 223
%X Interactions between internet users are mediated by their devices and the
common support infrastructure in data centres. Keeping track of causality
amongst actions that take place in this distributed system is key to provide a
seamless interaction where effects follow causes. Tracking causality in large
scale interactions is difficult due to the cost of keeping large quantities of
metadata; even more challenging when dealing with resource-limited devices. In
this paper, we focus on keeping partial knowledge on causality and address
deduction from that knowledge.
We provide the first proof-theoretic causality modelling for distributed
partial knowledge. We prove computability and consistency results. We also
prove that the partial knowledge gives rise to a weaker model than classical
causality. We provide rules for offline deduction about causality and refute
some related folklore. We define two notions of forward and backward
bisimilarity between devices, using which we prove two important results.
Namely, no matter the order of addition/removal, two devices deduce similarly
about causality so long as: (1) the same causal information is fed to both. (2)
they start bisimilar and erase the same causal information. Thanks to our
establishment of forward and backward bisimilarity, respectively, proofs of the
latter two results work by simple induction on length.
@article{Haeri2016Worlds,
abstract = {{Interactions between internet users are mediated by their devices and the
common support infrastructure in data centres. Keeping track of causality
amongst actions that take place in this distributed system is key to provide a
seamless interaction where effects follow causes. Tracking causality in large
scale interactions is difficult due to the cost of keeping large quantities of
metadata; even more challenging when dealing with resource-limited devices. In
this paper, we focus on keeping partial knowledge on causality and address
deduction from that knowledge.
We provide the first proof-theoretic causality modelling for distributed
partial knowledge. We prove computability and consistency results. We also
prove that the partial knowledge gives rise to a weaker model than classical
causality. We provide rules for offline deduction about causality and refute
some related folklore. We define two notions of forward and backward
bisimilarity between devices, using which we prove two important results.
Namely, no matter the order of addition/removal, two devices deduce similarly
about causality so long as: (1) the same causal information is fed to both. (2)
they start bisimilar and erase the same causal information. Thanks to our
establishment of forward and backward bisimilarity, respectively, proofs of the
latter two results work by simple induction on length.}},
added-at = {2019-03-01T00:11:50.000+0100},
archiveprefix = {arXiv},
author = {Haeri, Seyed H. and Van Roy, Peter and Baquero, Carlos and Meiklejohn, Christopher},
biburl = {https://www.bibsonomy.org/bibtex/23b0b9c427aeec2df1629066a878c8294/gdmcbain},
citeulike-article-id = {14508347},
citeulike-attachment-1 = {haeri_16_worlds_1126114.pdf; /pdf/user/gdmcbain/article/14508347/1126114/haeri_16_worlds_1126114.pdf; 096ddfc9b86985f84514531e4cf7ab9f34b80ebd},
citeulike-linkout-0 = {http://arxiv.org/abs/1608.03326},
citeulike-linkout-1 = {http://arxiv.org/pdf/1608.03326},
citeulike-linkout-2 = {http://dx.doi.org/10.4204/eptcs.223.8},
comment = {Nominated for discussion at Sydney Paper Club 2018-01-04.},
day = 11,
doi = {10.4204/eptcs.223.8},
eprint = {1608.03326},
file = {haeri_16_worlds_1126114.pdf},
interhash = {7340c10434562f596feeb4d21f10473b},
intrahash = {3b0b9c427aeec2df1629066a878c8294},
issn = {2075-2180},
journal = {Electronic Proceedings in Theoretical Computer Science},
keywords = {68q85-models-and-methods-for-concurrent-and-distributed-computing},
month = aug,
pages = {113--127},
posted-at = {2017-12-26 03:39:46},
priority = {0},
timestamp = {2019-03-01T00:11:50.000+0100},
title = {{Worlds of Events: Deduction with Partial Knowledge about Causality}},
url = {http://dx.doi.org/10.4204/eptcs.223.8},
volume = 223,
year = 2016
}