Um Modelo Formal para Verificação da Consistência de - PUC-Rio

Um Modelo Formal para Verificação da Consistência de Documentos Hipermídia NCM
C.A.S. Santos1
J-P. Courtiat1
G.L. de Souza2
L.F.G. Soares3
[email protected]
[email protected]
[email protected]
[email protected]
1
LAAS-CNRS, 7 avenue du Colonel Roche, 31400 Toulouse Cedex, France
DIMAp, UFRN, Campus Universitário, Lagoa Nova, 59072-970 - Natal-RN, Brazil
3
Dept. Informática, PUC-Rio, R. Marquês S. Vicente 225, 22453-900 - Rio de Janeiro, Brazil
2
Resumo
Este artigo apresenta uma metodologia para especificação e validação da estrutura lógica e temporal do
modelo NCM, desenvolvido e implementado no ambiente de autoria e execução de documentos HyperProp. A
idéia básica é mostrar como uma técnica de descrição formal de propósito geral como LOTOS (na verdade uma
extensão temporal de LOTOS, chamada RT_LOTOS), pode ser usada para formalizar os comportamentos
temporais de documentos que podem ser expressos pelo modelo NCM. A validação de documentos é então
realizada através da identificação de inconsistências temporais potenciais através da aplicação de técnicas de
validação desenvolvidas e implementadas para RT-LOTOS. A noção de consistência dos documentos considera,
além de suas restrições lógicas e temporais, restrições impostas pela plataforma multimídia onde ele será
exibido, permitindo verificar se um documento intrinsecamente consistente pode ser apresentado
adequadamente em uma dada plataforma.
Abstract
This paper presents a methodology for formally specifying and validating the temporal and logical structure of
the Nested Context Model designed and implemented in the HyperProp authoring and execution environment. It
shows how a general-purpose formal description technique like LOTOS (in fact a temporal extension of LOTOS,
called RT-LOTOS), may easily and consistently be used for formalizing the highly complex temporal behaviors
that may be expressed using the NCM model. Validating a hypermedia document looking for potential temporal
inconsistencies is then performed using standard validation techniques that have been developed and
implemented for RT-LOTOS. The notion of consistency is generalized to a multimedia platform by assessing
whether a document, consistent per se, can effectively be presented on that platform.
1. Introdução
O problema central na concepção de um documento multimídia é a definição da sua estrutura
lógico-temporal, ou seja, a definição das relações de cooperação e coordenação entre as
diversas mídias que o compõem [BlSt96]. Define-se por sincronização multimídia, o conjunto
de ações executadas para controlar estas relações durante a apresentação de um documento.
Diversos modelos para especificação da estrutura temporal de documentos multi e hipermídia
foram propostos. Destacam-se, entre outros, os modelos de sincronização baseados em
intervalos temporais [WaRo94], os de descrição hierárquica das sincronizações [LiGh90], os
baseados em pontos de referência [BuZe93] e os baseados em redes de Petri Temporizadas
[WiSS97].
O presente trabalho propõe uma metodologia para contruir uma especificação baseada na
extensão temporal da Técnica de Descrição Formal (ou FDT) LOTOS [BoBr87] denominada RT-LOTOS [CoOl94] - para formalizar e validar documentos multi/hipermídia
construídos a partir do modelo NCM [SoSo96]. A idéia central da proposta é esconder dos
autores de documentos toda a complexidade envolvida no uso de uma FDT para especificar os
documentos que são por eles editados. Para tal, propõe-se um esquema de mapeamento direto
das entidades NCM (nós, elos e ancoras) em processos RT-LOTOS. Cabe ressaltar que o
mapeamento pode ser automatizado e integrado às ferramentas de autoria do sistema
HyperProp [SoCa95]. A metodologia é genérica, hierárquica e, dado que está baseada numa
FDT, a consistência temporal do documento pode ser garantida a partir da análise da
especificação obtida. Mais ainda, o mesmo princípio pode ser aplicado para representar outros
modelos multi/hipermídia baseados em eventos.
A obtenção de uma descrição formal RT-LOTOS de um documento NCM permite definir
uma semântica precisa para esse modelo, evitando descrições ambíguas do comportamento da
apresentação de um documento. Além disso, esta descrição permitirá a aplicação das técnicas
desenvolvidas e implementadas na ferramenta RTL [CoOl95] para verificação da consistência
de um documento, seja em relação as suas restrições temporais intrínsecas, seja em relação às
restrições adicionais relativas à plataforma onde o documento vai ser apresentado. No escopo
deste trabalho, um documento é dito ser consistente quando sua apresentação termina
decorrido um tempo finito após seu início [CoOl96, SCSS97].
O artigo está divido em quatro seções: a primeira define rapidamente os conceitos do modelo
NCM; a segunda trata da metodologia desenvolvida para gerar a especificação formal de um
documento NCM; a terceira mostra um exemplo de aplicação e os resultados obtidos. Por fim,
as conclusões gerais dos resultados do trabalho são apresentadas.
2. O Modelo NCM
Um documento hipermídia é definido no modelo NCM a partir dos conceitos usuais de nós e
elos. Os nós são constituídos de fragmentos de informação e os elos são usados para exprimir
todas as possíveis relações entre os diferentes nós que constituem o documento. Existem duas
classes básicas de nós: os nós terminais e os nós de composição, sendo estes últimos o ponto
central do modelo.
Um nó terminal (ou nó de conteúdo) contém um conjunto de dados, cuja estrutura interna é
dependente da aplicação, como no caso dos nós hipermídia tradicionais. A classe de nós
terminais pode ser especializada em outras classes (por ex., texto, gráfico, áudio, vídeo),
conforme requerido pelas aplicações. Um nó de composição contém uma coleção de elos e
nós, de conteúdo ou de composição, inter-relacionados. Dado que os nós de composição
podem ser aninhados em qualquer profundidade (desde que a restrição de um nó não conter
recursivamente a si mesmo seja obedecida) e que diferentes composições podem conter um
mesmo nó, é necessário introduzir o conceito de perspectiva. A perspectiva identifica de
forma única a seqüência de nós de composição aninhados correspondente a instância do nó
que está sendo observada.
Um elo é caracterizado como uma relação m:n entre um conjunto de pontos terminais origem
e destino. Os pontos terminais origem e destino especificam eventos, os quais podem ser a
exibição ou seleção de um conjunto não vazio de unidades de informação1 e ainda, a mudança
de um atributo de um objeto componente do documento, chamado evento de atribuição. O elo
possui ainda um ponto de encontro que define uma lista de condições e ações, especificando
relações entre os eventos que o caracterizam. Assim, condições devem ser satisfeitas em
eventos de origem para que ações sejam aplicadas nos eventos de destino. Normalmente, as
condições são descritas como algo do tipo “um evento E ocorreu ou está ocorrendo, …”, e as
ações como “inicie um evento, modifique a apresentação de um nó em exibição, …”.
Outra característica do NCM é que para cada nó, o qual passa a ser denominado nó objeto de
dados, é associado um objeto descritor. Um descritor especifica como um nó objeto de dados
1 A noção exata do que se constitui uma unidade de informação é parte da definição do tipo de mídia do objeto componente do documento.
será exibido, detalhando como será iniciado (métodos de exibição), qual dispositivo de E/S
será utilizado e quais mudanças ocorrerão no seu comportamento durante sua exibição, caso
elas existam. O descritor contém adicionalmente toda a informação necessária à obtenção do
nó objeto de dados associado, tais como o custo de transferência (retardo, banda passante,
etc). A agregação de um descritor a um nó objeto de dados dá origem a um nó objeto de
representação, ou simplesmente, objeto de representação. O identificador do descritor, a ser
associado a um nó objeto de dados, pode ser definido em um atributo do próprio nó a partir do
qual o objeto de representação será criado. Os elos também podem possuir um conjunto de
identificadores de descritores, como no Modelo Dexter, que contém informações para o
modelo de apresentação indicando como os objetos de representação devem ser criados. Os
nós de composição também possuem, para cada um dos seus nós componentes, um atributo
onde pode ser definido o identificador do descritor que deve ser utilizado na criação do objeto
representação do componente.
3. Especificação Formal do modelo NCM
A idéia central desta seção é não só apresentar uma descrição formal para o exemplo
específico utilizado neste trabalho, mas também definir uma metodologia geral para mapear
qualquer documento hipermídia baseado no modelo NCM numa Técnica de Descrição Formal
(FDT). Entre as diversas vantagens apresentadas por esse tipo de abordagem, pode-se
destacar:
•
Simplificação da tarefa de elaborar uma especificação formal do documento. A
metodologia permite que qualquer usuário capaz de editar um documento utilizando
ferramentas de autoria de alto nível obtenha uma especificação formal, mesmo nao tendo
o conhecimento básico que seria necessário para produzi-la diretamente;
•
Aplicação das técnicas de verificação sobre a especificação (obtida através da tradução do
modelo de autoria numa FDT) do documento para analisar suas propriedades,
particularmente, a consistência temporal e a consistência em relação a plataforma utilizada
para a sua apresentação.
A escolha do RT-LOTOS como método formal para o mapeamento é plenamente justificada
pela ênfase deste método à composição hierárquica de processos (similar ao sistema de nós de
composição do NCM), por sua semântica formal, sua habilidade para expressar tanto o nãodeterminismo como as restrições temporais dos sistemas e, finalmente, pela disponibilidade e
confiabilidade da ferramenta RTL (RT-LOTOS Laboratory) para verificação e simulação de
sistemas [CoOl95].
3.1. O FDT Real Time LOTOS
Um sistema descrito em LOTOS é visto como um processo composto por diversos subprocessos. Esses sub-processos são também processos LOTOS que podem ser, de maneira
semelhante, decompostos hierarquicamente [BoBr87]. Um processo é composto de uma lista
de ações externas (ou observáveis) e de uma lista de ações internas (ou não-observáveis). As
ações externas são mapeadas sobre um conjunto de portas de comunicação que são utilizadas
para as interações do processo com o ambiente externo e, consequentemente, com outros
processos. Estas interações dão origem às sincronizações que são a base das especificações
LOTOS. Se dois ou mais processos se sincronizam sobre uma ação (ou sobre uma porta), esta
ação tem que ser executada ao mesmo tempo por todos os processos envolvidos. Além disso,
dado que uma sincronização pode envolver a troca de valores, estabelece-se que ao fim desta
operação os valores oferecidos pelas portas envolvidas devem ser os mesmos. Vale lembrar
também que a execução das ações é considerada instantânea.
Dado que o padrão LOTOS não tem a capacidade de expressar restrições temporais, algumas
extensões a seus operadores têm sido propostas (dentre as quais o RT-LOTOS [CoOl94]), as
quais atualmente convergem para uma versão comum a ser padronizada, denominada (ELOTOS). A lista parcial dos operadores RT-LOTOS adicionada ao padrão LOTOS é
mostrada a seguir:
Atraso fixo
Atraso aleatório
Validade Temporal da ação
delay(d) B
delay(dmin,dmax) B
g{t} O1…On;B
Figura 1 – Principais operadores RT-LOTOS
B corresponde a uma expressão de comportamento genérica LOTOS. O operador de atraso
retarda a execução de B de um valor fixo d, ou de um valor aleatório compreendido entre dmin
e dmax de unidades de tempo. Enfim, o operador de validade temporal limita o tempo de oferta
da ação ao ambiente. Ele é, por definição, “∞” no caso de ações externas e “0” para as
internas.
3.2. Mapeamento dos Objetos NCM
O mapeamento dos objetos NCM sobre processos RT-LOTOS é baseado no fato de que é
possível encontrar uma relação direta entre a hierarquia de composições do modelo NCM e a
hierarquia de processos de uma especificação RT-LOTOS. Mais ainda, é possivel construir
uma biblioteca de processos básicos que especifiquem os objetos de base da estrutura NCM,
como por exemplo, os elos e os nós de conteúdo. A proposta é suficientemente geral para que
possa ser automatizada e incorporada dentro do sistema de autoria de documentos.
O modelo NCM tem como estrutura principal o Nó de Composição (Composite Node), cuja
tradução em RT-LOTOS é mostrada na Figura 4. A característica principal deste processo é a
possiblidade de instanciá-lo com diferentes versões (ou descritores) e de maneira recursiva.
Cada nó de composição possui uma lista de parâmetros que correspondem aos descritores dos
nós, elos e âncoras pertencentes às composições que estão no nível hierárquico inferior em
relação à perspectiva.
Um nó é identificado por seu parâmetro nodeID. Cada nó tem um conjunto de portas start e
end caracterizando o início e o fim da apresentação, user associada à interação com o usuário
sobre uma âncora, e trigger correspondendo a ação decorrente da interação do usuário sobre
uma âncora que pertence a outro nó, mas que modifica a apresentação do nó em questão. As
portas possuem parâmetros que asseguram a correta sincronização das ações com os seus
respectivos nós (nodeID) e âncoras (anchorID).
process compositeNode[start,end,user,trigger]
(nodeID:nat, nodeList:nodeDescriptorList, anchorList:anchorDescriptorList, linkList:linkDescriptorList ) :=
hide endRequest in
start !nodeID?version:nat;
( ( ( nodeBody[user,endRequest](version,nodeList,anchorList,linkList) [> end{0}!nodeID!version; exit )
|[endRequest,end]| terminationNode[endRequest,end](nodeID, version, nodeList) )
|||
compositeNode[start,end,user,trigger] (nodeID, nodeList,anchorList,linkList) ) [] exit
where
process nodeBody[user,endRequest]
(version:nat, nodeList:nodeDescriptorList,anchorList:anchorDescriptorList,linkList:linkDescriptorList) :=
hide start,end,trigger in
nodePresentations[start,end,user,trigger](version,nodeList,anchorList,linkList)
|[start,end,trigger]|
nodeConstraints[start,end,trigger](version,linkList)
where
process nodePresentations[start,end,user,trigger]
(version:nat, nodeList:nodeDescriptorList,anchorList:anchorDescriptorList, linkList:linkDescriptorList) :=
nodeStructure[start,end,user,trigger] (version,nodeList,anchorList,linkList)
|||
nodeInteractions[user,trigger] (version,anchorList)
where
process nodeStructure[start,end,user,trigger] (version:nat,nodeList:nodeDescriptorList,
anchorList:anchorDescriptorList,linkList:linkDescriptorList) := ...endproc
process nodeInteractions[user,trigger] (version:nat, anchorList:anchorDescriptorList) :=
interactionsCapture[user,trigger] (anchor_1)
||| … ||| interactionsCapture[user,trigger] (anchor_i)
||| … ||| interactionsCapture[user,trigger] (anchor_n)
endproc
endproc
process nodeConstraints[start,end,trigger] (version:nat, linkList:linkDescriptorList) :=
link[start,end] (descriptorLink_1)
|[…]| … |[…]| link[trigger,end] (descriptorLink_i)
|[…]| … |[…]| link[trigger,start] (descriptorLink_n)
endproc
endproc
endproc
Figura 2 – O Processo CompositeNode Genérico
Quando um processo CompositeNode com algum nodeID é instanciado, ele recebe um valor
correspondente a versão (version) que deve ser apresentada. Através destes parâmetros, os
valores dos descritores dos nós, elos e âncoras da composição podem ser obtidos nas listas de
descritores que são passadas como parâmetro ao processo. Desta forma, diferentes versões de
um mesmo nó podem ser facilmente implementadas, somente com a mudança de seus
parâmetros.
Uma vez que a sincronização com a ação start é realizada, o comportamento do processo
passa a ser descrito pelo processo nodeBody e pelas restrições de finalização do nó (processo
terminationNode).
O processo nodeBody descreve a estrutura interna da composição, a qual é composta de uma
parte correspondente aos objetos de apresentação, modelada pelo processo nodePresentaions,
e outra relativa às restrições destas apresentações, pelo processo nodeConstraints.
O processo nodePresentations é descrito com a composição paralela dos processos
nodeStructure e nodeInteractions. O primeiro corresponde ao conjunto de nós de conteúdo e
de composição que pertencem ao nó de composição em questão, e o segundo, ao conjunto de
âncoras visíveis e destinadas a capturar as interações do usuário durante a apresentação desse
nó. As âncoras são modeladas pelos processos interactionCapture, os quais expressam todos
as possíveis eventos relacionados às interações com o usuário (múltiplas interações
consecutivas, tempo máximo disponível para uma interação, etc).
O processo nodeConstraints corresponde a uma composição paralela com sincronização dos
processos link pertencentes a esta perspectiva do nó e que modelam as interações entre os
diversos processos da composição. Os processos link são constituídos por uma ação de
entrada e outra de saída que é oferecida após um retardo e durante um intervalo limitado de
tempo. A composição de diversos processos link (não apresentada no trabalho) permite a
construção de operadores lógicos tais como AND, OR ou XOR.
4. Exemplo
O exemplo utilizado neste trabalho trata de uma composição NCM, que representa a estrutura
lógica de parte de um documento hipermídia sobre o Carnaval. A composição C contém
quatro nós, V, A, AT e I, e três elos l3, l4 e l5. Ela tem também dois pontos de entrada, através
dos elos l1 e l2, chegando de outras partes do documento. O nó de conteúdo V contém uma
sequência de vídeo mostrando a construção de uma alegoria, A contém um samba a ser
executado durante a apresentação e o nó I contém uma imagem relacionada ao povo da
favela, representando a verdadeira essência do Carnaval. Por fim, o nó AT é um nó de
conteúdo que pode ser apresentado como texto ou com áudio, dependendo do descritor
utilizado. O fim da apresentação de I marca o fim da apresentação da composição C, levandoa, através de l6, para outra parte do documento Carnaval.
O elo l1 inicia a apresentação simultânea dos nós V e AT, fornecendo também a versão do nó
de composição que foi iniciada, especificando (i) que o nó AT deve ser apresentado como um
áudio durante d1 segundos e (ii) que o nó V deve ser apresentado como um vídeo durante d2
segundos.
De maneira similar, o elo l2 especifica que V e A devem começar ao mesmo tempo, além de
fornecer as versões corretas dos nós a ser apresentada (duração de d2 segundos para V, e d5
segundos para A). Este exemplo ilustra como o NCM permite diferentes formas de
apresentação de uma mesma composição, dependendo do contexto externo, ou seja, de como
é feita a navegação até o nó. Assim, pode-se ter a apresentação de C com uma música de
fundo (se a navegação foi feita através do elo l2) ou sem música (se a navegação foi feita
através do elo l1). O link l3 contém uma informação temporal relacionada ao início da
apresentação de AT, impondo que ela deve começar d3 segundos após o início de A. Ele
fornece também a versão do nó a ser executada, o que determinará o descritor a ser utilizado
na apresentação de AT. Este descritor vai definir se AT será apresentado como um áudio (com
duração d1) ou como um texto (com duração d4). O elo l4 especifica que a imagem I deve ser
apresentada logo após o fim de AT e que ela permanece indefinidamente sendo apresentada.
Como consequência, o fim da apresentação de I deve ser definido por uma outra restrição. O
elo l5 tem esta finalidade, determinando que I deve acabar sua apresentação tão logo a
apresentação de V esteja terminada. Considera-se ainda que I tem uma duração mínima de
apresentação d6 . O elo l6 dispara quando I termina.
a2
a1
l1
l2
V
l5
l6
I
A
l3
AT
l4
C
Figura 3 – Parte do documento Carnaval
d2
d2
l1
V
l2
V
d5
d1
A
l5
AT
l4
d6
l6
I
l5
d4
l3
AT
l4
d3
d6
l6
I
Figura 4a – Navegação através do elo l1
Figura 4b – Navegação através do elo l2
d2
d2
V
l2
A
d3
d5
A
l5
d1
l3
V
l2
d5
l3
AT
l4
d3’
I
Figura 5a - Deadlock na apresentação de C causado
por uma inconsistência temporal
l5
d1
AT
l4
d6
I
l6
Figura 5b - Apresentação de C com consistência
temporal mas com inconsistência de plataforma
4.1 – Verificação da Consistência Temporal Intrínseca
A Figura 4a ilustra por meio de linhas de tempo o que acontece quando a navegação é feita
através de l1, assumindo que d 1 + d 6 ≤d 2 . A Figura 4b mostra uma outra possibilidade quando
a navegação é feita através de l2, assumindo que AT é apresentado como texto e que
d 3 + d 4 + d 6 ≤d 2 . Ambos os casos não apresentam inconsistência temporal. Observa-se
também a grande vantagem dos modelos de autoria baseados em eventos, como o caso do
NCM em relação ao tradicional modelo baseado em timelines. Neste exemplo, seriam
necessários duas representações em timeline para modelar o comportamento de um único nó
de composição.
Seja agora, uma navegação através do elo com o nó AT sendo apresentado como áudio e não
como texto e, com d 3 + d 1 > d 2 (Figura 5a). Neste caso, pode-se notar que a apresentação de I
nunca chegará ao fim, porque o nó V acaba antes do início de I. Consequentemente, a
apresentação de C nunca acabará, caracterizando uma indesejável situação de deadlock.
00
11
18
18
11
tt
i(start<C,0>)
i(start<C,0>)
i(user)
i(user)
33
i(trigger<anchor2>)
i(trigger<anchor2>)
16
16
i(start<A,2>)
i(start<A,2>)
i(start<V,0>)
i(start<V,0>)
22
i(user)
i(user)
41
42
41
42
i(start<AT,1>)
i(trigger<anchor1>) i(start<AT,1>)
i(trigger<anchor1>)
i(start<V,0>)
i(start<V,0>)
i(start<V,0>)
i(start<V,0>)
43
43
i(start<V,0>)
i(start<V,0>)
12
12
17
17
39
39
tt
13
13
39
39
39
39
i(start<AT,1>)
i(start<AT,1>)
i(timeout<anchor1>)i(timeout<anchor1>)
i(timeout<anchor1>)
i(timeout<anchor1>)
40
40
38
38
tt
38
38
i(end<V,0>)
i(end<V,0>)
19
19
i(start<AT,1>)
i(start<AT,1>)
10
10
44
tt
14
14
14
14
tt
i(start<I,0>)
i(start<I,0>)
i(endRequest<I,0>)
i(endRequest<I,0>)
11
15
11
15
i(endRequest<V,0>)
i(endRequest<V,0>)
i(end<A,2>)
i(end<A,2>)
37
20
37
20
i(endRequest<A,2>)
i(endRequest<A,2>)
44
i(endRequest<AT,1>)
i(endRequest<AT,1>)
i(end<AT,1>)
i(end<AT,1>)
i(start<A,2>)
i(start<A,2>)
tt
44
44
44
44
tt
i(start<AT,1>)
i(start<AT,1>)
i(timeout<anchor2>)
i(timeout<anchor2>)
i(sync<0,0>)
i(sync<0,0>)
55
15
15
tt
i(end<I,0>)
i(end<I,0>)
66
i(endRequest<C,0>)
i(endRequest<C,0>)
tt
77
21
20
21
20
i(endRequest<V,0>)
i(endRequest<V,0>)
23
22
23
22
i(end<V,0>)
i(sync<0,0>)
i(end<V,0>)
i(sync<0,0>)
i(endRequest<AT,1>)
i(endRequest<AT,1>)
i(endRequest<AT,1>)
i(endRequest<AT,1>)
i(endRequest<AT,1>)
i(endRequest<AT,1>)
i(endRequest<AT,1>)
i(endRequest<AT,1>)
34
34
31
31
i(endRequest<V,0>)
i(endRequest<V,0>)
i(end<AT,1>)
i(end<AT,1>)
35
32
35
32
i(endRequest<V,0>)
i(endRequest<V,0>)
i(start<I,0>)
i(start<I,0>)
i(end<V,0>)
i(end<V,0>)
i(end<AT,1>)
i(end<AT,1>)
i(end<V,0>)
i(end<V,0>)
i(start<I,0>)
i(start<I,0>)
33
36
33
36
i(endRequest<V,0>)
i(endRequest<V,0>)
28
28
i(sync<0,0>)
i(sync<0,0>)
i(end<AT,1>)
i(end<AT,1>)
29
29
i(sync<0,0>)
i(sync<0,0>)
i(start<I,0>)
i(start<I,0>)
30
30
i(end<V,0>)
i(end<V,0>)
24
24
88
i(exit)
i(exit)
99
i(end<AT,1>)
i(end<AT,1>)
25
25
27
27
i(start<I,0>)
i(start<I,0>)
26
26
i(sync<0,0>)
i(sync<0,0>)
i(end<C,0>)
i(end<C,0>)
tt
tt
27
26
27
26
i(endRequest<I,0>)
i(endRequest<I,0>)
Figura 6 – Grafo de alcançabilidade da apresentação de C com deadlock e durações: d1=50,
d2=60, d3=10 e d6=5s.
A situação de deadlock pode ser facilmente identificada através da verificação da
especificação formal RT-LOTOS derivada do modelo NCM da composição C. O grafo de
alcançabilidade2 gerado a partir da ferramenta RTL para esta situação é mostrado na Figura 6.
A transição marcada mostra que apenas a ação temporal t pode ser executada após o estado
27, ou seja, a apresentação de C iniciada por l2 ficará bloqueada indefinidamente na imagem
I, pois a ação end<I,0> nunca será executada. Por outro lado, a parte correspondente a
apresentação de C iniciada pelo elo l1 continua consistente, como era de se esperar [CoOl96].
Vale notar ainda que não fosse especificado um tempo mínimo de apresentação para I, a
composição C seria ainda consistente para as durações utilizadas. Neste caso porém, o nó I
não seria apresentado (ou teria um tempo nulo de execução).
Para tornar a apresentação de C consistente para ambos os casos, pode-se pensar em (i)
aumentar o tempo de apresentação de V (duração d2), (ii) reduzir o tempo de apresentação de
AT (d1) ou (iii) o atraso antes da sua apresentação (d3). Adotando-se a última solução, com
d3’=2s (d3’<< d3), o documento torna-se consistente em relação ao tempo, como mostra a
Figura 5b. Entretanto, como será visto a seguir, ele pode ser inconsistente, dependendo da
plataforma utilizada para sua apresentação.
2 O prefixo i significa que a ação é interna ou não-observável.
4.2 – Verificação da Consistência em Relação à Plataforma de Apresentação
Uma vez verificada a consistência intrínseca do documento, pode-se pensar em verificar se o
documento é ainda consistente, em relação à plataforma na qual ele será apresentado.
A utilização simultânea da tela por diferentes nós de conteúdo do tipo texto ou imagem não
deve causar maiores problemas em relação à consistência global do documento, a não ser a
nível do posicionamento ou área ocupada por uma janela durante a apresentação. Entretanto,
em se tratando dos recursos necessários para a apresentação de vídeos ou áudios, a situação é
bastante diferente. Um canal de áudio por exemplo, ficará alocado por um determinado nó de
conteúdo até que sua apresentação acabe. O mesmo acontece para a apresentação de um
vídeo.
Duas modificações bastante simples na estrutura do processo genérico CompositeNode
permitem analisar a consistência de um documento, de acordo com as características da
plataforma utilizada para sua apresentação. A primeira consiste em adicionar duas portas,
denominadas lock e unlock, na lista de portas dos processos RT-LOTOS ContentNode (e
consequentemente, dos processos CompositeNode que os contêm), para modelar a
sincronização da apresentação de cada nó de conteúdo com cada uma das mídias da
plataforma. A segunda, modifica a condição de terminação de uma composição (processo
terminationNode) de maneira a assegurar que todos os recursos utilizados por ela sejam
liberados antes do seu fim.
Para verificar a consistência intríseca da composição C, descrita na seção 4, foi suposto que
sua apresentação seria realizada em uma plataforma sem restrições de recursos e que tempo
de resposta dos dispositivos seria nulo. Assim, considerou-se que um nó de conteúdo
começaria a ser apresentado imediatamente após suas restrições lógico-temporais serem
satisfeitas e que um número infinito de mídias está a disposição dos nós durante a
apresentação. Apesar de permitir a verificação da consistência intrínseca de documentos, este
cenário não se verifica em aplicações reais, onde, além da limitação natural do número de
recursos, diferentes plataformas vão apresentar dispositivos com diferentes tempos de
resposta. Nesse caso, um documento intrinsicamente consistente em termos lógicos e
temporais pode se tornar inconsistente devido as características da plataforma utilizada.
Para os casos com consistência temporal (Figuras 4a e 4b) descritos anteriormente, pode-se
obter o grafo de alcançabilidade de C sob uma plataforma sem restrições (Figura 7). Verificase que a apresentação de C chegará sempre ao fim para ambos os casos, dado que a ação
end<C,0> é sempre alcançável a partir do início da apresentação [CoOl96]. A ação lock
marca o início da utilização da mídia e a ação unlock, sua liberação. Os parâmetros a, v, i, t
representam as mídias áudio, vídeo, imagem e texto correspondentes aos nós de conteúdo
apresentados.
00
11
i(start<C,0>)
i(start<C,0>)
66
88
i(lock<A,2,a>)
i(lock<A,2,a>)
i(start<V,0>)
i(start<V,0>)
99
i(start<A,2>)
i(start<A,2>)
i(start<V,0>)
i(start<V,0>)
77
i(lock<A,2,a>)
i(lock<A,2,a>)
44
i(user)
i(user)
i(user)
i(user)
i(start<V,0>)
i(start<V,0>)
49
49
i(start<A,2>)
i(start<A,2>)
tt
29
29
i(start<I,0>)
i(start<I,0>)
i(lock<I,0,i>)
i(lock<I,0,i>)
74
74
i(start<I,0>)
i(start<I,0>)
tt
76
77
76
77
i(endRequest<I,0>)
i(endRequest<I,0>)
69
69
i(lock<AT,1,a>)
i(lock<AT,1,a>)
70
69
70
69
i(end<AT,1>) i(endRequest<AT,1>)
i(end<AT,1>)
i(endRequest<AT,1>)
tt
72
72
i(endRequest<V,0>)
i(endRequest<V,0>)
68
68
77
77
i(end<V,0>)
i(end<V,0>)
66
66
i(unlock<V,0,v>)
i(unlock<V,0,v>)
i(sync<0,0>)
i(sync<0,0>)
i(sync<0,0>)
i(sync<0,0>)
67
67
60
60
51
51
i(unlock<V,0,v>)
i(unlock<V,0,v>)
i(end<I,0>)
i(end<I,0>)
i(end<I,0>)
i(end<I,0>)
36
36
36
36
i(unlock<AT,2,t>)
i(unlock<AT,2,t>)
tt
i(endRequest<I,0>)
i(endRequest<I,0>)
i(endRequest<C,0>)
i(endRequest<C,0>)
52
59
63
61
52
59
63
61
65
65
i(unlock<V,0,v>) i(endRequest<C,0>)
i(unlock<V,0,v>)
i(unlock<I,0,i>)
i(unlock<I,0,i>)
i(endRequest<C,0>)
37
37
i(unlock<V,0,v>) i(unlock<V,0,v>)
i(unlock<V,0,v>) i(unlock<I,0,i>)
i(unlock<I,0,i>)
i(unlock<V,0,v>)
tt
54
54
53
53
i(unlock<I,0,i>)
i(unlock<I,0,i>)
i(unlock<V,0,v>)
i(unlock<V,0,v>)
64
64
i(endRequest<C,0>)
i(endRequest<C,0>)
i(unlock<I,0,i>)
i(unlock<I,0,i>)
i(unlock<V,0,v>)
i(unlock<V,0,v>)
i(unlock<V,0,v>)
i(unlock<V,0,v>)
i(exit)
i(exit)
18
18
i(endRequest<C,0>)
i(endRequest<C,0>)
i(exit)
i(exit)
58
58
56
56
i(endRequest<C,0>)
i(endRequest<C,0>)
i(exit)
i(exit)
23
23
55
55
i(exit)
i(exit)
i(unlock<V,0,v>)
i(unlock<V,0,v>)
57
57
13
13
i(end<C,0>)
i(end<C,0>)
i(exit)
i(exit)
16
16
i(unlock<I,0,i>)
i(unlock<I,0,i>)
62
62
i(sync<0,0>)
i(sync<0,0>)
i(unlock<V,0,v>)
i(unlock<V,0,v>)
20
20
i(end<I,0>)
i(end<I,0>)
i(end<I,0>)
i(end<I,0>)
i(unlock<V,0,v>)
i(endRequest<C,0>) i(unlock<I,0,i>)
i(unlock<V,0,v>)
i(endRequest<C,0>)
i(unlock<I,0,i>)
11
19)
21
11
19)
21
25
25
i(endRequest<C,0>)
i(endRequest<C,0>)
i(unlock<I,0,i>)
i(unlock<I,0,i>)
i(unlock<V,0,v>)
i(unlock<V,0,v>)
i(unlock<I,0,i>)
i(unlock<I,0,i>)
i(unlock<I,0,i>)
i(unlock<I,0,i>)
12
12
24
22
24
22
i(unlock<I,0,i>)
i(unlock<I,0,i>)
i(endRequest<C,0>)
i(endRequest<C,0>)
i(unlock<V,0,v>)
i(unlock<V,0,v>)
17
17
50
50
i(lock<I,0,i>)
i(lock<I,0,i>)
28
37
28
37
i(endRequest<V,0>)
i(endRequest<V,0>)
i(end<V,0>)
i(end<V,0>)
i(unlock<V,0,v>)
i(unlock<V,0,v>)
27
26
27
26
10
10
71
71
i(lock<I,0,i>)
i(lock<I,0,i>)
76
76
32
32
i(unlock<AT,2,t>)
i(unlock<AT,2,t>)
i(start<I,0>)
i(start<I,0>)
i(start<I,0>)
i(start<I,0>)
33
34
33
34
i(unlock<AT,2,t>)
i(unlock<AT,2,t>)
i(sync<0,0>)
i(sync<0,0>)
79
79
i(lock<AT,1,a>)
i(lock<AT,1,a>)
i(start<V,0>)
i(start<V,0>)
i(start<V,0>)
i(start<V,0>)
i(unlock<AT,1,a>) i(unlock<AT,1,a>)
i(unlock<AT,1,a>)
i(unlock<AT,1,a>) i(unlock<AT,1,a>)
i(unlock<AT,1,a>)
38
39
38
39
i(unlock<A,2,a>) i(end<A,2>)
i(end<A,2>)
i(unlock<A,2,a>)
i(lock<I,0,i>)
i(lock<I,0,i>)
46
46
tt
73
73
75
75
i(endRequest<AT,2>)
i(endRequest<AT,2>)
30
30
31
31
i(end<AT,2>)
i(end<AT,2>)
35
35
i(start<AT,1>)
i(start<AT,1>)
i(lock<V,0,v>)
i(lock<V,0,v>)
41
42
42
41
42
42
i(start<AT,2>)
i(lock<AT,2,t>)
tt
i(lock<AT,2,t>)
i(start<AT,2>)
i(endRequest<A,2>)
i(endRequest<A,2>)
29
29
i(start<AT,1>)
i(start<AT,1>)
i(start<V,0>)
i(start<V,0>)
47
48
78
47
48
78
i(start<AT,1>)
i(start<AT,1>)
i(lock<AT,1,a>)
i(lock<AT,1,a>)
i(lock<V,0,v>)
i(lock<V,0,v>)
i(lock<V,0,v>)
i(lock<V,0,v>)
i(lock<V,0,v>)
i(lock<V,0,v>)
tt
40
40
45
45
i(trigger<anchor1>)
i(trigger<anchor1>)
33
i(trigger<anchor2>)
i(trigger<anchor2>)
43
44
43
44
i(lock<A,2,a>)
i(start<A,2>)
i(lock<A,2,a>)
i(start<A,2>)
40
40
22
55
i(lock<V,0,v>)
i(lock<V,0,v>)
i(lock<V,0,v>)
i(lock<V,0,v>)
11
tt
i(exit)
i(exit)
14
14
i(end<C,0>)
i(end<C,0>)
15
15
i(exit)
i(exit)
00
Figura 7 – Grafo de alcançabilidade de C sob uma plataforma sem limitação de recursos.
Seja a apresentação do mesmo trecho do documento Carnaval anterior, mas sob uma
plataforma P contando apenas com um canal de áudio, uma placa de descompressão de vídeo,
além de obviamente, um monitor. Fazendo uma nova verificação do documento C sob a
plataforma proposta, observa-se que sua apresentação iniciada através do elo l2 ocasionará
uma situação de deadlock, dependendo dos valores d5 e d4. Isto se deve ao conflito na
utilização do canal de áudio causado pela tentativa apresentação simultânea dos nós A e AT,
conforme mostra o resultado da simulação da Figura 8. Note que o recurso áudio está ocupado
com a apresentação do nó A quando o nó AT começa a ser apresentado. A ação seguinte,
nesse caso, corresponderia a atribuição do recurso a AT, mas como isso não é possível, a
apresentação de AT ficará bloqueada à espera do recurso áudio e a apresentação de C não
chegará ao fim. Mais ainda, pelos valores definidos para d2, d3 e d1, o documento seria
consistente do ponto de vista temporal, pois d 3 + d 4 + d 6 ≤d 2 (Figura 5b). Entretando, pode-se
verificar que ele é inconsistente em relação a sua plataforma de apresentação.
00
11
i(start<C,0>)
i(start<C,0>)
i(start<V,0>)
i(start<V,0>) i(lock<A,2,a>)
i(lock<A,2,a>) i(start<A,2>)
i(start<A,2>)
88
66
44
99
11
tt
22
i(user)
i(user)
i(user)
i(user)
25
25
58
58
24
24
i(trigger<anchor1>)
i(trigger<anchor1>)
i(lock<AT,1,a>)
i(start<AT,1>)
i(start<AT,1>) i(lock<AT,1,a>)
i(start<V,0>)
i(start<V,0>)
i(start<V,0>)
i(start<V,0>)
i(start<V,0>)
i(start<V,0>)
26
26
57
57
27
27
i(start<AT,1>)
i(start<AT,1>) i(lock<AT,1,a>)
i(lock<AT,1,a>)
i(lock<V,0,v>)
i(lock<V,0,v>) i(lock<V,0,v>)
i(lock<V,0,v>) i(lock<V,0,v>)
i(lock<V,0,v>)
33
i(trigger<anchor2>)
i(trigger<anchor2>)
i(start<V,0>)
i(start<V,0>)
i(start<V,0>)
i(start<V,0>)
i(lock<V,0,v>)
i(lock<V,0,v>)
i(start<A,2>)
i(lock<A,2,a>)
i(lock<A,2,a>) i(start<A,2>)
20
20
77
99
55
tt
20
20
tt
20
20
tt
i(end<AT,1>)
i(start<I,0>)
i(start<I,0>) i(end<AT,1>)
i(lock<I,0,i>)
i(lock<I,0,i>)
50
50
49
49
48
48
52
52
i(endRequest<AT,1>)
i(endRequest<AT,1>)
i(unlock<AT,1,a>)
i(unlock<AT,1,a>) i(unlock<AT,1,a>)
i(unlock<AT,1,a>) i(unlock<AT,1,a>)
i(unlock<AT,1,a>)
i(lock<V,0,v>)
i(lock<V,0,v>) i(lock<V,0,v>)
i(lock<V,0,v>)
i(lock<V,0,v>)
i(lock<V,0,v>)
23
23
i(start<A,2>)
i(start<A,2>)
22
22
i(lock<A,2,a>)
i(lock<A,2,a>)
i(start<AT,1>)
i(start<AT,1>)
54
54
55
55
56
56
tt
11
11
19
19
i(endRequest<A,2>)
i(endRequest<A,2>)
10
10
i(endRequest<V,0>)
i(endRequest<V,0>)
tt
tt
55
55
53
53
51
51
i(lock<I,0,i>)
i(lock<I,0,i>) i(start<I,0>)
i(start<I,0>)
i(endRequest<V,0>)
i(endRequest<V,0>)
56
56
47
47
45
45
46
46
i(end<V,0>)
i(end<V,0>)
i(unlock<V,0,v>)
i(unlock<V,0,v>)
i(sync<0,0>)
i(sync<0,0>)
i(sync<0,0>)
i(sync<0,0>)
i(endRequest<C,0>)
i(endRequest<C,0>)
18
18
40
40
39
39
32
32
44
44
30
30
i(unlock<V,0,v>)
i(unlock<V,0,v>)
i(unlock<V,0,v>)
i(unlock<V,0,v>)
i(end<I,0>)
i(end<I,0>)
i(unlock<A,2,a>)
i(unlock<A,2,a>)
i(unlock<V,0,v>) i(end<I,0>)
i(unlock<I,0,i>) i(unlock<V,0,v>)
i(unlock<I,0,i>)
i(unlock<I,0,i>)
i(unlock<I,0,i>)
i(unlock<I,0,i>) i(unlock<I,0,i>)
i(end<I,0>)
10
10
i(unlock<V,0,v>)
i(unlock<V,0,v>)
33
33
42
42
41
41
31
31
35
35
i(unlock<V,0,v>)
i(unlock<V,0,v>)
i(unlock<I,0,i>)
i(unlock<I,0,i>)
i(end<A,2>)
i(end<A,2>)
i(end<V,0>)
i(end<V,0>)
12
12
tt
i(endRequest<I,0>)
i(endRequest<I,0>)
21
21
21
21
48
48
28
28
29
29
i(start<AT,1>)
i(start<AT,1>) i(lock<AT,1,a>)
i(lock<AT,1,a>)
i(endRequest<C,0>)
i(endRequest<C,0>)
i(endRequest<C,0>) i(endRequest<C,0>)
17
17
i(unlock<V,0,v>)
i(unlock<V,0,v>)
i(sync<0,0>)
i(sync<0,0>)
i(unlock<V,0,v>)
i(unlock<V,0,v>)
43
43
16
16
i(exit)
i(exit)
i(end<C,0>)
i(end<C,0>)
15
15
34
34
i(endRequest<C,0>)
i(endRequest<C,0>)
i(unlock<V,0,v>)
i(unlock<V,0,v>)
i(exit)
i(exit)
14
14
13
13
37
37
i(exit)
i(exit)
i(sync<0,0>)
i(sync<0,0>)
i(exit)
i(exit)
36
36
i(unlock<I,0,i>)
i(unlock<I,0,i>)
38
38
Figura 8 – Grafo de alcançabilidade de C sob a plataforma P com restrição de recursos e
parâmetros: d2=60s, d5=25s, d3=2s, d6=3s e d1=45 s.
5. Conclusões
O trabalho propõe um modelo formal que permite organizar de maneira hierárquica, simular o
comportamento e verificar a consistência lógico-temporal intrínseca de um documento. Uma
extensão ao modelo básico permitiu ainda verificar consistência dos documentos em relação à
plataforma de apresentação. Tal análise permitiu verificar, por exemplo, a existência ou não
de super-posições de imagens, se a plataforma disponível suporta o documento a ser
apresentado, ou se existe conflito na utilização de recursos durante uma apresentação.
Embora os resultados obtidos sejam simples, deve-se notar que a mesma metodologia pode
ser utilizada para análises detalhadas de apresentações sobre modelos complexos de
plataforma, sem que seja necessário alterar a especificação que modela a estrutura o
documento. Isto ocorre porque os processos correspondentes à plataforma e ao documento só
se relacionam através da sincronização sobre as portas lock e unlock.
Outro contribuição importante é a construção de uma biblioteca de processos básicos link,
contentNode e anchor para facilitar a aplicação da metodologia de maneira sistemática,
qualquer que seja o documento hipermídia a ser analisado.
Entre as perspectivas para trabalhos futuros, está sendo estudado o aumento da complexidade
da plataforma, buscando reproduzir um modelo com um comportamento o mais próximo
possível de dispositivos reais. Outro ponto de interesse é a utilização da mesma metodologia
sobre outros modelos conceituais de autoria, além do próprio NCM.
6. Referências
[BlSt96] Blakowski, G.; Steinmetz, R. “A Media Synchronization Survey: Reference Model,
Specification and Case Studies”. IEEE Journal on Selected Areas in
Communication. v.14, n.1, Jan. 1996.
[BoBr87] Bolognesi, T.; Brinksma, E. Introduction to the ISO Specification Language
LOTOS. Computer Networks and ISDN Systems, v.14, n.1, 1987.
[BuZe93] Buchanan, M.C.; Zellweger, P.T. Automatic Temporal Layout Mechanisms. In:
Proceedings of ACM Multimedia’93. California, 1993. pp. 341-50.
[CoOl94] Courtiat, J.-P.; De Oliveira, R.C. About Time non-determinism and Exception
Handling in a Temporal Extension of LOTOS. In: Protocol Specification, Testing
and Verification XIV, Vancouver, Canada, Jun. 1994. Chapman & Hall.
[CoOl95] Courtiat, J.-P.; De Oliveira, R.C. A Reachability Analysis of RT-LOTOS
Specifications. In: Proceedings of the 8th Int. Conf. on Formal Description
Techniques. Montreal, Canada, Oct. 1995. Chapman & Hall.
[CoOl96] Courtiat, J.-P.; De Oliveira, R.C. Proving Temporal Consistency in a New
Multimedia Synchronization Model. In: Proceedings of ACM Multimedia’96. 1996.
[LiGh90] Little, T.D.C.; Ghafoor, A. Synchronization and Storage Models for Multimedia
Objects. IEEE Journal on Selected Areas in Communications, v.8, n.3, Apr. 1990.
pp.413-27.
[SCSS97] Souza Filho, G.L; Courtiat, J-P; Santos, C.A.S.; Soares, L.F.G. Usando RTLOTOS para Verificar a Consistência de Documentos Multimídia em Plataformas
Configuráveis. II Seminário Franco-Brasileiro em Sistemas Informáticos
Distribuídos. Anais. Fortaleza - CE. Nov. 1997.
[SDLS96]Sénac, P.; Diaz, M.; Leger, A.; Saqui-Sannes, P. Modeling Logical and Temporal
Synchronization in Hypermedia Systems. IEEE Journal on Selected Areas in
Communication. v.14, n.1, Jan. 1996.
[SoCa95] Soares, L.F.G.; Casanova, M.A.; Rodriguez, N.L.R.. Nested Composite Nodes and
Version Control in an Open Hypermedia System. International Journal on
Information Systems; Special Issue on Multimedia Information Systems, Sep. 1995.
pp. 501-19.
[SoSo96] Soares, L.F.G.; Souza, G.L. Sistema HyperProp: Modelo Conceitual. Relatório
Técnico do Labóratorio TeleMídia do Dep. de Informática, PUC-Rio. Rio de
Janeiro. Nov. 1996.
[WaRo94]Wahl, T.; Rothermel, K. Representing Time in Multimedia Systems. In: Proc.
IEEE Int. Conf. on Multimedia Computing and Systems, Boston. May 1994. pp.
538-43.
[WiSS97] Willrich, R.; Sénac, P.; Saqui-Sannes, P.; Diaz, M.; Hypermedia Documents
Design Using the HTSPN Model. 3rd Int. Conf. on MultiMedia Modeling MMM’96. Toulouse, Nov. 1996. pp.151-66.