Visibility, guarding and polygon decomposition are problems in the field of compu¬tational geometry which have roots in real world applications. These problems have been the focus of much research over a number of years. This thesis introduces a new problem in the field - The Axial line Placement Problem - which has some commonalities with these other problems. The problem arises from a consideration of the computational issues that result from attempting to automate the space syntax method. Space syntax is used for describing, quantifying and interpreting the spatial patterns in urban designs by analysing the relationship between the space through which one can move (roads, parks, etc.) and the buildings in the urban layout. In particular, this thesis considers the problem of the placing the axial lines, defining paths along which someone can move, to cross the shared boundaries between the convex polygons which represent the space through which someone can move in the town. A number of simplifications of the original problem are considered in this thesis. The first of these is the problem of placing the smallest number of orthogonal line segments (orthogonal axial lines) to cross the shared boundaries (adjacencies) in a collection of adjacent orthogonal rectangles. This problem is shown to be NP¬Complete by a transformation from the vertex cover problem for planar graphs. A heuristic algorithm which produces an approximation to the general solution is then presented. In addition, special cases of collections of orthogonal rectangles which allow polynomial time solutions are described and algorithms to solve some ofthese special cases are presented. The problem where the axial lines, that pass through the adjacencies between or¬thogonal rectangles, can have arbitrary orientation is then considered. This problem is also shown to be NP-Complete and once again heuristic approaches to solving the problem are considered. The problem of placing axial lines to cross the adjacencies between adjacent convex polygons is a more general case of the problem of placing axial lines of arbitrary orientation in orthogonal rectangles. The NP-Completeness proof can be extended to this problem as well. The final stage of the thesis considers real world urban layouts. Many urban layouts are regular grids of roads. Such layouts can be modelled as general urban grids and this thesis shows that it is possible to find the minimal axial line cover in general urban grids in polynomial time. Some urban layouts are less regular and the idea of a deformed urban grid is introduced to model some of these layouts. A heuristic algorithm that finds a partition of a deformed urban grid in polynomial time is presented and it is conjectured that the axial map of a deformed urban grid can be found in polynomial time. The problem is still open for more general urban layouts which cannot be modelled by deformed urban grids. The contribution of this thesis is that a number of new NP-Complete problems were identified and some new and interesting problems in the area of computational geometry have been introduced. / Thesis (DPhil (Computer Science))--University of Pretoria, 2005. / Computer Science / unrestricted

Thesis (MPhil)--Stellenbosch University, 2005. / ENGLISH ABSTRACT: Prior to the invention of Personal Computers the scope of research activities was limited by the pre-existing capabilities of problem solving mechanisms. However, with the advent of PCs and inter-networking thereof, the new tools (hardware and software) enabled the scientific community to tackle more complex research challenges and this led to a better understanding of our environment. The development of the Internet also enabled research communities to communicate and share information in real time. However, even the Internet has limitations of its own when it comes to the need of sharing not only information but also massive storage, processing power, huge databases and applications, expensive and delicate scientific instruments, knowledge and expertise. This led to the need for a networking system that includes these above-mentioned services, using the Internet infrastructure, semantic web technologies and pervasive computing devices, which is so called Grid Computing. This research study deals with a Generic Campus Grid Computing framework, which mobilizes the available idle/extra computing resources residing in the faculty-computing centres for use by the e-community on CPU-intensive or Data-intensive jobs. This unused computing capacity could be utilized for Grid computing services; hence, the already available resources could be more efficiently exploited. Besides, this could be a huge saving when compared to the cost of acquiring supercomputers by these institutions. Therefore, this research study intends to establish a simple and functional Generic Campus Grid Computing Framework at this stage, with the consent that subsequent research studies could deal with further assessment in a more detailed perspective and practical implementation thereof. / AFRIKAANSE OPSOMMING: Voor die uitvinding van die Persoonlike Rekenaar is die omvang van navorsingsaktiwiteite beperk deur die voorafbestaande vermoëns van probleemoplossingsmeganismes. Met die verskyning van PR's en die daaropvolgende internetwerking daarvan, het die nuwe gereedskap (hardeware en sagteware) die wetenskaplike gemeenskap in staat gestel om meer komplekse navorsingsuitdagings aan te pak. Dit het gelei tot groter begrip van ons omgewing. Die onwikkeling van die Internet het navorsingsgemeenskappe ook in staat gestel om in reële tyd te kommunikeer en inligting te deel. Nietemin, selfs die Internet het gebreke wanneer dit kom by die behoefte om nie slegs inligting te deel nie, maar ook massiewe stoorruimte, verwerkingskrag, baie groot databasisse en toepassings, duur en delikate wetenskaplike toerusting, kennis en kundigheid. Dit het gelei tot die behoefte aan 'n netwerksisteem wat bogenoemde dienste insluit, deur gebruik te maak van Internet-infrastruktuur, semantiese web tegnologieë, en alomteenwoordige rekenaartoestelle. Hierdie sisteem staan bekend as "Grid Computing" of te wel Rooster Komputasie. Hierdie navorsingstudie handel oor 'n Generiese Kampus Rooster Komputasie Raamwerk wat die ongebruikte, ekstra komputasiebronne, wat beskikbaar is in fakulteite se rekenaargebruikersareas, mobiliseer vir gebruik deur die e-gemeenskap op SVE-intensiewe of Dataintensiewe toepassings. Hierdie ongebruikte komputasie kapasiteit kan aangewend word vir Rooster komputasie dienste; gevolglik kan die beskikbare bronne dan meer effektief benut word. Verder kan dit lei tot groot besparings wanneer dit vergelyk word met die koste om superrekenaars aan te koop deur die betrokke instansies. Dus, op hierdie stadium stel hierdie navorsingstudie dit ten doel om 'n eenvoudige en funksionele Generiese Kampus Rooster Komputasie Raamwerk te skep met dien verstande dat daaropvolgende studies sou kon fokus op verdere assessering met 'n meer gedetaileerde perspektief en met praktiese implementasie.

The rise of business-oriented and commercial applications for Grid computing environments has recently gathered pace. Grid computing traditionally has been linked with scientific environments, where heterogeneous resources provided by Grid systems and infrastructures were employed for carrying out computationally-intensive and data-intensive scientific experiments or applications that may have not been possible before. The natural progression is that business-oriented applications will look to build on this success and utilise the large number of heterogeneous Grid resources including computational resources such as CPUs and memory and storage resources such as disk space, potentially available. The success of introducing these applications into the mainstream is directly related to whether service providers can deliver a level of Quality of Service (QoS) to a consumer and the ability of the consumer to request high-level QoS such as the numbers of CPUs required or the RAM required. QoS refers to the guidelines and requirements requested by a user/consumer from the service providers and resources. The communication and agreement establishment processes between user and provider must be defined clearly to accommodate a new type of user where knowledge of the underlying infrastructure cannot be assumed. QoS parameters have generally been defined at the Grid resource level using low level definitions. This tailors to specific applications and models related to scientific domains where brokering, scheduling and QoS delivery is designed for specific applications within specific domains. This thesis presents a flexible model for high-level QoS requests. Business Grid Quality of Service (BGQoS) is introduced for business-oriented and commercial Grid applications which may wish to make use of the resources made available by Grid system environments. BGQoS allows GRCs (Grid Resource Consumers) to specify varying types of high-level QoS requirements which are delivered via querying up-to-date resource information, matchmaking and monitoring operations. Moreover, we present dynamically calculated metrics for measuring QoS such as reliability, increasing the accuracy of meeting the GRC’s requirements. On the other hand GRPs (Grid Resource Provider) are also capable of advertising their resources, their capabilities, their usage policies and availability both locally and globally. This leads to a flexible model that could be carried across domains without altering the core operations and which could easily be expanded in order to accommodate different types of GRC, resources and applications.

published_or_final_version / abstract / Computer Science and Information Systems / Master / Master of Philosophy

M.Sc. / Grid computing is a technology concerned with harvesting idle resources of geographically distributed and interconnected computers. It solves problems regarded as too complex or large to be solved by a single computer. Furthermore, economic grid computing is becoming the most dominant form of grid computing. It enables some form of payment to occur between resource producers and resource consumers in grid computing. Mobile devices and mobile telecommunication services, a relatively new field of technology, are rapidly increasing in popularity, size, strength and application. At the end of 2006, there were approximately 2.7 billion global active mobile users utilising mobile devices and mobile telecommunication services [Aho07]. At the end of 2007 this number had grown to 3.3 billion mobile users, more than half a billion additional mobile users in a period of one year [McN07]. With such large numbers, grid computing can benefit from the clustering of mobile devices forming a mobile grid computing model. However, there are many inherent disadvantages concerning mobile devices, such as low processing capabilities, unpredictable network connections and battery utilisation. Such hurdles must be addressed and solved if a mobile computing infrastructure or architecture is ever to be considered. This dissertation proposes the implementation of an economic mobile computing solution: Mobile Agents for Global Mobile Device Grid Infrastructure Enterprises, or MAGGIE. MAGGIE is concerned with harvesting idle mobile device resources by implementing the supply and demand economic model, aiming to create a healthy competitive economic market environment. MAGGIE implements agent and mobile agent technology to compensate for the hurdles introduced by mobile devices and mobile device software development platforms. It is targeted at both Sun Microsystems’s J2ME MIDP 2.0 and Microsoft’s .NET Compact Framework, enabling lower-end and higher-end mobile devices to contribute mobile computing services and resources for utilisation by other mobile device users. The primary goal of MAGGIE is to produce an architecture as generic as possible regarding the development and implementation of MAGGIE services. MAGGIE allows third-party application developers to seamlessly implement an array of MAGGIE services, without indepth prior knowledge of the architecture and technical aspects of MAGGIE. Finally, MAGGIE’s capabilities are demonstrated by implementing a distributed mobile chess service known as the MAGGIE Chess Service. The MAGGIE Chess Service enables a collection of distributed mobile devices in determining the best move originating from a chessboard position.

Cloud Computing is a new computing model consists of a large pool of hardware and software resources on remote datacenters that are accessed through the Internet. Cloud Computing faces significant obstacles to its acceptance, such as security, virtualization, and lack of standardization. For Cloud standards, there is a long debate about their role, and more demands for Cloud standards are put on the table. The Cloud standardization landscape is so ambiguous. To model and analyze security standards for Cloud Computing and web services, we have surveyed Cloud standards focusing more on the standards for security, and we classified them by groups of interests. Cloud Computing leverages a number of technologies such as: Web 2.0, virtualization, and Service Oriented Architecture (SOA). SOA uses web services to facilitate the creation of SOA systems by adopting different technologies despite their differences in formats and protocols. Several committees such as W3C and OASIS are developing standards for web services; their standards are rather complex and verbose. We have expressed web services security standards as patterns to make it easy for designers and users to understand their key points. We have written two patterns for two web services standards; WS-Secure Conversation, and WS-Federation. This completed an earlier work we have done on web services standards. We showed relationships between web services security standards and used them to solve major Cloud security issues, such as, authorization and access control, trust, and identity management. Close to web services, we investigated Business Process Execution Language (BPEL), and we addressed security considerations in BPEL and how to enforce them. To see how Cloud vendors look at web services standards, we took Amazon Web Services (AWS) as a case-study. By reviewing AWS documentations, web services security standards are barely mentioned. We highlighted some areas where web services security standards could solve some AWS limitations, and improve AWS security process. Finally, we studied the security guidance of two major Cloud-developing organizations, CSA and NIST. Both missed the quality of attributes offered by web services security standards. We expanded their work and added benefits of adopting web services security standards in securing the Cloud. / Includes bibliography. / Dissertation (Ph.D.)--Florida Atlantic University, 2013.

Esta dissertação tem por objetivo apresentar a proposta de uma política de escalonamento para grids computacionais. Essa política, intitulada Dynamic Max-Min2x, é orientada ao escalonamento de aplicações cujas tarefas não realizam comunicação entre si e visa a redução do tempo de resposta dessas aplicações através da utilização de atribuição dinâmica de tarefas e replicação das mesmas. Experimentos, feitos através de simulação, mostram que o tempo médio de resposta de aplicações utilizando-se a Dynamic Max-Min2x é inferior ao de outras políticas da literatura. Análises dos resultados desses experimentos apontam que esse tempo tende a ser mais atrativo principalmente quando as tarefas necessitam de muito processamento e quando há grande variação de carga no sistema, caracteristicas comuns em grids computacionais. Além disso, esta dissertação apresenta a implementação de um framework utilizando-se o Globus Toolkit, onde é possível a inserção de políticas de escalonamento para a submissão inteligente de tarefas em um grid computacional. / This Master thesis proposes a new grid scheduling policy called Dynamic Max-Min2x. This policy focuses on applications in which tasks do not communicate among themsenves and targets a response time reduction of these applications through the use of dynamic task distribution and replication techniques. Experiments, done using simulations, have shown that the response time related to Dynamic Max-Min2x is smaller than others policies found in literature. Analysis of the results have demonstrated that this time tends to become more attractive when tasks do not need much processing power and when there is a great load variation in the system, characteristics frequently found in grids. Furthermore, this thesis presents the implementation of a framework using Globus Toolkit, which makes possible the new scheduling policies insertion to provide an intelligent submission tasks in a computational grid system.

Silicon carbide as a representative wide band-gap semiconductor has recently received wide attention due to its excellent physical, thermal and especially electrical properties. It becomes a promising material for electronic and optoelectronic device under high-temperature, high-power and high-frequency and intense radiation conditions. During the Silicon Carbide crystal grown by the physical vapor transport process, the temperature gradients induce thermal stresses which is a major cause of the dislocations multiplication. Although large dimension crystal with low dislocation density is required for satisfying the fast development of electronic and optoelectronic device, high dislocation densities always appear in large dimension crystal. Therefore, reducing dislocation density is one of the primary tasks of process optimization. This dissertation aims at developing a transient finite element model based on the Alexander-Haasen model for computing the dislocation densities in a crystal during its growing process. Different key growth parameters such as temperature gradient, crystal size will be used to investigate their influence on dislocation multiplications. The acceptable and optimal crystal diameter and temperature gradient to produce the lowest dislocation density in SiC crystal can be obtained through a thorough numerical investigation using this developed finite element model. The results reveal that the dislocation density multiplication in SiC crystal are easily affected by the crystal diameter and the temperature gradient. Generally, during the iterative calculation for SiC growth, the dislocation density multiples very rapidly in the early growth phase and then turns to a relatively slow multiplication or no multiplication at all. The results also show that larger size and higher temperature gradient causes the dislocation density enters rapid multiplication phase sooner and the final dislocation density in the crystal is higher. / Includes bibliography. / Dissertation (Ph.D.)--Florida Atlantic University, 2015. / FAU Electronic Theses and Dissertations Collection

Made available in DSpace on 2015-03-05T13:56:59Z (GMT). No. of bitstreams: 0 Previous issue date: 23 / Hewlett-Packard Brasil Ltda / Contabilizar e caracterizar o uso de grades computacionais constitui uma tarefa de gerenciamento indispensável, especialmente quando essas grades são usadas em larga escala, envolvendo várias instituições e participantes. As soluções de gerência de grades existentes atualmente são limitadas: (a) por se destinarem a monitorar apenas o estado dos recursos que compõem o ambiente (como consumo de memória e espaço de armazenamento em disco),omitindo dados estatísticos e históricos sobre a execução de aplicações; (b) por não oferecem suporte à coleta, ao processamento e à consolidação de informações que são geradas por diferentes tecnologias de grade; e (c) por não oferecem um esquema seletivo para a divulgação das informações gerenciais que são obtidas. Para suprir as lacunas recém mencionadas, esta dissertação propõe uma abordagem baseada em políticas para contabilização e caracterização de uso de grades computacionais compostas por sistemas heterogêneos. A abordagem proposta se materializa através de uma arquit / Accounting and characterizing the use of computational grids constitutes a management task of paramount importance, especially when they are used in large scale, involving many institutions and participants. Current grid computing management solutions are limited since they: (a) solely monitor the status of environment resources (like CPU and disk space consumption), omitting statistical and historical data about the execution of applications; (b) do not offer support for gathering, processing and consolidation of information that is generated by heterogeneous grid technologies; and (c) do not allow the specification of policies to distribute the collected information. To fullfil this gap, this work proposes an approach based on polices to account and characterize usage of grid computing infrastructures, even when such grids are formed by heterogeneous middleware. The approach is materialized through an architecture based on the Web Services Distributed Management standard. This work presents the architec

Os Sistemas de Grades Computacionais são intrinsecamente mais vulneráveis às ameaças de segurança que os Sistemas tradicionais, uma vez que abrangem um grande número de usuários e os recursos e as aplicações são geridas por diferentes domínios administrativos. A autenticação e a autorização são fatores imperativos para os Sistemas de Grade Computacional. Da mesma forma, a escalabilidade e a distribuição de dados vêm também sendo objeto de estudo de vários pesquisadores da área. Os serviços providos pelas Grades Computacionais devem evitar implementações centralizadas pela dificuldade do gerenciamento global. Outro importante requisito das Grades Computacionais é prover mecanismos para a delegação de direitos de acesso aos recursos. O proprietário do recurso deve ser capaz de delegar permissões para outro usuário, talvez por um tempo limitado, com base na confiança que possui neste. No entanto, a delegação deve ser usada com cuidado, pois uma longa cadeia de delegações poderia conduzir a uma utilização abusiva dos recursos pelos usuários maliciosos. Para tratar os principais requisitos de segurança das Grades Computacionais, desenvolvemos uma Arquitetura de Segurança denominada Xenia. Esta arquitetura é baseada em SPKI/SDSI, um modelo de segurança flexível, extensível e descentralizado que fornece autenticação, confidencialidade e controle de acesso. Propusemos uma extensão ao modelo SPKI/SDSI baseada em lógica subjetiva para representar relações de confiança entre indivíduos. / Grid Computing Systems are inherently more vulnerable to security threats than traditional systems, since they potentially encompass a large number of users, resources, and applications managed by different administrative domains. Authentication and authorization are imperative for grid systems. Since scalability and distribution are major concerns on grid environments, those services implementations should avoid centralized solutions. Another relevant requirement to consider is the provision of mechanisms for delegating access rights, since they minimize the overhead of grid administrators on providing access rights to grid resources. The owner of an access right should be able to delegate permissions to another user, maybe for a limited time, based on his trust on that user. However, delegation must be used with care. A long chain of delegations could lead to improper use of resources by malicious users. Confidentiality and integrity are also important security requirements for many grid applications. To address these problems, we designed a Security Architecture for Grid Systems named Xenia. This architecture is based on SPKI/SDSI, a flexible and extensible decentralized security model that provides authentication, confidentiality, and access control. We proposed an extension to the SPKI/SDSI model to represent trust relations between subjects based on subjective logic.