Reactive Pls for Distributed Decision
Abstract. We generalize the definition of Proof Labeling Schemes toreactive systems, that is, systems where the configuration is supposedto keep changing forever. As an example, we address the main classicaltest case of reactive tasks, namely, the task of token passing. DifferentRPLSs are given for the cases that the network is assumed to be a treeor an anonymous ring, or a general graph, and the sizes of RPLSs’ labelsare analyzed. We also address the question whether an RPLS exists.First, on the positive side, we show that there exists an RPLS for anydistributed task for a family of graphs with unique identities. For the caseof anonymous networks (even for the special case of rings), interestingly,it is known that no token passing algorithm is possible even if the numbern of nodes is known. Nevertheless, we show that an RPLS is possible.On the negative side, we show that if one drops the assumption that nis known, then the construction becomes impossible
Year of publication: |
[2022]
|
---|---|
Authors: | Chen, Jiaqi ; Dolev, Shlomi ; Kutten, Shay |
Publisher: |
[S.l.] : SSRN |
Saved in:
freely available
Saved in favorites
Similar items by person
-
Chen, Jiaqi, (2001)
-
Volatility-selling strategies carry potential systemic cost
Chen, Jiaqi, (2013)
-
Hedge fund dynamic market sensitivity
Chen, Jiaqi, (2012)
- More ...