nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

Resilient Distributed Collection Through Information Speed Thresholds

verfasst von : Giorgio Audrito, Sergio Bergamini, Ferruccio Damiani, Mirko Viroli

Erschienen in: Coordination Models and Languages

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

One of the key coordination problems in physically-deployed distributed systems, such as mobile robots, wireless sensor networks, and IoT systems in general, is to provide notions of “distributed sensing” achieved by the strict, continuous cooperation and interaction among individual devices. An archetypal operation of distributed sensing is data summarisation over a region of space, by which several higher-level problems can be addressed: counting items, measuring space, averaging environmental values, and so on. A typical coordination strategy to perform data summarisation in a peer-to-peer scenario, where devices can communicate only with a neighbourhood, is to progressively accumulate information towards one or more collector devices, though this typically exhibits problems of reactivity and fragility, especially in scenarios featuring high mobility. In this paper, we propose coordination strategies for data summarisation involving both idempotent and arithmetic aggregation operators, with the idea of controlling the minimum information propagation speed, so as to improve the reactivity to input changes. Given suitable assumptions on the network model, and under the restriction of no data loss, these algorithms achieve optimal reactivity. By empirical evaluation via simulation, accounting for various sources of volatility, and comparing to other existing implementations of data summarisation algorithms, we show that our algorithms are able to retain adequate accuracy even in high-variability scenarios where all other algorithms are significantly diverging from correct estimations.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Time-Fluid Field-Based Coordination

Nächstes Kapitel Refined Mean Field Analysis: The Gossip Shuffle Protocol Revisited

Event structures for Petri Nets are used to model a spectrum of possible evolutions of a system, hence include also an incompatibility relation, discriminating between alternate future histories and modelling non-deterministic choice. However, following [21], we use event structures to model a “timeless” unitary history of events, thus avoiding the need for an incompatibility relation.

In reality, the communication range of a node is very irregular. As suggested by Zhou et al. [35], such an irregular radius can be bounded, justifying the usage of a fixed quantity.

Note that this quantity can be computed with reasonable accuracy even in absence of a global clock [10].

Also known as the count to infinity problem in routing algorithms.

We also used the notation \(w_\delta (\epsilon ')\) as alias of \(w_{\epsilon ''}(\epsilon ')\) where \(\delta (\epsilon '') = \delta \).

If no neighbour satisfies \({{\,\mathrm{surelyConnected}\,}}_{\epsilon '}(\epsilon )\), the no-data-loss requirement is not satisfiable and the threshold is set to \(-\infty \), thus falling back to a gossip algorithm.

We also need to guarantee that a message from an event \(\epsilon \) is not able to reach more than one event on a same device, that is, messages are not retained across rounds.

If no neighbour satisfies \({{\,\mathrm{surelyConnected}\,}}_{\epsilon '}(\epsilon )\), the no-data-loss requirement is not satisfiable and we select the neighbour \(m(\epsilon )\) minimising the probability of data loss.

As the variance between the runs for arithmetic aggregation was significantly high, data was aggregated with median instead of mean.

The actual code experiment is available at https://bitbucket.org/gaudrito/experiment-optimal-collection.

Aldinucci, M., Bagnasco, S., Lusso, S., Pasteris, P., Vallero, S., Rabellino, S.: The open computing cluster for advanced data manipulation (OCCAM). In: The 22nd International Conference on Computing in High Energy and Nuclear Physics (CHEP), San Francisco, USA (2016)

Audrito, G., Beal, J., Damiani, F., Pianini, D., Viroli, M.: The share operator for field-based coordination. In: Riis Nielson, H., Tuosto, E. (eds.) COORDINATION 2019. LNCS, vol. 11533, pp. 54–71. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-22397-7_4CrossRefMATH

Audrito, G., Beal, J., Damiani, F., Viroli, M.: Space-time universality of field calculus. In: Di Marzo Serugendo, G., Loreti, M. (eds.) Coordination Models and Languages. COORDINATION 2018. LNCS, vol 10852, pp. 1–20 Springer, Cham (2018). https://doi.org/10.1007/978-3-319-92408-3_1

Audrito, G., Bergamini, S.: Resilient blocks for summarising distributed data. In: 1st Workshop on Architectures, Languages and Paradigms for IoT (ALP4IoT), pp. 23–26 (2017). https://doi.org/10.4204/EPTCS.264.3

Audrito, G., Bergamini, S., Damiani, F., Viroli, M.: Effective collective summarisation of distributed data in mobile multi-agent systems. In: 18th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), pp. 1618–1626. IFAAMAS (2019). https://doi.org/10.5555/3306127.3331882

Audrito, G., Casadei, R., Damiani, F., Viroli, M.: Compositional blocks for optimal self-healing gradients. In: Self-Adaptive and Self-Organizing Systems (SASO), pp. 91–100. IEEE (2017). https://doi.org/10.1109/SASO.2017.18

Audrito, G., Damiani, F., Viroli, M.: Aggregate graph statistics. In: 1st Workshop on Architectures, Languages and Paradigms for IoT (ALP4IoT), pp. 18–22 (2017). https://doi.org/10.4204/EPTCS.264.2

Audrito, G., Damiani, F., Viroli, M.: Optimally-self-healing distributed gradient structures through bounded information speed. In: Jacquet, J.-M., Massink, M. (eds.) COORDINATION 2017. LNCS, vol. 10319, pp. 59–77. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-59746-1_4CrossRef

Audrito, G., Damiani, F., Viroli, M.: Optimal single-path information propagation in gradient-based algorithms. Sci. Comput. Program. 166, 146–166 (2018). https://doi.org/10.1016/j.scico.2018.06.002CrossRef

10.

Audrito, G., Damiani, F., Viroli, M., Bini, E.: Distributed real-time shortest-paths computations with the field calculus. In: IEEE Real-Time Systems Symposium (RTSS), pp. 23–34. IEEE Computer Society (2018). https://doi.org/10.1109/RTSS.2018.00013

11.

Audrito, G., Viroli, M., Damiani, F., Pianini, D., Beal, J.: A higher-order calculus of computational fields. ACM Trans. Comput. Log. 20(1), 5:1–5:55 (2019). https://doi.org/10.1145/3285956MathSciNetCrossRefMATH

12.

Beal, J.: Flexible self-healing gradients. In: ACM Symposium on Applied Computing (SAC), pp. 1197–1201. SAC 2009. ACM (2009). https://doi.org/10.1145/1529282.1529550

13.

Beal, J., Michel, O., Schultz, U.P.: Spatial computing: distributed systems that take advantage of our geometric world. ACM Trans. Auton. Adapt. Syst. 6(2), 11:1–11:3 (2011). https://doi.org/10.1145/1968513.1968514CrossRef

14.

Beal, J., Pianini, D., Viroli, M.: Aggregate programming for the Internet of Things. IEEE Comput. 48(9), 22–30 (2015). https://doi.org/10.1109/MC.2015.261CrossRef

15.

Beal, J., Usbeck, K., Loyall, J., Rowe, M., Metzler, J.: Adaptive opportunistic airborne sensor sharing. ACM Trans. Auton. Adapt. Syst. 13(1), 61–629 (2018). https://doi.org/10.1145/3179994CrossRef

16.

Bicocchi, N., Mamei, M., Zambonelli, F.: Self-organizing virtual macro sensors. ACM Trans. Auton. Adapt. Syst. 7(1), 21–228 (2012). https://doi.org/10.1145/2168260.2168262CrossRef

17.

Casadei, R., Pianini, D., Viroli, M., Natali, A.: Self-organising coordination regions: a pattern for edge computing. In: Riis Nielson, H., Tuosto, E. (eds.) COORDINATION 2019. LNCS, vol. 11533, pp. 182–199. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-22397-7_11CrossRef

18.

Coutaz, J., Crowley, J.L., Dobson, S., Garlan, D.: Context is key. ACM Commun. 48(3), 49–53 (2005). https://doi.org/10.1145/1047671.1047703CrossRef

19.

Dean, J., Ghemawat, S.: MapReduce: simplified data processing on large clusters. ACM Commun. 51(1), 107–113 (2008). https://doi.org/10.1145/1327452.1327492CrossRef

20.

Jelasity, M., Montresor, A., Babaoglu, O.: Gossip-based aggregation in large dynamic networks. ACM Trans. Comput. Syst. 23(3), 219–252 (2005). https://doi.org/10.1145/1082469.1082470CrossRef

21.

Lamport, L.: Time, clocks, and the ordering of events in a distributed system. ACM Commun. 21(7), 558–565 (1978). https://doi.org/10.1145/359545.359563CrossRefMATH

22.

Liu, Q., Pruteanu, A., Dulman, S.: Gradient-based distance estimation for spatial computers. Comput. J. 56(12), 1469–1499 (2013). https://doi.org/10.1093/comjnl/bxt124CrossRef

23.

Lluch-Lafuente, A., Loreti, M., Montanari, U.: Asynchronous distributed execution of fixpoint-based computational fields. Log. Methods Comput. Sci. 13(1) (2017). https://doi.org/10.23638/LMCS-13(1:13)2017

24.

Mamei, M., Zambonelli, F., Leonardi, L.: Co-fields: a physically inspired approach to motion coordination. IEEE Pervasive Comput. 3(2), 52–61 (2004). https://doi.org/10.1109/MPRV.2004.1316820CrossRef

25.

Moustafa, H., Zhang, Y.: Vehicular Networks: Techniques, Standards, and Applications, 1st edn. Auerbach Publications, Boston (2009)CrossRef

26.

Nath, S., Gibbons, P.B., Seshan, S., Anderson, Z.R.: Synopsis diffusion for robust aggregation in sensor networks. TOSN 4(2), 71–740 (2008). https://doi.org/10.1145/1340771.1340773CrossRef

27.

Pianini, D., Montagna, S., Viroli, M.: Chemical-oriented simulation of computational systems with Alchemist. J. Simul. 7(3), 202–215 (2013). https://doi.org/10.1057/jos.2012.27CrossRef

28.

Pianini, D., Viroli, M., Beal, J.: Protelis: practical aggregate programming. In: ACM Symposium on Applied Computing (SAC), pp. 1846–1853 (2015). https://doi.org/10.1145/2695664.2695913

29.

Talele, A.K., Patil, S.G., Chopade, N.B.: A survey on data routing and aggregation techniques for wireless sensor networks. In: International Conference on Pervasive Computing (ICPC), pp. 1–5. IEEE (2015)

30.

Viroli, M., Audrito, G., Beal, J., Damiani, F., Pianini, D.: Engineering resilient collective adaptive systems by self-stabilisation. ACM Trans. Model. Comput. Simul. 28(2), 16:1–16:28 (2018). https://doi.org/10.1145/3177774MathSciNetCrossRef

31.

Viroli, M., Beal, J., Damiani, F., Audrito, G., Casadei, R., Pianini, D.: From distributed coordination to field calculus and aggregate computing. J. Log. Algebraic Methods Program. 109, 100486 (2019). https://doi.org/10.1016/j.jlamp.2019.100486MathSciNetCrossRefMATH

32.

Viroli, M., Damiani, F.: A calculus of self-stabilising computational fields. In: Kühn, E., Pugliese, R. (eds.) COORDINATION 2014. LNCS, vol. 8459, pp. 163–178. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-43376-8_11CrossRef

33.

Viroli, M., Pianini, D., Ricci, A., Croatti, A.: Aggregate plans for multiagent systems. Int. J. Agent-Oriented Softw. Eng. 4(5), 336–365 (2017). https://doi.org/10.1504/IJAOSE.2017.087638CrossRef

34.

Zhang, Y., Lin, X., Yuan, Y., Kitsuregawa, M., Zhou, X., Yu, J.X.: Duplicate-insensitive order statistics computation over data streams. IEEE Trans. Knowl. Data Eng. 22(4), 493–507 (2010). https://doi.org/10.1109/TKDE.2009.68CrossRef

35.

Zhou, G., He, T., Krishnamurthy, S., Stankovic, J.A.: Impact of radio irregularity on wireless sensor networks. In: 2nd International Conference on Mobile Systems, Applications, and Services, MobiSys 2004, pp. 125–138. ACM, New York (2004). https://doi.org/10.1145/990064.990081

Titel: Resilient Distributed Collection Through Information Speed Thresholds
verfasst von: Giorgio Audrito
Sergio Bergamini
Ferruccio Damiani
Mirko Viroli
Verlag: Springer International Publishing
Buch: Coordination Models and Languages
Print ISBN: 978-3-030-50028-3

Electronic ISBN: 978-3-030-50029-0

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-50029-0_14

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"