Página 1 dos resultados de 102 itens digitais encontrados em 0.005 segundos

Algoritmos criptográficos para redes de sensores.; Cryptographic algorithms for sensor networks.

Simplicio Junior, Marcos Antonio
Fonte: Biblioteca Digitais de Teses e Dissertações da USP Publicador: Biblioteca Digitais de Teses e Dissertações da USP
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 03/04/2008 PT
Relevância na Pesquisa
36.14%
É crescente a necessidade de prover segurança às informações trocadas nos mais diversos tipos de redes. No entanto, redes amplamente dependentes de dispositivos com recursos limitados (como sensores, tokens e smart cards) apresentam um desafio importante: a reduzida disponibilidade de memória, capacidade de processamento e (principalmente) energia dos mesmos dificulta a utilização de alguns dos principais algoritmos criptográficos considerados seguros atualmente. É neste contexto que se insere o presente documento, que não apenas apresenta uma pesquisa envolvendo projeto e análise de algoritmos criptográficos, mas também descreve um novo algoritmo simétrico denominado CURUPIRA. Esta cifra de bloco baseia-se na metodologia conhecida como Estratégia de Trilha Larga e foi projetada especialmente para ambientes onde existe escassez de recursos. O CURUPIRA possui estrutura involutiva, o que significa que os processos de encriptação e decriptação diferem apenas na seqüência da geração de chaves, dispensando a necessidade de algoritmos distintos para cada uma destas operações. Além disto, são propostas duas formas diferentes para seu algoritmo de geração de chaves, cada qual mais focada em segurança ou em desempenho. Entretanto...

Algoritmos de autenticação de mensagens para redes de sensores.; Message authentication algorithms for wireless sensor networks.

Simplício Junior, Marcos Antonio
Fonte: Biblioteca Digitais de Teses e Dissertações da USP Publicador: Biblioteca Digitais de Teses e Dissertações da USP
Tipo: Tese de Doutorado Formato: application/pdf
Publicado em 12/03/2010 PT
Relevância na Pesquisa
36.19%
Prover segurança às informações trafegadas nos mais diversos tipos de redes é algo essencial. Entretanto, redes altamente dependentes de dispositivos com recursos limitados (como sensores, tokens e smart cards) apresentam um desafio importante: a reduzida disponibilidade de memória e energia destes dispositivos, bem como sua baixa capacidade de processamento, dificultam a utilização de diversos algoritmos criptográficos considerados seguros atualmente. Este é o caso não apenas de cifras simétricas, que proveem confidencialidade aos dados, mas também de MACs (Message Authentication Code, ou Código de Autenticação de Mensagem), que garantem sua integridade e autenticidade. De fato, algumas propostas recentes de cifras de bloco dedicadas a plataformas limitadas (e.g., o Curupira-2) proveem segurança e desempenho em um nível mais adequado a este tipo de cenário do que soluções tradicionais. Seguindo uma linha semelhante, o presente trabalho concentra-se no projeto e análise MACs leves e seguros voltados a cenários com recursos limitados, com foco especial em redes de sensores sem fio (RSSF). Marvin é o nome do algoritmo de MAC proposto neste trabalho. Marvin adota a estrutura Alred, que reutiliza porções de código de uma cifra de bloco subjacente e...

Projeto e avaliação de um co-processador  criptográfico pós-quântico.; Design and evaluation of a post-quantum cryptographic co-processor.

Massolino, Pedro Maat Costa
Fonte: Biblioteca Digitais de Teses e Dissertações da USP Publicador: Biblioteca Digitais de Teses e Dissertações da USP
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 14/07/2014 PT
Relevância na Pesquisa
25.9%
Primitivas criptografias assimétricas são essenciais para conseguir comunicação segura numa rede ou meio público. Essas primitivas podem ser instaladas como bibliotecas de software ou como coprocessadores de hardware. Coprocessadores de hardware são muito utilizados em cenários como Systems on Chip (SoC), dispositivos embarcados ou servidores de aplicações específicas. Coprocessadores existentes baseados em RSA ou curvas ellipticas (ECC) fazem um processamento intenso por causa da aritmética modular de grande precisão, portanto não estão disponíveis em plataformas com quantidade de energia mais restrita. Para prover primitivas assimétricas para esses dispositivos, será avaliado um esquema de cifração assimétrica que utiliza artimética de pequena precisão, chamado McEliece. McEliece foi proposto com códigos de Goppa binários durante o mesmo ano que o RSA, porém com chaves públicas 50 vezes maiores. Por causa de chaves tão grandes ele não ganhou muita atenção como RSA e ECC. Com a adoção de códigos Quase-Diádicos de Goppa binários é possível obter níveis de segurança práticos com chaves relativamente pequenas. Para avaliar uma implementação em hardware para esse esquema, foi proposto uma arquitetura escalável que pode ser configurada de acordo com os requisitos do projeto. Essa arquitetura pode ser utilizada em todos os níveis de segurança...

Temporal behavior of Ethernet communications: Impact of the operating system and protocol stack

Pedro Silva; Luis Almeida; Mário de Sousa; Ricardo Marau
Fonte: Universidade do Porto Publicador: Universidade do Porto
Tipo: Artigo de Revista Científica
ENG
Relevância na Pesquisa
26.45%
Ethernet is currently the most widely used networking technology, spanning across many application domains including embedded systems. In this particular case, Ethernet is even used in many time-critical applications in which the delay induced by communication must be short and bounded. It is thus very important to understand the entire transmission process and assess its temporal behavior. There are a number of aspects to consider, including the network protocol, network topology, network elements and end devices. This paper aims at assessing the impact of the operating system and its protocol stack implementation in the end devices on the network temporal behavior. We studied four operating systems, namely a standard Ubuntu distribution with and without a real-time kernel patch, an embedded stripped down version of Linux and QNX Neutrino, and two hardware platforms, namely ordinary PCs and a single board computer based on an AVR32 CPU. We measured the Round Trip Delay (RTD) using RAW, UDP and TCP sockets to interface the protocol stack. We verified that on high computing power platforms the difference between the sockets is small but still significant in resource-constrained platforms. On the other hand, full featured general OSs present rather large worst-case delays. These can be reduced using real-time patches for those OSs...

The Regulation of Light Sensing and Light-Harvesting Impacts the Use of Cyanobacteria as Biotechnology Platforms

Montgomery, Beronda L.
Fonte: Frontiers Media S.A. Publicador: Frontiers Media S.A.
Tipo: Artigo de Revista Científica
Publicado em 01/07/2014 EN
Relevância na Pesquisa
26.17%
Light is harvested in cyanobacteria by chlorophyll-containing photosystems embedded in the thylakoid membranes and phycobilisomes (PBSs), photosystem-associated light-harvesting antennae. Light absorbed by the PBSs and photosystems can be converted to chemical energy through photosynthesis. Photosynthetically fixed carbon pools, which are constrained by photosynthetic light capture versus the dissipation of excess light absorbed, determine the available organismal energy budget. The molecular bases of the environmental regulation of photosynthesis, photoprotection, and photomorphogenesis are still being elucidated in cyanobacteria. Thus, the potential impacts of these phenomena on the efficacy of developing cyanobacteria as robust biotechnological platforms require additional attention. Current advances and persisting needs for developing cyanobacterial production platforms that are related to light sensing and harvesting include the development of tools to balance the utilization of absorbed photons for conversion to chemical energy and biomass versus light dissipation in photoprotective mechanisms. Such tools can be used to direct energy to more effectively support the production of desired bioproducts from sunlight.

Paper and Flexible Substrates as Materials for Biosensing Platforms to Detect Multiple Biotargets

Shafiee, Hadi; Asghar, Waseem; Inci, Fatih; Yuksekkaya, Mehmet; Jahangir, Muntasir; Zhang, Michael H.; Durmus, Naside Gozde; Gurkan, Umut Atakan; Kuritzkes, Daniel R.; Demirci, Utkan
Fonte: Nature Publishing Group Publicador: Nature Publishing Group
Tipo: Artigo de Revista Científica
EN_US
Relevância na Pesquisa
26.17%
The need for sensitive, robust, portable, and inexpensive biosensing platforms is of significant interest in clinical applications for disease diagnosis and treatment monitoring at the point-of-care (POC) settings. Rapid, accurate POC diagnostic assays play a crucial role in developing countries, where there are limited laboratory infrastructure, trained personnel, and financial support. However, current diagnostic assays commonly require long assay time, sophisticated infrastructure and expensive reagents that are not compatible with resource-constrained settings. Although paper and flexible material-based platform technologies provide alternative approaches to develop POC diagnostic assays for broad applications in medicine, they have technical challenges integrating to different detection modalities. Here, we address the limited capability of current paper and flexible material-based platforms by integrating cellulose paper and flexible polyester films as diagnostic biosensing materials with various detection modalities through the development and validation of new widely applicable electrical and optical sensing mechanisms using antibodies and peptides. By incorporating these different detection modalities, we present selective and accurate capture and detection of multiple biotargets including viruses (Human Immunodeficieny Virus-1)...

Pricing strategies in software platforms : video consoles vs. operating systems

Viecens, María Fernanda
Fonte: Universidade Carlos III de Madrid Publicador: Universidade Carlos III de Madrid
Tipo: Trabalho em Andamento Formato: application/pdf
Publicado em /05/2007 ENG; ENG
Relevância na Pesquisa
36.23%
We study software platforms for which the total amount that users spend depends on the twosided pricing strategy of the platform firm, and on the pricing strategy of application developers. When setting prices, developers may be constrained by one of two margins: the demand margin and the competition margin. By analyzing how these margins affect pricing strategies we find some conditions which explain features of the market of operating systems and its differences with the one corresponding to the video consoles. The problem that arises when the platform does not set prices (as an open platform) is considered. We show that policy makers should promote open source in operating systems platforms but not necessarily in video consoles. We also analyze the incentives for a platform to integrate with applications as a function of the extent of substitutability among them and provide a possible explanation for the observed fact of vertical disintegration in these industries.

Essays in two-sided platforms

Viecens, María Fernanda
Fonte: Universidade Carlos III de Madrid Publicador: Universidade Carlos III de Madrid
Tipo: info:eu-repo/semantics/doctoralThesis; info:eu-repo/semantics/doctoralThesis Formato: application/pdf
ENG
Relevância na Pesquisa
26.32%
In the first chapter we present a critical survey of the literature on platforms and two-sided markets. First, we introduce two general models, called the “Armstrong’s model” and the “Rochet-Tirole’s model”, to understand the main issues that arise in the literature. Second, we analyze some of the main assumptions of the above models. Finally, we review some articles related to specific markets and to competition policy issues. In the second chapter we study software platforms for which the total amount that users spend depends on the two-sided pricing strategy of the platform firm, and on the pricing strategy of application developers. When setting prices, developers may be constrained by one of two margins: the demand margin and the competition margin. By analyzing how these margins affect pricing strategies we find some conditions which explain features of the market of operating systems and its differences with the one corresponding to the video consoles. The problem that arises when the platform does not set prices (as an open platform) is considered. We show that policy makers should promote open source in operating systems platforms but not necessarily in video consoles. We also analyze the incentives for a platform to integrate with applications as a function of the extent of substitutability among them and provide a possible explanation for the observed fact of vertical disintegration in these industries. Third chapter analyzes the effect of firm dominance on the incentives to become compatible and how compatibility decisions affect investment incentives. We will consider compatibility in two dimensions: compatibility of the complementary good and inter-network compatibility. We show that if products are substitutes...

Optimizing employment of search platforms to counter self-propelled semi-submersibles

Pfeiff, Daniel M.
Fonte: Monterey, California. Naval Postgraduate School Publicador: Monterey, California. Naval Postgraduate School
Tipo: Tese de Doutorado Formato: xviii, 73 p. : ill. (chiefly col.) ;
Relevância na Pesquisa
26.33%
Approved for public release, distribution unlimited; Self-Propelled Semi-Submersibles now transport an estimated 75% of cocaine originating from Colombia and headed for the United States. There are several types of search platforms (i.e., units to detect, classify, and interdict) being employed by the Joint Interagency Task Force South to combat the semi-submersibles. We use a defender-attacker optimization model to maximize the defender's probability of successful detection and classification of the semisubmersible through the advantageous disposition of these search platforms against an intelligent attacker operating the semi-submersible. We assume the attacker has imperfect knowledge of defender platform disposition but is aware that there are defenders that must be avoided. Given this assumption, the solution to the defender-attacker model is a mixed (i.e., probabilistic) strategy for the defender and a least-risk path for the attacker. We demonstrate our defender-attacker model with both an Eastern Pacific and a Caribbean scenario using five representative search platform types whose detection and classification performance vary by platform, and by geography. In each of these cases, we find that our model prescribes a face-valid defensive plan; defenders take advantage of geography by positioning at chokepoints in constrained waterways...

RealCrono –sistema de difusão de resultados em tempo real na web

Carneiro, Jorge Manuel Nunes
Fonte: Instituto Politécnico do Porto Publicador: Instituto Politécnico do Porto
Tipo: Dissertação de Mestrado
Publicado em //2013 POR
Relevância na Pesquisa
26.27%
A velocidade de difusão de conteúdos numa plataforma web, assume uma elevada relevância em serviços onde a informação se pretende atualizada e em tempo real. Este projeto de Mestrado, apresenta uma abordagem de um sistema distribuído de recolher e difundir resultados em tempo real entre várias plataformas, nomeadamente sistemas móveis. Neste contexto, tempo real entende-se como uma diferença de tempo nula entre a recolha e difusão, ignorando fatores que não podem ser controlados pelo sistema, como latência de comunicação e tempo de processamento. Este projeto tem como base uma arquitetura existente de processamento e publicação de resultados desportivos, que apresentava alguns problemas relacionados com escalabilidade, segurança, tempos de entrega de resultados longos e sem integração com outras plataformas. Ao longo deste trabalho procurou-se investigar fatores que condicionassem a escalabilidade de uma aplicação web dando ênfase à implementação de uma solução baseada em replicação e escalabilidade horizontal. Procurou-se também apresentar uma solução de interoperabilidade entre sistemas e plataformas heterogêneas, mantendo sempre elevados níveis de performance e promovendo a introdução de plataformas móveis no sistema. De várias abordagens existentes para comunicação em tempo real sobre uma plataforma web...

Paper and Flexible Substrates as Materials for Biosensing Platforms to Detect Multiple Biotargets

Shafiee, Hadi; Asghar, Waseem; Inci, Fatih; Yuksekkaya, Mehmet; Jahangir, Muntasir; Zhang, Michael H.; Durmus, Naside Gozde; Gurkan, Umut Atakan; Kuritzkes, Daniel R.; Demirci, Utkan
Fonte: Nature Publishing Group Publicador: Nature Publishing Group
Tipo: Artigo de Revista Científica
Publicado em 06/03/2015 EN
Relevância na Pesquisa
26.17%
The need for sensitive, robust, portable, and inexpensive biosensing platforms is of significant interest in clinical applications for disease diagnosis and treatment monitoring at the point-of-care (POC) settings. Rapid, accurate POC diagnostic assays play a crucial role in developing countries, where there are limited laboratory infrastructure, trained personnel, and financial support. However, current diagnostic assays commonly require long assay time, sophisticated infrastructure and expensive reagents that are not compatible with resource-constrained settings. Although paper and flexible material-based platform technologies provide alternative approaches to develop POC diagnostic assays for broad applications in medicine, they have technical challenges integrating to different detection modalities. Here, we address the limited capability of current paper and flexible material-based platforms by integrating cellulose paper and flexible polyester films as diagnostic biosensing materials with various detection modalities through the development and validation of new widely applicable electrical and optical sensing mechanisms using antibodies and peptides. By incorporating these different detection modalities, we present selective and accurate capture and detection of multiple biotargets including viruses (Human Immunodeficieny Virus-1)...

Scaling efficient code-based cryptosystems for embedded platforms

Biasi, Felipe P.; Barreto, Paulo S. L. M.; Misoczki, Rafael; Ruggiero, Wilson V.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 18/12/2012
Relevância na Pesquisa
36.08%
We describe a family of highly efficient codes for cryptographic purposes and dedicated algorithms for their manipulation. Our proposal is especially tailored for highly constrained platforms, and surpasses certain conventional and post-quantum proposals (like RSA and NTRU, respectively) according to most if not all efficiency metrics.

Power-Aware Real-Time Scheduling upon Identical Multiprocessor Platforms

Nélis, Vincent; Goossens, Joël; Navet, Nicolas; Devillers, Raymond; Milojevic, Dragomir
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
26.08%
In this paper, we address the power-aware scheduling of sporadic constrained-deadline hard real-time tasks using dynamic voltage scaling upon multiprocessor platforms. We propose two distinct algorithms. Our first algorithm is an off-line speed determination mechanism which provides an identical speed for each processor. That speed guarantees that all deadlines are met if the jobs are scheduled using EDF. The second algorithm is an on-line and adaptive speed adjustment mechanism which reduces the energy consumption while the system is running.; Comment: The manuscript corresponds to the final version of SUTC 2008 conference

MORA: an Energy-Aware Slack Reclamation Scheme for Scheduling Sporadic Real-Time Tasks upon Multiprocessor Platforms

Nelis, Vincent; Goossens, Joel
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 01/06/2009
Relevância na Pesquisa
26.08%
In this paper, we address the global and preemptive energy-aware scheduling problem of sporadic constrained-deadline tasks on DVFS-identical multiprocessor platforms. We propose an online slack reclamation scheme which profits from the discrepancy between the worst- and actual-case execution time of the tasks by slowing down the speed of the processors in order to save energy. Our algorithm called MORA takes into account the application-specific consumption profile of the tasks. We demonstrate that MORA does not jeopardize the system schedulability and we show by performing simulations that it can save up to 32% of energy (in average) compared to execution without using any energy-aware algorithm.; Comment: 11 pages

LPKI - A Lightweight Public Key Infrastructure for the Mobile Environments

Toorani, M.; Beheshti, A. A.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
26.23%
The non-repudiation as an essential requirement of many applications can be provided by the asymmetric key model. With the evolution of new applications such as mobile commerce, it is essential to provide secure and efficient solutions for the mobile environments. The traditional public key cryptography involves huge computational costs and is not so suitable for the resource-constrained platforms. The elliptic curve-based approaches as the newer solutions require certain considerations that are not taken into account in the traditional public key infrastructures. The main contribution of this paper is to introduce a Lightweight Public Key Infrastructure (LPKI) for the constrained platforms such as mobile phones. It takes advantages of elliptic curve cryptography and signcryption to decrease the computational costs and communication overheads, and adapting to the constraints. All the computational costs of required validations can be eliminated from end-entities by introduction of a validation authority to the introduced infrastructure and delegating validations to such a component. LPKI is so suitable for mobile environments and for applications such as mobile commerce where the security is the great concern.; Comment: 6 Pages, 6 Figures

Elliptic Curve Based Zero Knowledge Proofs and Their Applicability on Resource Constrained Devices

Chatzigiannakis, Ioannis; Pyrgelis, Apostolos; Spirakis, Paul G.; Stamatiou, Yannis C.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 08/07/2011
Relevância na Pesquisa
26.14%
Elliptic Curve Cryptography (ECC) is an attractive alternative to conventional public key cryptography, such as RSA. ECC is an ideal candidate for implementation on constrained devices where the major computational resources i.e. speed, memory are limited and low-power wireless communication protocols are employed. That is because it attains the same security levels with traditional cryptosystems using smaller parameter sizes. Moreover, in several application areas such as person identification and eVoting, it is frequently required of entities to prove knowledge of some fact without revealing this knowledge. Such proofs of knowledge are called Zero Knowledge Interactive Proofs (ZKIP) and involve interactions between two communicating parties, the Prover and the Verifier. In a ZKIP, the Prover demonstrates the possesion of some information (e.g. authentication information) to the Verifier without disclosing it. In this paper, we focus on the application of ZKIP protocols on resource constrained devices. We study well-established ZKIP protocols based on the discrete logarithm problem and we transform them under the ECC setting. Then, we implement the proposed protocols on Wiselib, a generic and open source algorithmic library. Finally...

Exact Feasibility Tests for Real-Time Scheduling of Periodic Tasks upon Multiprocessor Platforms

Cucu, Liliana; Goossens, Joël
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 28/01/2008
Relevância na Pesquisa
26.43%
In this paper we study the global scheduling of periodic task systems upon multiprocessor platforms. We first show two very general properties which are well-known for uniprocessor platforms and which remain for multiprocessor platforms: (i) under few and not so restrictive assumptions, we show that feasible schedules of periodic task systems are periodic from some point with a period equal to the least common multiple of task periods and (ii) for the specific case of synchronous periodic task systems, we show that feasible schedules repeat from the origin. We then present our main result: we characterize, for task-level fixed-priority schedulers and for asynchronous constrained or arbitrary deadline periodic task models, upper bounds of the first time instant where the schedule repeats. We show that job-level fixed-priority schedulers are predictable upon unrelated multiprocessor platforms. For task-level fixed-priority schedulers, based on the upper bounds and the predictability property, we provide for asynchronous constrained or arbitrary deadline periodic task sets, exact feasibility tests. Finally, for the job-level fixed-priority EDF scheduler, for which such an upper bound remains unknown, we provide an exact feasibility test as well.

CheepSync: A Time Synchronization Service for Resource Constrained Bluetooth Low Energy Advertisers

Sridhar, Sabarish; Misra, Prasant; Warrior, Jay
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 26/01/2015
Relevância na Pesquisa
26.23%
Clock synchronization is highly desirable in distributed systems, including many applications in the Internet of Things and Humans (IoTH). It improves the efficiency, modularity and scalability of the system; and optimizes use of event triggers. For IoTH, Bluetooth Low Energy (BLE) - a subset of the recent Bluetooth v4:0 stack - provides a low-power and loosely coupled mechanism for sensor data collection with ubiquitous units (e.g., smartphones and tablets) carried by humans. This fundamental design paradigm of BLE is enabled by a range of broadcast advertising modes. While its operational benefits are numerous, the lack of a common time reference in the broadcast mode of BLE has been a fundamental limitation. This paper presents and describes CheepSync: a time synchronization service for BLE advertisers, especially tailored for applications requiring high time precision on resource constrained BLE platforms. Designed on top of the existing Bluetooth v4:0 standard, the CheepSync framework utilizes low-level timestamping and comprehensive error compensation mechanisms for overcoming uncertainties in message transmission, clock drift and other system specific constraints. CheepSync was implemented on custom designed nRF24Cheep beacon platforms (as broadcasters) and commercial off-the-shelf Android ported smartphones (as passive listeners). We demonstrate the efficacy of CheepSync by numerous empirical evaluations in a variety of experimental setups; and show that its average (single-hop) time synchronization accuracy is in the 10u?s range.

Unconstrained and Constrained Fault-Tolerant Resource Allocation

Liao, Kewen; Shen, Hong
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 12/06/2011
Relevância na Pesquisa
26.05%
First, we study the Unconstrained Fault-Tolerant Resource Allocation (UFTRA) problem (a.k.a. FTFA problem in \cite{shihongftfa}). In the problem, we are given a set of sites equipped with an unconstrained number of facilities as resources, and a set of clients with set $\mathcal{R}$ as corresponding connection requirements, where every facility belonging to the same site has an identical opening (operating) cost and every client-facility pair has a connection cost. The objective is to allocate facilities from sites to satisfy $\mathcal{R}$ at a minimum total cost. Next, we introduce the Constrained Fault-Tolerant Resource Allocation (CFTRA) problem. It differs from UFTRA in that the number of resources available at each site $i$ is limited by $R_{i}$. Both problems are practical extensions of the classical Fault-Tolerant Facility Location (FTFL) problem \cite{Jain00FTFL}. For instance, their solutions provide optimal resource allocation (w.r.t. enterprises) and leasing (w.r.t. clients) strategies for the contemporary cloud platforms. In this paper, we consider the metric version of the problems. For UFTRA with uniform $\mathcal{R}$, we present a star-greedy algorithm. The algorithm achieves the approximation ratio of 1.5186 after combining with the cost scaling and greedy augmentation techniques similar to \cite{Charikar051.7281.853...

Semi-Partitioned Hard Real-Time Scheduling with Restricted Migrations upon Identical Multiprocessor Platforms

Dorin, François; Yomsi, Patrick Meumeu; Goossens, Joël; Richard, Pascal
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 14/06/2010
Relevância na Pesquisa
26.08%
Algorithms based on semi-partitioned scheduling have been proposed as a viable alternative between the two extreme ones based on global and partitioned scheduling. In particular, allowing migration to occur only for few tasks which cannot be assigned to any individual processor, while most tasks are assigned to specific processors, considerably reduces the runtime overhead compared to global scheduling on the one hand, and improve both the schedulability and the system utilization factor compared to partitioned scheduling on the other hand. In this paper, we address the preemptive scheduling problem of hard real-time systems composed of sporadic constrained-deadline tasks upon identical multiprocessor platforms. We propose a new algorithm and a scheduling paradigm based on the concept of semi-partitioned scheduling with restricted migrations in which jobs are not allowed to migrate, but two subsequent jobs of a task can be assigned to different processors by following a periodic strategy.