Monday, November 30, 2015

Advent Programming Contest 2015

An Advent calendar is a special calendar used to count or celebrate the days in anticipation of Christmas. Advent calendars typically begin on December 1 and provide a window to open until December 24. Usually they have windows, which you can open each day containing some chocolate or other stuff. But what is better to kill some time until Christmas, Hanukkah, Yule, Kwanzaa, Diwali, Boxing Day, etc. than an Advent calendar giving you a programming problem every day?

The Advent Programming Contest, being organized by the IEEE Student Branch Klagenfurt will provide a new problem every day from December 1st to December 24th. You can submit solutions any day until the contest ends on December 26. You can choose to use C, C++, C#, Java, Perl, Python 2.x or Python 3.x as programming language. The programming tasks can be solved with short programs (typically less than 100 lines of code). Until a solution is correct you can submit your program as often as you want (but please don't spam our server). The number of tries will not be a criterion for determining your score. The idea is to do it just for fun, but we will try to announce a winner after the contest is closed. The event is open to everyone. There are separate categories for pupils, university students and others. If you want to participate, please register at (Registration is also possible after 1st December)

Tuesday, November 24, 2015

Random Numbers in Java: Comparison of java.util.random, Xorshift, and PCG

In a previous post, we have shown how to replace the Java random number generator with a faster Xorshift algorithm, which also has nicer properties than the Java random number generator which was implemented in 1995.

Melissa E. O’Neill from Harvey Mudd College suggests a new class of random number generators called PCG. For a detailed description, see her paper "PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation".

Like the Xorshift algorithm, PCG is using a couple of shift and bitwise logical operators to generate random integers. Typically this is faster that Java's linear congruential generator. We have implemented a simple version of the PCG algorithm in order to compare its performance to java.util.random and our Xorshift implementation.

The best way to replace the Java random generator in our opinion is to make a subclass of java.util.random and to overwrite the next() method. For Xorshift, the algorithm is as follows:

import java.util.Random;

 * A subclass of java.util.random that implements the 
 * Xorshift random number generator

public class XSRandom extends Random {
 private long seed;

 public XSRandom(long seed) {
  this.seed = seed;

 protected int next(int nbits) {
  long x = seed;
  x ^= (x << 21);
  x ^= (x >>> 35);
  x ^= (x << 4);
  seed = x;
  x &= ((1L << nbits) - 1);
  return (int) x;

We implemented the PCG algorithm in Java based on the minimal C code example by M.E. O'Neill at

import java.util.Random;

 * A subclass of java.util.random that implements the 
 * PCG32 random number generator
 * Based on the minimal code example by M.E. O'Neill /
 * Licensed under Apache License 2.0

public class PCGRandom extends Random {
 private long inc;
 private long state;
 public PCGRandom(long seed) {
  this.state = seed;

 public PCGRandom(long seed, long initseq) {
  // initseq selects the output sequence for the RNG
  this.state = seed;;

 protected int next(int nbits) {
  long oldstate=state;
  // Advance internal state
  state=oldstate * 6364136223846793005L + (inc | 1);
  // Calculate output function (XSH RR), uses old state for max ILP
  long xorshifted = ((oldstate >> 18) ^ oldstate) >> 27;
  long rot = oldstate >> 59;
  return (int) ((xorshifted >> rot) | (xorshifted << ((-rot) & 31)));

To use the class in legacy code, you may also instantiate an XSRandom object and assign it to a java.util.Random variable:
  java.util.Random rand = new XSRandom(); // or new PCGRandom
All method calls to rand are then using the new implementation.

The PCG algorithm comes with better properties regarding its period. But what about the performance?
We tested the performance by calculating 107 random numbers subsequently, repeating this 10 times with different starting seeds. Then we compared the average execution time for a program compiled under Java 8 running single threaded on an core i7 notebook computer. Results show that for our implementation, the PCG algorithm has a very similar execution time to the original Java random generator, while the Xorshift is significantly faster.

Execution time of java.util.random, Xorshift, and PCG. Please note that y axis starts at 10 ns.
So if you mainly care about speed, go for Xorshift. If statistical quality is important, go for PCG. If you want a bad random number generator and have a lot of time, stick with java.util.random.

Tuesday, June 2, 2015

Five postdoctoral fellowships in complex systems, Mexico

The Center for Complexity Science of the National Autonomous University of Mexico is seeking outstanding candidates for five one year postdoctoral positions beginning in August, 2015. Research plans from all areas related to complex systems are encouraged.

Please send CV and research plan to cgg [at] before June 10th.

Original post: Complexes: Five postdoctoral fellowships in complex systems, UNAM

Monday, April 13, 2015

Hardware for Swarm Robotics

Collective behavior that emerges from the interactions between agents and with the environment are one of the most prominent examples of self-organizing systems. The field of swarm robotics allows to research and engineer such collective behavior. However to do this, there is the need for small cost-effective swarmbots. 

The table below lists a number of robots used in real experiments in the field of swarm robotics. It shows the most important parameters and information about the robots simplifying comparison between them. For more detailed description there are links (right after the robots' names) to websites or articles exhibiting specifications or conducted experiments.
RobotCostLocomotionSpeed (cm/s)Size (cm)Battery life (hours)Communication
Jasmine[1,2]$118wheelsN/A2.6x2.6x2.61-2RF, IR
E-puck[1,2]$850wheels13∅71-10Bluetooth, ZigBee
R-one[1,2]$322wheels30 cm/s∅106RF, IR
JL-2[1]N/Atracks 2035x25x152Wi-Fi
Khepera IV[1, 2]$2700wheels 100∅144-7Wi-Fi, Bluetooth

One of the first questions, coming up in the beginning of a project concerning swarm robotics, is money. Conducting real experiments with dozens of robots require high investments to buy all needed hardware and software. The price of the robots varies greatly that depends on a number of sensors and actuators, quality of a robot's frame, and demand for a particular robot. Unfortunately, the price of some robots is not specified. The most of these robots have an open-source design and code so they can be built from scratch in case there is such a need.

The table shows that the majority of the robots are differential drive robots whose movement is based on two wheels placed on either side of the robot. It allows achieving higher speed and precisely controlling the direction of movement. However, there are also some disadvantages, such as a need for a prepared surface without pits and bumps. Robots using the tracks usually can move on the unprepared surface, which facilitates a preparation for experiments and demonstrations. A unique type of locomotion is vibration (check the Kilobot robot) which tends to be slow and imprecise way of movement. It also requires a special smooth surface.

Size matters in the field of swarm robotics. A swarm consists of a large number of individuals which are quite effective in performing of important tasks for surviving of the colony. A significant number of robots is important in order to reproduce the swarm behavior or to check a hypothesis.

Unlike individuals in the real swarms, robots cannot generate energy from organics and still require a source of energy such as a battery. The working time of a robot depends on the capacity of battery and the amount of sensor and actuators using by a robot in experiments. Some of the robots have charging stations (e.g. Elisa, Jasmine) which may be useful in conducting of long-term experiments. The marXbot goes even further supporting exchange of the battery in less than 10 seconds without shutting down the power.

Communication in swarm robotics can play a crucial role while the effectiveness of the whole colony depends on how well the robots can send and receive messages. There are two types of communication: abstract (e.g. Wi-Fi, Bluetooth, ZigBee, RF) and situated (e.g. IR). Both of them work well for messages exchange, but situated communication provides additional information about the sender and the message, e.g. strength of the signal and its direction.

The choice of the robot depends on experiments where it will be used. Select the most important features of the future research and pick a robot that fits best.

Monday, April 6, 2015

Call for Papers Ninth IEEE International Conference on Self-Adaptive and Self-Organizing Systems (SASO 2015)

 The Ninth IEEE International Conference on Self-Adaptive and Self-Organizing Systems (SASO 2015)

Boston Massachusetts; 21-25 September 2015

Part of FAS* - Foundation and Applications of Self* Computing Conferences

Colocated with:

Aims and Scope aim of the Self-Adaptive and Self-Organizing systems conference series (SASO) is to provide a forum for the foundations of a principled approach to engineering systems, networks and services based on self-adaptation and self-organization. The complexity of current and emerging networks, software and services, especially in dealing with dynamics in the environment and problem domain, has led the software engineering, distributed systems and management communities to look for inspiration in diverse fields (e.g., complex systems, control theory, artificial intelligence, sociology, and biology) to find new ways of designing and managing such computing systems. In this endeavor, self-organization and self-adaptation have emerged as two promising interrelated approaches. They form the basis for many other self-* properties, such as self-configuration, self-healing, or self-optimization. Systems exhibiting such properties are often referred to as self-* systems.

The ninth edition of the SASO conference embraces the inter-disciplinarity and the scientific, empirical, and application dimensions of self-* systems and welcomes novel results on both self-adaptive and self-organizing systems research. The topics of interest include, but are not limited to:

  • Self-* systems theory: theoretical frameworks and models; biologically- and socially-inspired paradigms; inter-operation of self-* mechanisms;
  • Self-* systems engineering: reusable mechanisms, design patterns, architectures, methodologies; software and middleware development frameworks and methods, platforms and toolkits; hardware; self-* materials;
  • Self-* system properties: robustness, resilience and stability; emergence; computational awareness and self-awareness; reflection;
  • Self-* cyber-physical and socio-technical systems: human factors and visualization; self-* social computers; crowdsourcing and collective awareness; human-in-the-loop;
  • Applications and experiences of self-* systems: cyber security, transportation, computational sustainability, big data and creative commons, power systems; swarm systems and robotics.
  • Self-* in education: experience reports; curricula; innovative course concepts; methodological aspects of self-* systems education

Contributions must present novel theoretical or experimental results; novel design patterns, mechanisms, system architectures, frameworks or tools; or practical approaches and experiences in building or deploying real-world systems and applications. Contributions contrasting different approaches for engineering a given family of systems, or demonstrating the applicability of a certain approach for different systems, are equally encouraged. Likewise, papers describing substantial innovation or insights in the use and communication of self-* systems in the classroom are welcome.

Where relevant and appropriate, accepted papers will also be encouraged to participate in the Demo or Poster Sessions.

Important Dates

Abstract submission: May 8, 2015
Paper submission: May 22, 2015 (There will be no extensions of this deadline)
Notification: June 30, 2015
Camera ready copy due: July 17, 2015
Conference: September 21-25, 2015

Submission Instructions

All submissions should be 10 pages and formatted according to the IEEE Computer Society Press proceedings style guide and submitted electronically in PDF format.
Please register as authors and submit your papers using the SASO 2015 conference management system, which is located at:

The proceedings will be published by IEEE Computer Society Press, and made available as a part of the IEEE digital library. Note that a separate call for poster submissions has also been issued.
Review Criteria

Papers should present novel ideas in the cross-disciplinary research context described in this call, clearly motivated by problems from current practice or applied research.

We expect both theoretical and empirical contributions to be clearly stated, substantiated by formal analysis, simulation, experimental evaluations, comparative studies, and so on. Appropriate reference must be made to related work. Because SASO is a cross-disciplinary conference, papers must be intelligible and relevant to researchers who are not members of the same specialized sub-field. Authors are also encouraged to submit papers describing applications. Application papers are expected to provide an indication of the real world relevance of the problem that is solved, including a description of the deployment domain, and some form of evaluation of performance, usability, or comparison to alternative approaches. Experience papers are also welcome, but they must clearly state the insight into any aspect of design, implementation or management of self-* systems which is of benefit to practitioners and the SASO community

Conference General Chairs

  • Howard E. Shrobe, MIT CSAIL, Cambridge, MA, USA
  • Julie A. McCann, Imperial College London, UK

Program Chairs

  • Emma Hart, Edinburgh Napier University
  • Gregory Sullivan, BAE Systems AIT
  • Jan-Philipp Steghöfer, University of Gothenburg, Sweden

Friday, February 27, 2015

SEAHORSE: A Middleware for Search and Delivery of Information Units based on an Artificial Hormone System Algorithm

SEAHORSE structure
With the rise of networked smart devices and the so called Internet of Things, services require more scalability and robustness to handle the complexity of the underlying ecosystem. In some situations (e.g., disaster areas, large-area sports events, battle fields, etc.), a traditional network infrastructure does not exist, or is expensive to set up. In this context content is also consumed in a more dynamic way than in traditional environments. By looking at principles found in nature we can see that it is possible to handle complexity and dynamics by relying exclusively on simple, local decisions (bio-inspired self-organizing systems). As an example, ants are exploring the surrounding area to find food, and if found they go back to their home base leaving pheromones to guide other ants.
We introduce SEAHORSE, a middleware showing by example how an existing self-organizing algorithm can be generalized. SEAHORSE is a first step for bringing self-organizing algorithms towards real-world applications.
By specifying interfaces to the application the middleware transparently handles the distribution of content. We show two use cases from different technical fields and performed a parameter analysis to reduce the configuration effort.

A. Sobe, W. Elmenreich, T. Skalicky, and L. Böszörmenyi. SEAHORSE: Generalizing an artificial hormone system algorithm to a middleware for search and delivery of information units. Elsevier Journal of Computer Networks, 2015.

Wednesday, February 18, 2015

Advent Programming Contest 2014 Awarding

At the awarding ceremony
In December 2014, the Advent Programming Contest (APC) was held for the third time. The joint event between the Faculty of Technical Sciences and the IEEE Student Branch Klagenfurt enjoys increasing popularity every year. This time there were 345 enthusiastic participants who accepted the challenge and tryed to solve a daily programming task from December 1st to December 24th. I hope everybody who participated enjoyed the problems, even though nobody was able to solve all the tasks. While every problem was solved at least once, the maximum number of solved tasks by any participant was 23 out of 24 – given the hardness of several of the problems this is an excellent result.
The winners of the three categories of "student", "university staff" and "other" were announced at a formal ceremony organized by the IEEE Student Branch Klagenfurt. The best student adventcoder was Philip Gasteiger, student of computer science at Alpen-Adria-Universität Klagenfurt.
The best pupil adventcoder, Simon Dörrer, came from HTL Mössingerstraße Klagenfurt. Ben Wright, a recent graduate of the University of Tennessee, Martin, now working as a software engineer won the third category “other” and attended the ceremony via webcast.