×

zbMATH — the first resource for mathematics

Quantified abstract configurations of distributed systems. (English) Zbl 1319.68023
Summary: When reasoning about distributed systems, it is essential to have information about the different kinds of nodes that compose the system, how many instances of each kind exist, and how nodes communicate with other nodes. In this paper we present a static-analysis-based approach which is able to provide information about the questions above. In order to cope with an unbounded number of nodes and an unbounded number of calls among them, the analysis performs an abstraction of the system producing a graph whose nodes may represent (infinitely) many concrete nodes and arcs represent any number of (infinitely) many calls among nodes. The crux of our approach is that the abstraction is enriched with upper bounds inferred by resource analysis that limit the number of concrete instances that the nodes and arcs represent and their resource consumption. The information available in our quantified abstract configurations allows us to define performance indicators which measure the quality of the system. In particular, we present several indicators that assess the level of distribution in the system, the amount of communication among distributed nodes that it requires, and how balanced the load of the distributed nodes that compose the system is. Our performance indicators are given as functions on the input data sizes, and they can be used to automate the comparison of different distributed settings and guide towards finding the optimal configuration.

MSC:
68M14 Distributed systems
Software:
ABS; Erlang; COSTABS; JCobox
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Albert E, Arenas P, Genaim S, Puebla G, Zanardini D (2007) Cost analysis of Java bytecode. In: De Nicola R (ed) Proceedings of the 16th European symposium on programming (ESOP’07). Lecture notes in computer science, vol 4421. Springer, New York, pp 157-172 · Zbl 1236.68042
[2] Albert E, Arenas P, Genaim S, Herraiz I, Puebla G (2010) Comparing cost functions in resource analysis. In: 1st International workshop on foundational and practical aspects of resource analysis (FOPARA’09). Lecture notes in computer science, vol 6234. Springer, New York, pp 1-17 · Zbl 1305.68051
[3] Albert E, Arenas P, Genaim S, Gómez-Zamalloa M, Puebla G (2011) Cost analysis of concurrent oo programs. In: Proceedings of APLAS’11. LNCS, vol 7078. Springer, New York, pp 238-254
[4] Albert E, Arenas P, Genaim S, Gómez-Zamalloa M, Puebla G (2012) COSTABS: a cost and termination analyzer for ABS. In: Proceedings of PEPM’12. ACM Press, New York, pp 151-154
[5] Albert, E; Arenas, P; Genaim, S; Puebla, G; Zanardini, D, Cost analysis of object-oriented bytecode programs, Theor Comput Sci (Spec Issue Quant Asp Program Lang), 413, 142-159, (2012) · Zbl 1236.68042
[6] Albert E, Arenas P, Genaim S, Puebla G (2008) Automatic inference of upper bounds for recurrence relations in cost analysis. In: Proceedings of SAS’08. Lecture notes in computer science, vol 5079. Springer, New York, pp 221-237 · Zbl 1149.68345
[7] Albert, E; Arenas, P; Genaim, S; Puebla, G, Closed-form upper bounds in static cost analysis, J Autom Reason, 46, 161-203, (2011) · Zbl 1213.68200
[8] Albert E, Correas J, Puebla G, Román-Díez G (2013) Quantified abstractions of distributed systems. In: Proceedings of iFM’13. LNCS, vol 7940. Springer, New York, pp 285-300
[9] Albert E, Flores-Montoya A, Genaim S, Martin-Martin E (2013) Termination and cost analysis of loops with concurrent interleavings. In: ATVA’13, LNCS, vol 8172. Springer, New York, pp 349-364 · Zbl 1410.68080
[10] America, P, Issues in the design of a parallel object-oriented language, Form Asp Comput, 1, 366-411, (1989) · Zbl 0694.68012
[11] Albert E, Arenas P, Correas J, Gómez-Zamalloa M, Genaim S, Puebla G, Román-Díez G (2012) Object-sensitive cost analysis for concurrent objects. http://costa.ls.fi.upm.es/papers/costa/AlbertACGGPRtr.pdf. Accessed 15 May 2014
[12] Al-Saleh, MF; Yousif, AE, Properties of the standard deviation that are rarely mentioned in classrooms, Austrian J Stat, 38, 193-202, (2009)
[13] Armstrong J, Virding R, Wistrom C, Williams M (1996) Concurrent programming in Erlang. Prentice Hall, USA · Zbl 0829.68014
[14] Bruynooghe, M; Codish, M; Gallagher, J; Genaim, S; Vanhoof, W, Termination analysis of logic programs through combination of type-based norms, TOPLAS, 29, 10, (2007)
[15] Bjørk, J; Boer, FS; Broch Johnsen, E; Schlatte, R; Tapia Tarifa, SL, User-defined schedulers for real-time concurrent objects, ISSE, 9, 29-43, (2013)
[16] Buyya, R; Yeo, CS; Venugopal, S; Broberg, J; Brandic, I, Cloud computing and emerging IT platforms: vision, hype, and reality for delivering computing as the 5th utility, Future Gener Comput Syst, 25, 599-616, (2009)
[17] Caromel, D, Towards a method of object-oriented concurrent programming, Commun ACM, 36, 90-102, (1993)
[18] Boer, FS; Grabe, I; Steffen, M, Termination detection for active objects, J Log Algebr Program, 81, 541-557, (2012) · Zbl 1243.68221
[19] Di Pierro, A; Hankin, C; Wiklicky, H, Quantitative static analysis of distributed systems, J Funct Program, 1, 37-81, (2005) · Zbl 1104.68004
[20] Feret, J, Occurrence counting analysis for the pi-calculus, Electron Notes Theor Comput Sci, 39, 1-18, (2001) · Zbl 0970.68113
[21] Flores-Montoya A, Albert E, Genaim S (2013) May-happen-in-parallel based deadlock analysis for concurrent objects. In: FORTE’13. LNCS. Springer, New York, pp 273-288
[22] Gori R, Levi F (2005) A new occurrence counting analysis for bioambients. In: APLAS. LNCS, vol 3780. Springer, New York, pp 381-400 · Zbl 1159.68368
[23] Haller, P; Odersky, M, Scala actors: unifying thread-based and event-based programming, Theor Comput Sci, 410, 202-220, (2009) · Zbl 1162.68396
[24] Johnsen EB, Hähnle R, Schäfer J, Schlatte R, Steffen M (2012) ABS: a core language for abstract behavioral specification. In: Proceedings of FMCO’10 (revised papers). LNCS, vol 6957. Springer, New York, pp 142-164
[25] Milanova, A; Rountev, A; Ryder, BG, Parameterized object sensitivity for points-to analysis for Java, ACM Trans Softw Eng Methodol, 14, 1-41, (2005)
[26] Smaragdakis Y, Bravenboer M, Lhoták O (2011) Pick your contexts well: understanding object-sensitivity. In: Proceedings of POPL’11. ACM, New York, pp 17-30 · Zbl 1284.68204
[27] Schäfer J, Poetzsch-Heffter A (2010) JCobox: generalizing active objects to concurrent components. In: Proceedings of ECOOP’10. LNCS. Springer, New York, pp 275-299
[28] Yonezawa A, Briot JP, Shibayama E (1986) Object-oriented concurrent programming ABCL/1. In: Proceedings of OOPLSA’86. ACM, New York, pp 258-268 · Zbl 0970.68113
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.