Characterizing Data Dependence Constraints for Dynamic Reliability Using N-Queens Attack Domains

详细信息    查看全文

• 关键词：Big data ; Reliability ; Storage ; n ; queens ; Intelligent systems
• 刊名：Lecture Notes in Computer Science
• 出版年：2015
• 出版时间：2015
• 年：2015
• 卷：9259
• 期：1
• 页码：211-227
• 全文大小：660 KB
• 参考文献：1.Akinyele, J.A., Green, M., Hohenberger, S.: Using smt solvers to automate design tasks for encryption and signature schemes. In: Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security, pp. 399–410. ACM (2013)
  2.Anvin, H.P.: The mathematics of raid-6 (2007)
  3.Bayram, U., Rozier, E.W., Zhou, P., Divine, D.: Improving reliability with dynamic syndrome allocation in intelligent software defined data centers. In: IEEE/IFIP International Conference on Dependable Systems & Networks, DSN 2015. IEEE (2015)
  4.Bell, J., Stevens, B.: A survey of known results and research areas for n-queens. Discrete Math. 309(1), 1–31 (2009)CrossRef MathSciNet MATH
  5.Corbett, P., English, B., Goel, A., Grcanac, T., Kleiman, S., Leong, J., Sankar, S.: Row-diagonal parity for double disk failure correction. In: Proceedings of the 3rd USENIX Conference on File and Storage Technologies, pp. 1–14 (2004)
  6. de Moura, L., Bjørner, N.S.: Z3: an efficient SMT solver. In: Ramakrishnan, C.R., Rehof, J. (eds.) TACAS 2008. LNCS, vol. 4963, pp. 337–340. Springer, Heidelberg (2008) CrossRef
  7.Derisavi, S., Kemper, P., Sanders, W.H.: Symbolic state-space exploration and numerical analysis of state-sharing composed models. Linear Algebra Appl. 386, 137–166 (2004)CrossRef MathSciNet MATH
  8.Duffy, D., Schnase, J.: Meeting the big data challenges of climate science through cloud-enabled climate analytics-as-a-service. In: Proceedings of the 30th International Conference on Massive Storage Systems and Technology. IEEE Computer Society (2014)
  9.Eickenscheidt, B.: Das \(n\) -damen-problem auf dem zylinderbrett. Feenschach 50, 382–385 (1980)
  10.Gu, J., et al.: Efficient local search with conflict minimization: a case study of the n-queens problem. IEEE Trans. Knowl. Data Eng. 6(5), 661–668 (1994)CrossRef
  11.Hashem, I.A.T., Yaqoob, I., Anuar, N.B., Mokhtar, S., Gani, A.B., Khan, S.U.: The rise of big data on cloud computing: review and open research issues. Inf. Syst. 47, 98–115 (2015)CrossRef
  12.Klarner, D.A.: Queen squares. J. Recreational Math 12(3), 177–178 (1979)MathSciNet
  13. Klebanov, V., et al.: The 1st verified software competition: experience report. In: Butler, M., Schulte, W. (eds.) FM 2011. LNCS, vol. 6664, pp. 154–168. Springer, Heidelberg (2011) CrossRef
  14. Köksal, A.S., Kuncak, V., Suter, P.: Scala to the power of Z3: Integrating SMT and programming. In: Bjørner, N., Sofronie-Stokkermans, V. (eds.) CADE 2011. LNCS, vol. 6803, pp. 400–406. Springer, Heidelberg (2011) CrossRef
  15.Leventhal, A.: Triple-parity raid and beyond. Queue 7(11), 30 (2009)
  16.McCarty, C.P.: Queen squares. Am. Math. Monthly 85, 578–580 (1978)CrossRef MathSciNet MATH
  17.Nadel, B.A.: Representation selection for constraint satisfaction: a case study using n-queens. IEEE Intell. Syst. 5(3), 16–23 (1990)MathSciNet
  18.Pâris, J.F., Amer, A., Schwarz, T.J.: Low-redundancy two-dimensional raid arrays. In: 2012 International Conference on Computing, Networking and Communications (ICNC), pp. 507–511. IEEE (2012)
  19.Pâris, J.F., Long, D.D., Litwin, W.: Three-dimensional redundancy codes for archival storage. In: 2013 IEEE 21st International Symposium on Modeling, Analysis & Simulation of Computer and Telecommunication Systems (MASCOTS), pp. 328–332. IEEE (2013)
  20.Patterson, D.A., Gibson, G., Katz, R.H.: A case for redundant arrays of inexpensive disks (RAID), vol. 17. ACM (1988)
  21. Pless, V.: Introduction to the Theory of Error-Correcting Codes, vol. 48. Wiley, New York (2011)
  22.Rozier, E.W., Sanders, W.H., Zhou, P., Mandagere, N., Uttamchandani, S.M., Yakushev, M.L.: Modeling the fault tolerance consequences of deduplication. In: 2011 30th IEEE Symposium on Reliable Distributed Systems (SRDS), pp. 75–84. IEEE (2011)
  23.Rozier, E.W., Zhou, P., Divine, D.: Building intelligence for software defined data centers: modeling usage patterns. In: Proceedings of the 6th International Systems and Storage Conference, p. 20. ACM (2013)
  24.Rozier, E.W.D., Sanders, W.H.: A framework for efficient evaluation of the fault tolerance of deduplicated storage systems. In: 2012 42nd Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), pp. 1–12. IEEE (2012)
  25.Salido, M.A., Barber, F.: How to classify hard and soft constraints in non-binary constraint satisfaction problems. In: Coenen, F., Preece, A., Macintosh, A. (eds.) AResearch and Development in Intelligent Systems XX, pp. 213–226. Springer, New York (2004)CrossRef
  26.Schnase, J.L., Duffy, D.Q., Tamkin, G.S., Nadeau, D., Thompson, J.H., Grieg, C.M., McInerney, M.A., Webster, W.P.: Merra analytic services: Meeting the big data challenges of climate science through cloud-enabled climate analytics-as-a-service. Computers, Environment and Urban Systems (2014)
  27.Schwarz, S., Long, D.D., Paris, J.F.: Reliability of disk arrays with double parity. In: 2013 IEEE 19th Pacific Rim International Symposium on Dependable Computing (PRDC), pp. 108–117. IEEE (2013)
  28.Turner, V., Gantz, J.F., Reinsel, D., Minton, S.: The digital universe of opportunities: Rich data and the increasing value of the internet of things. International Data Corporation, White Paper, IDC\(\_\) 1672 (2014)
  29.Weisstein, E.W.: Rooks problem (2002)
  
• 作者单位：Ulya Bayram (15)
  Kristin Yvonne Rozier (15)
  Eric W. D. Rozier (15)
  
  15. University of Cincinnati, Cincinnati, OH, USA
  
• 丛书名：Quantitative Evaluation of Systems
• ISBN：978-3-319-22264-6
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

As data centers attempt to cope with the exponential growth of data, new techniques for intelligent, software-defined data centers (SDDC) are being developed to confront the scale and pace of changing resources and requirements. For cost-constrained environments, like those increasingly present in scientific research labs, SDDCs also present the possibility to provide better reliability and performability with no additional hardware through the use of dynamic syndrome allocation. To do so the middleware layers of SDDCs must be able to calculate and account for complex dependence relationships to determine an optimal data layout. This challenge is exacerbated by the growth of constraints on the dependence problem when available resources are both large (due to a higher number of syndromes that can be stored) and small (due to the lack of available space for syndrome allocation). We present a quantitative method for characterizing these challenges using an analysis of attack domains for high-dimension variants of the n-queens problem that enables performable solutions via the SMT solver Z3. We demonstrate correctness of our technique, and provide experimental evidence of its efficacy; our implementation is publicly available.