High-integrity networking

High-integrity networking

[Maciej Sobczak]

Hi,

Ravenscar describes the language subset and the usage patterns for
multitasking within a single process.
I'm interested in patterns and solutions for high-reliability
networking/middleware.

Just "extrapolating" Ravenscar to the distributed environment can lead
to some imaginably constrained environment where the set of
communicating nodes is constant, the number and configuration of
channels is statically known, the types (and lengths) of messages are
known up front, etc.
There are some start-up issues with ensuring all these constraints
(for example, the locations of other nodes would need to be first read
from some configuration file/database before the connections can be
established, etc., so that the initialization phase would need to be
more pronounced than just stating that something happens at the
package elaboration), but it seems feasible.

Can you recommend some papers on this? Is there any document of the
Ravenscar profile kind that targets high-integrity networking and
middleware approaches?

--
Maciej Sobczak * www.msobczak.com * www.inspirel.com

Re: High-integrity networking

[Colin Paul Gloster]

On Mon, 8 Oct 2007, Maciej Sobczak wrote:

|----------------------------------------------------------------------|
|"Ravenscar describes the language subset and the usage patterns for   |
|multitasking within a single process."                                |
|----------------------------------------------------------------------|

RAVENSCAR is not about patterns. I do not believe that even Tullio
Vardanega claimed that in his paper "Ravenscar design patterns?:
reflections on use of the Ravenscar profile".

A RAVENSCAR task is a process. Multiple threads inside one process are
not possible in RAVENSCAR.

|----------------------------------------------------------------------|
|"I'm interested in patterns and solutions for high-reliability        |
|networking/middleware.                                                |
|                                                                      |
|Just "extrapolating" Ravenscar to the distributed environment can lead|
|to some imaginably constrained environment where [..]                 |
|[..], the types (and lengths) of messages are                         |
|known up front, etc.                                                  |
|There are some start-up issues with ensuring all these constraints    |
|(for example, the locations of other nodes would need to be first read|
|from some configuration file/database before the connections can be   |
|established, etc., [..]                                               |
|                                                                      |
|[..]"                                                                 |
|----------------------------------------------------------------------|

RAVENSCAR is not intrinsically specific to the packet-switching
paradigm.

Regards,
Colin Paul Gloster

Re: High-integrity networking

[Maciej Sobczak]

On 8 Pa , 18:03, Colin Paul Gloster <Colin_Paul_Glos...@ACM.org>
wrote:

> |----------------------------------------------------------------------|
> |"Ravenscar describes the language subset and the usage patterns for   |
> |multitasking within a single process."                                |
> |----------------------------------------------------------------------|
>
> RAVENSCAR is not about patterns. I do not believe that even Tullio
> Vardanega claimed that in his paper "Ravenscar design patterns?:
> reflections on use of the Ravenscar profile".

I didn't mean "design patterns", but "usage patterns" in the sense
that some things are discouraged/forbidden and some others are
promoted/enforced.

> A RAVENSCAR task is a process. Multiple threads inside one process are
> not possible in RAVENSCAR.

Could you please throw some references? A relevant citation from the
Ravescar document itself would be perfect.

I have found *one* paragraph indicating that tasks are single-threaded
and *many* paragraphs about shared variables, global data, and so on.

As far as I'm concerned it does not really matter how the program is
deployed on the given system - and if it's deployed on bare metal (no
OS underneath), then the distinction between processes and threads
does not make any sense anyway.

The only thing I find important is that the complete Ravenscar
program, comprising potentially many tasks, is a *single entity* from
the deployment point of view - whatever that means on the given target
platform.

But I'm not asking about Ravenscar.

> |----------------------------------------------------------------------|
> |"I'm interested in patterns and solutions for high-reliability        |
> |networking/middleware.                                                |
> |                                                                      |
> |Just "extrapolating" Ravenscar to the distributed environment can lead|
> |to some imaginably constrained environment where [..]                 |
> |[..], the types (and lengths) of messages are                         |
> |known up front, etc.                                                  |
> |There are some start-up issues with ensuring all these constraints    |
> |(for example, the locations of other nodes would need to be first read|
> |from some configuration file/database before the connections can be   |
> |established, etc., [..]                                               |
> |                                                                      |
> |[..]"                                                                 |
> |----------------------------------------------------------------------|
>
> RAVENSCAR is not intrinsically specific to the packet-switching
> paradigm.

I'm not asking about Ravenscar. I'm asking about recommended reading
in the area of high-integrity networking and middleware. I have
mentioned Ravenscar to give you a hint on what is the kind of document
that could be the closest analogy to what I'm looking for.

Any recommendations?

--
Maciej Sobczak * www.msobczak.com * www.inspirel.com

Re: High-integrity networking

[Jeffrey R. Carter]

Maciej Sobczak wrote:
> 
> Ravenscar describes the language subset and the usage patterns for
> multitasking within a single process.
> I'm interested in patterns and solutions for high-reliability
> networking/middleware.

Ravenscar describes the language subset for a single Ada program. An Ada 
program may consist of multiple partitions, and different partitions may 
run on different computers. Unless I've missed something, Ravenscar is 
fine for distributed programs using Annex E.

-- 
Jeff Carter
"My mind is a raging torrent, flooded with rivulets of
thought, cascading into a waterfall of creative alternatives."
Blazing Saddles
89

Re: High-integrity networking

[Maciej Sobczak]

On 8 Pa , 23:02, "Jeffrey R. Carter"
<spam.jrcarter....@acm.nospam.org> wrote:

> Ravenscar describes the language subset for a single Ada program. An Ada
> program may consist of multiple partitions, and different partitions may
> run on different computers. Unless I've missed something, Ravenscar is
> fine for distributed programs using Annex E.

I understand this, but this approach has some limitations for me.
First of all, it limits the scope of discussion to Ada only, and every
non-trivial distributed system I have seen so far is heterogenous in
the sense of technology coverage.
I would like to understand the issues in such systems to get a better
view on the architectural and functional aspects of communication that
promotes verification and analysis of the whole. As I've already
pointed, I understand that Ravenscar can be used as a "mental
template" that can be extrapolated to distributed systems. This is
perfectly fine. Still, if there is anything that is particularly worth
reading *in addition*, I'm looking forward to get some pointers.

I have already found CSP (Communicating Sequential Processes), which
is one possible approach, although what I have seen up to now leaves
some "minor" details in the air, like the startup of the whole system.
Ravenscar can afford this, because it's the language implementation
that has to more or less transparently take care of all these issues,
but heterogenous systems might need some more explicit handling.

In any case - is this (CSP) the only keyword in this subject?

--
Maciej Sobczak * www.msobczak.com * www.inspirel.com

Re: High-integrity networking

[Jeffrey R. Carter]

Maciej Sobczak wrote:
> 
> I understand this, but this approach has some limitations for me.
> First of all, it limits the scope of discussion to Ada only, and every
> non-trivial distributed system I have seen so far is heterogenous in
> the sense of technology coverage.
> I would like to understand the issues in such systems to get a better
> view on the architectural and functional aspects of communication that
> promotes verification and analysis of the whole. As I've already
> pointed, I understand that Ravenscar can be used as a "mental
> template" that can be extrapolated to distributed systems. This is
> perfectly fine. Still, if there is anything that is particularly worth
> reading *in addition*, I'm looking forward to get some pointers.

Ravenscar is also Ada only, so you can't really talk about it in a 
heterogeneous system. I take it you're trying to apply the spirit of 
Ravenscar to heterogeneous distributed systems, but you're pretty much 
on your own there. I'd probably design such a system as a 
distributed/Annex-E Ravenscar system, then try to ensure that the 
non-Ada parts are equivalent to what an Ada implementation would be, and 
that all communications are equivalent to what would take place in a 
fully Annex-E implementation.

> I have already found CSP (Communicating Sequential Processes), which
> is one possible approach, although what I have seen up to now leaves
> some "minor" details in the air, like the startup of the whole system.
> Ravenscar can afford this, because it's the language implementation
> that has to more or less transparently take care of all these issues,
> but heterogenous systems might need some more explicit handling.

CSP was the basic model for Ada-83 tasking: tasks with entries calling 
each other. That scales nicely to one task per computer.

-- 
Jeff Carter
"You cheesy lot of second-hand electric donkey-bottom biters."
Monty Python & the Holy Grail
14

Re: High-integrity networking

[Maciej Sobczak]

On 9 Pa , 19:37, "Jeffrey R. Carter"
<spam.jrcarter....@acm.nospam.org> wrote:

> I'd probably design such a system as a
> distributed/Annex-E Ravenscar system, then try to ensure that the
> non-Ada parts are equivalent to what an Ada implementation would be, and
> that all communications are equivalent to what would take place in a
> fully Annex-E implementation.
>
> > I have already found CSP (Communicating Sequential Processes), which
> > is one possible approach, although what I have seen up to now leaves
> > some "minor" details in the air, like the startup of the whole system.
> > Ravenscar can afford this, because it's the language implementation
> > that has to more or less transparently take care of all these issues,
> > but heterogenous systems might need some more explicit handling.

Which is, basically, what I imagined at the beginning - but I have an
impression that some of the details might need to be more pronounced
in the explicitly distributed system. I will repeat the startup issue
with its inherent timing/ordering problems.

I can also imagine supporting this process (especially the last part
of your sentence above) with some model-driven generation of skeletons
for different nodes.

MDD with Ada/Ravenscar as a DSL for modeling communication patterns?
Sounds like a nice subject for a paper. :-)

--
Maciej Sobczak * www.msobczak.com * www.inspirel.com

Re: High-integrity networking

[Peter Morris]

On Mon, 08 Oct 2007 05:13:43 -0700, Maciej Sobczak
<see.my.homepage@gmail.com> wrote:

>Hi,
>
>Ravenscar describes the language subset and the usage patterns for
>multitasking within a single process.
>I'm interested in patterns and solutions for high-reliability
>networking/middleware.
>
>Just "extrapolating" Ravenscar to the distributed environment can lead
>to some imaginably constrained environment where the set of
>communicating nodes is constant, the number and configuration of
>channels is statically known, the types (and lengths) of messages are
>known up front, etc.
>There are some start-up issues with ensuring all these constraints
>(for example, the locations of other nodes would need to be first read
>from some configuration file/database before the connections can be
>established, etc., so that the initialization phase would need to be
>more pronounced than just stating that something happens at the
>package elaboration), but it seems feasible.
>
>Can you recommend some papers on this? Is there any document of the
>Ravenscar profile kind that targets high-integrity networking and
>middleware approaches?

I came across this paper:

Issues with using Ravenscar and the Ada Distributed Systems Annex for
High-Integrity Systems
http://www.acm.org/sigada/ada_letters/march2001/103-audsley_1.pdf

It identified the following problem:

"It is clear that in order to facilitate distributed
high-integrity real-time programming, the run-time
support for distributed programming itself should conform
to the Ravenscar profile. We have illustrated in this paper
that this support requires greater expressive power than that
afforded by Ravenscar. The result is greater complexity in
the run-time � the code is almost certainly less analyzable,
and definitely harder to produce and read."

I don't know if anyone has solved this problem.

However I  know it is possible implement CSP channels in Ravenscar for
multi-tasking programs running on a single processor.
http://www.springerlink.com/content/j7h8rr665r0x20n9/

So it might be possible to also implement CSP channels in Ravenscar
for communication between different processors.  

Eg suppose a serial link between two processors was managed at one end
by a task that relayed data to the link from a CSP channel and at the
other by a task that relayed data from the link to a CSP channel. 

Then distributed application tasks could communicate entirely via CSP
channels.

That might make the code easier to read and analyse.

Regards,
Peter Morris

Re: High-integrity networking

[Brian Drummond]

On Tue, 09 Oct 2007 06:17:33 -0700, Maciej Sobczak
<see.my.homepage@gmail.com> wrote:

>On 8 Pa , 23:02, "Jeffrey R. Carter"
><spam.jrcarter....@acm.nospam.org> wrote:
>

>I have already found CSP (Communicating Sequential Processes), which
>is one possible approach, although what I have seen up to now leaves
>some "minor" details in the air, like the startup of the whole system.
>Ravenscar can afford this, because it's the language implementation
>that has to more or less transparently take care of all these issues,
>but heterogenous systems might need some more explicit handling.
>
>In any case - is this (CSP) the only keyword in this subject?

I don't suppose there are any occam compilers still running?

- Brian

Re: High-integrity networking

[anon]

The orginal OCCAM language was designed for "transputers". 

Now for links try: Occam-pi and KRoC 

   http://www.occam-pi.org/  -- info and links 

   http://www.cs.kent.ac.uk/projects/ofa/kroc/   -- uses GPL. LGPL

   http://www.transterpreter.org/  -- occam virtual machine


In <i3kpg35i0p81nkjo4ifo6448otdnmcb56o@4ax.com>, Brian Drummond <brian_drummond@btconnect.com> writes:
>On Tue, 09 Oct 2007 06:17:33 -0700, Maciej Sobczak
><see.my.homepage@gmail.com> wrote:
>
>>On 8 Pa , 23:02, "Jeffrey R. Carter"
>><spam.jrcarter....@acm.nospam.org> wrote:
>>
>
>>I have already found CSP (Communicating Sequential Processes), which
>>is one possible approach, although what I have seen up to now leaves
>>some "minor" details in the air, like the startup of the whole system.
>>Ravenscar can afford this, because it's the language implementation
>>that has to more or less transparently take care of all these issues,
>>but heterogenous systems might need some more explicit handling.
>>
>>In any case - is this (CSP) the only keyword in this subject?
>
>I don't suppose there are any occam compilers still running?
>
>- Brian

Re: High-integrity networking

[Peter Morris]

On Wed, 10 Oct 2007 14:16:11 +0100, Brian Drummond
<brian_drummond@btconnect.com> wrote:

>On Tue, 09 Oct 2007 06:17:33 -0700, Maciej Sobczak
><see.my.homepage@gmail.com> wrote:
>
>>On 8 Pa , 23:02, "Jeffrey R. Carter"
>><spam.jrcarter....@acm.nospam.org> wrote:
>>
>
>>I have already found CSP (Communicating Sequential Processes), which
>>is one possible approach, although what I have seen up to now leaves
>>some "minor" details in the air, like the startup of the whole system.
>>Ravenscar can afford this, because it's the language implementation
>>that has to more or less transparently take care of all these issues,
>>but heterogenous systems might need some more explicit handling.
>>
>>In any case - is this (CSP) the only keyword in this subject?
>
>I don't suppose there are any occam compilers still running?
>

The Kent Retargetable Occam Compiler now compiles an extended version
of occam (occam-pi)
http://www.cs.kent.ac.uk/projects/ofa/kroc/

There is a portable runtime here with support for the Lego Mindstorm
http://www.transterpreter.org/

SPOC occam to C compiler
http://www.itk.ntnu.no/ansatte/Hendseth_Sverre/occam/index.html

A support group for the CSP model of parallel processing.
http://www.wotug.org

Proceedings of a recent conference.
http://wotug.org/paperdb/show_proc.php?f=4&num=25


Regards,
Peter Morris

Re: High-integrity networking

[Simon Wright]

Peter Morris <no@spam.please.net> writes:

> Issues with using Ravenscar and the Ada Distributed Systems Annex for
> High-Integrity Systems
> http://www.acm.org/sigada/ada_letters/march2001/103-audsley_1.pdf
>
> It identified the following problem:
>
> "It is clear that in order to facilitate distributed
> high-integrity real-time programming, the run-time
> support for distributed programming itself should conform
> to the Ravenscar profile. We have illustrated in this paper
> that this support requires greater expressive power than that
> afforded by Ravenscar. The result is greater complexity in
> the run-time – the code is almost certainly less analyzable,
> and definitely harder to produce and read."

Not clear from the last sentence whether it's the run-time or the user
code that's harder to analyse, produce or read. (Presumably that's not
true of Ravenscar itself, or no one would use it? It would be a hard
sell to management ...)

> I don't know if anyone has solved this problem.

Could a solution be analogous to the SPARK technique of telling the
Analyser that certain elements can be assumed to behave as specified
without needing proof? Could a multi-partition program use different
profiles for different parts?

Of course, that depends on what problem you are trying to solve; using
Ravenscar makes it easier to argue for correctness, not using
Ravenscar probably doesn't make an argiment impossible.

Re: High-integrity networking

[Peter Morris]

On Wed, 10 Oct 2007 20:40:17 +0100, Simon Wright
<simon.j.wright@mac.com> wrote:

>Peter Morris <no@spam.please.net> writes:
>
>> Issues with using Ravenscar and the Ada Distributed Systems Annex for
>> High-Integrity Systems
>> http://www.acm.org/sigada/ada_letters/march2001/103-audsley_1.pdf
>>
>> It identified the following problem:
>>
>> "It is clear that in order to facilitate distributed
>> high-integrity real-time programming, the run-time
>> support for distributed programming itself should conform
>> to the Ravenscar profile. We have illustrated in this paper
>> that this support requires greater expressive power than that
>> afforded by Ravenscar. The result is greater complexity in
>> the run-time � the code is almost certainly less analyzable,
>> and definitely harder to produce and read."
>
>Not clear from the last sentence whether it's the run-time or the user
>code that's harder to analyse, produce or read. (Presumably that's not
>true of Ravenscar itself, or no one would use it? It would be a hard
>sell to management ...)
>
I think they are referring to implementations of the DSA. Eg they say
that the GLADE implementation uses many protected objects that don't
comply with Ravenscar requirements.  

>> I don't know if anyone has solved this problem.
>
>Could a solution be analogous to the SPARK technique of telling the
>Analyser that certain elements can be assumed to behave as specified
>without needing proof? 
>
That should be possible. Eg if an implementation of the DSA had passed
sufficiently rigorous tests.

However I feel there is room for something simpler than the DSA.

>
>Of course, that depends on what problem you are trying to solve; using
>Ravenscar makes it easier to argue for correctness, not using
>Ravenscar probably doesn't make an argiment impossible.
>
I think that is true.


Regards,
Peter Morris

Re: High-integrity networking

[Colin Paul Gloster]

Hello,

On Mon, 8 Oct 2007, Maciej Sobczak wrote:

|--------------------------------------------------------------------------|
|"On 8 Pa , 18:03, Colin Paul Gloster <Colin_Paul_Glos...@ACM.org>         |
|wrote:                                                                    |
|                                                                          |
|[..]                                                                      |
|                                                                          |
|I didn't mean "design patterns", but "usage patterns" in the sense        |
|that some things are discouraged/forbidden and some others are            |
|promoted/enforced."                                                       |
|--------------------------------------------------------------------------|

Okay.

|--------------------------------------------------------------------------|
|"> A RAVENSCAR task is a process. Multiple threads inside one process are |
|> not possible in RAVENSCAR.                                              |
|                                                                          |
|Could you please throw some references? A relevant citation from the      |
|Ravescar document itself would be perfect."                               |
|--------------------------------------------------------------------------|

It is quite clear from using the index of
Alan Burns and Andy Wellings, "Real-Time Systems and Programming
Languages: Ada 95, Real-Time Java and Real-Time POSIX", third edition
(of the main title, not of the subtitle), 2001, reprint with
corrections that they consider a process to be represented in Ada (and
therefore RAVENSCAR) by a task. (It is not so quick to plainly find
in that book that they consider threads to be different from
processes, but it is what they describe elsewhere in the book.)

|--------------------------------------------------------------------------|
|"I have found *one* paragraph indicating that tasks are single-threaded   |
|and *many* paragraphs about shared variables, global data, and so on."    |
|--------------------------------------------------------------------------|

I do not typically recommend using shared variables nor global data.

|--------------------------------------------------------------------------|
|"As far as I'm concerned it does not really matter how the program is     |
|deployed on the given system - and if it's deployed on bare metal (no     |
|OS underneath), then the distinction between processes and threads        |
|does not make any sense anyway."                                          |
|--------------------------------------------------------------------------|

I disagree.

|--------------------------------------------------------------------------|
|"[..]                                                                     |
|                                                                          |
|> |----------------------------------------------------------------------||
|> |"I'm interested in patterns and solutions for high-reliability        ||
|> |networking/middleware.                                                ||
|> |                                                                      ||
|> |Just "extrapolating" Ravenscar to the distributed environment can lead||
|> |to some imaginably constrained environment where [..]                 ||
|> |[..], the types (and lengths) of messages are                         ||
|> |known up front, etc.                                                  ||
|> |There are some start-up issues with ensuring all these constraints    ||
|> |(for example, the locations of other nodes would need to be first read||
|> |from some configuration file/database before the connections can be   ||
|> |established, etc., [..]                                               ||
|> |                                                                      ||
|> |[..]"                                                                 ||
|> |----------------------------------------------------------------------||
|>                                                                         |
|> RAVENSCAR is not intrinsically specific to the packet-switching         |
|> paradigm.                                                               |
|                                                                          |
|I'm not asking about Ravenscar. I'm asking about recommended reading      |
|in the area of high-integrity networking and middleware. I have           |
|mentioned Ravenscar to give you a hint on what is the kind of document    |
|that could be the closest analogy to what I'm looking for.                |
|                                                                          |
|Any recommendations?"                                                     |
|--------------------------------------------------------------------------|

I had understood that your request was not specific to
RAVENSCAR. Packet-switching is not the only choice for high-integrity
networking. Many different requirements may be imposed on what you
consider to be important for the integrity of a particular network
deployment. E.g. instead of following the mainstream trend of reducing
power consumption, you may deem it to be acceptable to have high voltage
differences such that one of two binary digital values is less likely
to be misinterpreted as the other value. If timing is not crucial,
people do use schemes such as retransmission on wireless networks if
low power is necessary. Of course, reception of the intended value can
never be guaranteed.

In Marescaux; Corporaal, ``Introducing the SuperGT Network-on-Chip ---
SuperGT QoS: more than just GT'', Design Automation Conference it is
argued that delivering packets out of order
is undesirable for an on-chip network. I am not convinced that
this is universally true (it depends on the application, e.g. many
off-chip networks allow delivering packets out of order (e.g. the
Internet (see Page 536 of Andrew S. Tanenbaum, "Computer Networks",
international third edition, Prentice Hall, 1996) and the European
Space Agency's Packet Utilization Standard (European Space Agency,
"Packet Utilisation Standard", ESA
standard PSS-07-101, 1994,
HTTP://WWW.ESA.int/esapub/pss/ecss_web.pdf
and
European Cooperation for Space Standardization, "Ground systems and
operations --- Telemetry and telecommand packet utilization", ECSS
standard E-70-41A, 2003,
HTTP://WWW.ECSS.NL/forums/ecss/dispatch.cgi/standards/docProfile/100204/d20040512075344/No/t100204.htm
))). For designs in which out of order delivery is unacceptable, a
more robust architecture is a circuit-switched architecture as this
can never
happen (see Page 133 of the aforementioned book by Tanenbaum). Other
advantages of circuit-switched networks is that timing analysis is
easier. Misrouting could occur with a packet-switched network but much
of the network overall will survive which is why the Internet was
designed to be as it is: resilient to much of the U.S.A. being
destroyed by a nuclear attack from the U.S.S.R. So in that sense it
could be considered to be of high integrity. However, in the sense
that I would prefer to summon an ambulance by using a circuit-switched
landline telephone, it could be considered to have less desirable
characteristics. As I posted above, it depends on the requirements.

H. Pfeifer, F. von Henke, ``Modular Formal Analysis of the
Central Guardian in the Time-Triggered Architecture'', accepted for
publication in "Reliability Engineering & System Safety", Special
Issue on Safety, Reliability and Security of Industrial Computer
Systems, Elsevier Ltd., 2006,
HTTP://WWW.Informatik.Uni-Ulm.De/ki/Pfeifer/ress06.html
is another reference.

Metastability is claimed to be possible in fewer parts for the
asynchronous design in A. Sheibanyrad, I. Miro Panades and
A. Greiner, ``Systematic Comparison between the Asynchronous and
the Multi-Synchronous Implementations of a Network on Chip
Architecture'', Design for Automation and Test Europe
2007. Eliminating the risk of metastability is doubtful (consult
Freidin; Wormald; Cheney et al., ``Tell me about Metastability'',
HTTP://WWW.FPGA-FAQ.org/FAQ_Pages/0017_Tell_me_about_metastables.htm
) whereas members of the supposedly real-time community, e.g. Burns
and Wellings, do not voluntarily admit that digital electronic devices
are not proven to be suitable for real-time systems.

Regards,
Colin Paul Gloster

Re: High-integrity networking

[Maciej Sobczak]

On 15 Pa , 19:14, Colin Paul Gloster <Colin_Paul_Glos...@ACM.org>
wrote:

[...]

Thank you for these references, the points you make in between are
also interesting.
I was more focused on the approaches to be considered at each
communication end-point, but it is clear that the communication
technology as a whole (including physical level) cannot be excluded
from the discussion.

--
Maciej Sobczak * www.msobczak.com * www.inspirel.com