Redundant iterable semantic paths (RISP) for the smart grid

Abstract

Highly-reliable and scalable distributed algorithms are needed to meet the scalability, flexibility and reliability requirements of the power systems of the future. Iterative numerical methods will continue to be essential tools in such algorithms. The performance of existing versions of such algorithms degrades quickly in the presence of faults. In general, deterministic distributed algorithms which are guaranteed to always produce the required output in a timely manner, whenever theoretically possible at all, have too much overhead to be feasible for large systems. Moreover, even when they do, they provide output only for the fault-free portion of the system.

This thesis presents research undergone in techniques for improving fault-tolerance for distributed iterative numerical algorithms. In particular, a pattern of data dependency in such algorithms is exploited with a technique called redundant iterable semantic paths (RISP), in order to tolerate agent or communication failures while maintaining scalability. In RISP, overlapping input clusters are created at each agent and the communication protocol is adapted in order to provide redundant solution paths. Fault-tolerance comes from data redundancy, instead of equipment redundancy, which might help keeping additional sources of failure down. The size of the input clusters is parameterized so that the same algorithm can behave somewhere between the fully-distributed implementation, with no clustering, and the n-modular redundant version, when clustering size is greater than or equal to system height.

RISP was integrated into a distributed iterative power flow solver for radial power distribution systems based on a Multi-Agent System (MAS). Results for our solution, as applied to the 13-node IEEE test feeder at various clustering levels, show significant improvement in agent and communication fault-tolerance, as compared to the non-clustering solution. This scheme can be used by several known classes of distributed algorithms with little modification to achieve similar results.

Space, computational and message complexity per agent for RISP-DBFS is impacted by a factor of O(ca^c) for full trees of arity a, asymptotically on clustering size c. Even though this factor does not depend on the size of the MAS or the number of buses in the system, it might still be prohibitively expensive for large clustering sizes. However, for sparse systems like power distribution feeders, the impact might not grow as quickly.

This thesis presents and tests a technique called global input prefetching to take away exclusive ownership of local knowledge from corresponding local PEs in distributed consensus algorithms. This eliminates single points of failure, enabling distributed algorithms to provide precise global results that include input originally mapped to faulty PEs, not just the fault-free subset. The technique is integrated to RISP and tested in this work.

A recurring issue when studying agent-based algorithms and strategies for Power Microgrid Systems is having to construct an interface between the agent domain and the electrical model domain being simulated. Many different tools exist for such simulations, each with its own special external interface. Although many interfacing efforts have been published before, many of them support only special cases, while others are too complex and require a long learning curve to be used for even simple scenarios. This work presents a simple programming application interface (API) that aims to provide programming access to the electrical system model for any real-time simulation tool, from any agent-based platform, or programming language. We propose four basic operations for the API: read, write, call, and subscribe/call-back. We tested these by supporting two examples. In one of the examples, we present a creative way to have the model access libraries that are not available in the simulated environment.

Se necesitan algoritmos distribuidos altamente confiables y escalables para cumplir con los requisitos de escalabilidad, flexibilidad y confiabilidad de los sistemas de energía del futuro. Los métodos numéricos iterativos continuaran siendo herramientas esenciales en tales algoritmos. El rendimiento de las versiones existentes de dichos algoritmos se degrada rápidamente en presencia de fallas. En general, los algoritmos distribuidos determinísticos que garantizan la salida requerida de manera oportuna, siempre que sea teóricamente posible, tienen demasiada sobrecarga para ser factibles para sistemas grandes. Además, incluso cuando lo son, proporcionan salida solo para la parte libre de fallas del sistema. Esta tesis presenta la investigación realizada en técnicas para mejorar la tolerancia a fallas para algoritmos numéricos iterativos distribuidos. En particular, un patrón de dependencia de datos en tales algoritmos se explota con una técnica llamada rutas semánticas iterables redundantes (RISP, en inglés), con el fin de tolerar fallas de comunicación o de agentes, mientras se preserva la escalabilidad de la solución. En RISP, se crean grupos de entrada superpuestos en cada agente y el protocolo de comunicación se adapta para proporcionar rutas alternas hacia una solución correcta. La tolerancia a fallas proviene de la redundancia de datos, en lugar de la redundancia del equipo, lo que podría ayudar a evitar fuentes adicionales de fallas. El tamaño de los clústeres de entrada se parametriza para que el mismo algoritmo pueda comportarse en algún lugar entre la implementación completamente distribuida, sin clústeres, y la versión redundante n-modular, cuando el tamaño del clúster es mayor o igual que la altura del sistema. RISP se aplico a un solucionador de flujo de energía iterativo distribuido (DBFS) para sistemas radial de distribución de potencia basados en un sistema de agentes múltiples (MAS, en inglés). Los resultados de nuestra solución, aplicados al alimentador de prueba IEEE de 13 nodos en varios tamaños de clústeres, muestran una mejora significativa en la tolerancia a fallas de comunicación y de agentes, en comparación ´on con la solución original. Este esquema puede ser utilizado por varias clases conocidas de algoritmos distribuidos con pocas modificaciones para lograr resultados similares. La complejidad de espacio, computación y mensajería por agente para RISPDBFS aumenta con un factor de O(cac), para ´arboles completos de aridad a y de forma asintótica con el tamaño de los clústeres. Aunque este factor no depende del tamaño del MAS o de la cantidad de buses en el sistema, puede resultar prohibitivamente