Full Details

Heriot Watt University School of Mathematical and Computer Science held the second workshop of the SICSA Complex Systems Engineering sub-theme on the Theory of Resources for Autonomous and Dependable Scalable Systems (THREADSS) on Wednesday November 11th 2009. The workshop was joint with the SEMANTICS subtheme.

The purpose of the workshop is to determine common research interests and directions. Specifc focusses are:

SICSA THREADSS/SEMANTICS November Workshop Programme

New: Slides from the presentations.

WORKSHOP OBJECTIVES AND SCOPE

The workshop serves as a forum for presenting original research results
that are relevant to the analysis of resource (time, space) consumption
by computer programs. The workshop aims to bring together the
researchers that work on foundational issues with the researchers that
focus more on practical results. Therefore, both theoretical and
practical contributions are encouraged. The following list of topics is
non-exhaustive:

* resource analysis for embedded systems,
* logical and machine-independent characterisations
of complexity classes,
* logics closely related to complexity classes,
* type systems for controlling complexity,
* semantic methods to analyse resources, incl. quasi- and sup-
interpretations,
* practical applications of resource analysis.

Up to now a few similar events have taken place. In 2006, 2008
application-oriented resource analysis workshops ( EmBounded Open
Workshop in Budapest, 2006, and Resource Analysis Workshop in
Hertfordshir, 2008) were held as affiliated events of International
Symposium on the Implementation and Application of Functional Languages
(IFL). Participated: University of St. Andrew (UK), Heriot-Watt
University of Edinburgh (UK), Ludwig-Maximilians University of Munich
(Germany), University Complutense of Madrid (Spain), Politechnical
University of Madrid (Spain). Another large group of research schools is
presented in series of workshops on Implicit Computational Complexity,
see, for instance, WICC’08 in Paris . The series gather researchers
working in theoretical foundations of resource analysis, mainly from in
France (Universities of Paris Diderot and Paris Nord, LORIA Nancy),
Italy (Universities of Bologna and Turin), Norway, Germany and
Portugal. FOPARA aims to bringing these various directions in resource
analysis together and possibly to extend the community by other groups.

INVITED SPEAKER

Sumit Gulwani (http://research.microsoft.com/en-us/um/people/sumitg/),
Microsoft Research

PROGRAM

* 9:00 – 9:05 Greetings
* 9:05 – 10:00 Invited Talk (incl. 10 min discussion)

________________________________________________________________________
10:00-10:15 Coffee
________________________________________________________________________
Session 1: Abstract and Polynomial Interpretations, Data Flow
* 10:15 – 10:40 A Space Consumption Analysis By Abstract
Interpretation (Manuel Montenegro, Ricardo Peña and Clara
Segura)
* 10:40 – 11:05 Polynomials over the reals are safe for
interpretation of programs (Guillaume Bonfante, Florian Deloup
and Antoine Henrot)
* 11:05 – 11:30 Static Complexity Analysis of Higher Order
Programs (James Avery, Lars Kristiansen and Jean-Yves Moyen)
* 11:30 – 11:55 Implementing a practical polynomial programming
language (Mike Burrell, Robin Cockett and Brian Redmond)

________________________________________________________________________
Lunch 12:00 – 13:20
________________________________________________________________________
Session 2 Implicit Computational Complexity, PTIME
* 13:20-13:45 A structural and local criterion for polynomial time
computations (Luca Roversi and Luca Vercelli)
* 13:45-14:10 Polynomial Time Computation in the Context of
Recursive Analysis (Walid Gomaa)
* 14:10-14:35 Non-deterministic Boolean Proof Nets (Virgile
Mogbil)
* 14:35-15:00 Derivational Complexity is an Invariant Cost Model
(Ugo Dal Lago and Simone Martini)

________________________________________________________________________
15:00 – 15:15 Coffee
________________________________________________________________________
Session 3: Resource Analysis for varieties of programming languages
Session 3.1:
* 15:15 – 15:40 Comparing Cost Functions in Resource Analysis
(Elvira Albert, Puri Arenas, Samir Genaim, Israel Herraiz and
German Puebla)
* 15:40 – 16:05 Characterising Effective Resource Analyses for
Parallel and Distributed Coordination (Phil Trinder, Murray
Cole, Hans-Wolfgang Loidl and Greg Michaelson)
* 16:05 – 16:30 Global and local space properties of stream
programs (Marco Gaboardi and Romain Pechoux)

** 16:30 – 16:40 Pause **

Session 3.2

* 16:40 – 17:05 Improvements to a Resource Analysis for Hume
(Hans-Wolfgang Loidl and Steffen Jost)
* 17:05 – 17:30 Compositional Analysis of Hume Box Iterations
(Christoph Herrmann and Kevin Hammond)

LOCATION

The workshop is a satellite event of the 16th International Symposium on
Formal Methods, FM2009. The venue for FM2009 is the Auditorium of the
Technische Universiteit Eindhoven. Everything related to the symposium
will take place here, including workshops, lunches, and other
activities.

Technische Universiteit Eindhoven was founded in the 1950s on a patch of
uncultivated land near the centre of town. Due to this fortunate
circumstance, the university campus is now right in the middle of the
fifth largest city in the Netherlands. This means that the railway
station, the conference hotels, and other facilities are all within
walking distance of the campus, and that during your stay you will have
easy access to everything Eindhoven has to offer.

Free places are available to postgraduate students at SICSA institutions. Several topics are relevant to resource issues.

Confirmed Topics/Speakers
· Static and dynamic languages , Prof Philip Wadler, University of Edinburgh
· Compiler technology for data-parallel languages, Dr Sven-Bodo Scholz, University of Hertfordshire
· New applications of parametricity , Dr Janis Voigtlander, Technical University of Dresden
· Automatic vectorising compilation, Dr Paul Cockshott, University of Glasgow
· Foundational aspects of size analysis, Prof Marko van Eekelen/Dr Olha Shakaravska, Radboud University Nijmegen
· Context oriented programming , Dr Pascal Costanza, Vrije Universiteit Brussel
· Multi-core programming , Dr Phil Trinder, Heriot-Watt University
· Multi-core compilation, Dr Alastair Donaldson, Codeplay Software Ltd
· Principles and Applications of Refinement Types, Dr Andrew D. Gordon, Microsoft Research, Cambridge
· Resource aware programming in Hume, Prof Greg Michaelson, Heriot-Watt University/ Prof Kevin Hammond, University of St Andrews
· Haskell concurrency & parallelism, Dr Satnam Singh, Microsoft Research, Cambridge

http://www.macs.hw.ac.uk/~greg/ISS-AiPL/

The UK MM-NET (Memory Management Network) will hold a 1-day workshop on analytical techniques for memory management on Friday 12th June 2009 at the University of Manchester.

Topics of interest include but are not limited to

• static analysis for prediction of programs’ interaction with memory
• garbage collection supported by compile-time techniques
• theoretical models of memory management
• machine learning to tune memory management performance

If possible, please register by Friday June 5th.

http://www.cs.man.ac.uk/~jsinger/mmnet09.html#programme

Here is a (biased and incomplete) list based on discussion from Thursday’s workshop:

• Hume — language for real-time embedded systems, formal cost model and translation through abstract machine code (St Andrews/Heriot-Watt); uses boxes and functional programming
  W: http://www.hume-lang.org
• Planner — AI tool for automatically generating plans (Strathclyde)
• inSense — language for programming sensor networks, based on non-deterministically communicating components with int  (St Andrews/Glasgow)
  W: http://www-systems.cs.st-andrews.ac.uk/wiki/Dias/InsenseLanguage
• Minion — tool for solving constraints in a fast scalable manner (St Andrews)
  W: http://minion.sourceforge.net/

Please add more/edit what’s here.

The purpose of the workshop is to determine common research interests and directions. The first workshop will be fairly compact, with the aim of setting up high-quality collaborations between groups/institutions, and discovering research connections. The main topics of the Workshop (to be refined) are: interpretations of “resource”; application of various techniques to the study of resource information; integration of our tools; identification of applications.

SICSA Threadss Workshop Programme and Washup Slides

New: Slides from the presentations available here.

• Real-time, stack, heap, power consumption,
• concurrency, files, multi-core/many-core
• MONEY, interrupt vectors (system state),
• solar energy,
• buffer overflows (memory accesses)
• people
• electoral register, walkie-talkie
• communications bandwidth
• tools
• position (spatial location)

Do people agree with this? Are there obvious resources that are missing?

Kevin H