Special Issue: Euro-Par 2007

This special issue of Concurrency and Computation: Practice and Experience contains revised and extended versions of selected papers presented at the Euro-Par 2007 conference.

Euro-Par—the European Conference on Parallel Computing—is an annual series of international conferences dedicated to the promotion and advancement of all aspects of parallel and distributed computing. The major themes can be divided into the broad categories of hardware, software, algorithms, and applications for parallel and distributed computing.

Euro-Par 2007, the 13th conference in the Euro-Par series, was organized in Rennes, France, by the Brittany Research Center of INRIA, the French National Institute for Research in Computer Science and Control, in the framework of the IRISA Research Laboratory, a joint lab between CNRS, University of Rennes 1, INSA Rennes, and ENS Cachan, Brittany Campus.

Fourteen broad topics were defined and advertised, covering a large variety of aspects of parallel and distributed computing. The call for papers attracted a total of 333 submissions. The submitted papers were reviewed at least three and, in many cases, four times. A total of 89 papers were finally accepted for publication. Thus, the global acceptance rate was below 27%. The authors of accepted papers come from 27 countries, with the four main contributing countries—U.S.A., France, Spain and Germany—accounting for more than 60%.

Based on the results of the original reviewing and a majority opinion of the topic programme committees, several papers were recommended for a special journal issue. The authors of these papers were contacted after the conference and invited to submit revised and extended versions of their papers. These resulting papers were reviewed independently by three reviewers. Where possible, two reviewers were chosen among the conference reviewers, and a third had not reviewed the work before. Eventually, four papers were accepted for publication.

These four papers provide a good indication of the breadth of topics covered by Euro-Par. They address issues ranging from high-performance architectures and compilers to scheduling and load-balancing algorithms. Two of them address questions related to mobile and ubiquitous computing. In fact, this field is gaining more and more interest, as illustrated by the 61 papers submitted to this topic at the conference.

All four papers promote the central vision at the root of the Euro-Par conference series: there is no gap between theory and practice in the field of parallel and distributed systems. Mastering and conducting such systems is so difficult that no improvement can ever be gained in practice without resorting to high-level, even theoretical approaches. Parallel and distributed systems, especially when it comes to modern, large-scale systems, are simply too complex!

The first paper, Schemes for Avoiding Starvation in Transactional Memory Systems, by M. M. Waliullah and P. Stenström, is a very good example of this Euro-Par vision. As multi-core architectures are becoming commonplace, the need to make parallel programming easier is becoming acute. Transactional memory promises to reduce the programming effort by unburdening the programmer from resolving complex, fine-grain, inter-thread dependences by classical synchronization primitives such as locks and event synchronizations. This cannot be done without a detailed study of the underlying abstract model, especially when the scalability of the solution is addressed.

The next two papers promote a similar approach in the domain of ad hoc networks. The first paper, On the Connectivity of Bluetooth-Based Ad Hoc Networks, by P. Crescenzi et al., demonstrates that a study of the connectivity properties of a family of abstract random graphs can help mastering the Bluetooth networking technology. The class of abstract random graphs studied in this paper models the Bluetooth's device discovery process closely. The analytical and experimental results provide evidence that Bluetooth can indeed be used for establishing large ad hoc networks.

The second paper in the domain of ad hoc networks, An Algorithm for Dissemination and Retrieval of Information in Wireless Ad Hoc Networks, by H. Miranda et al., addresses the problem of distributing the data items among different nodes of a wireless, infrastructureless network. Replicating the data is helpful, but it also tends to saturate the system: a trade-off has to be found for optimal efficiency. The paper proposes a novel algorithm for finding this trade-off. Again, this is a convincing example that such complex problems cannot be tackled by handwaving or by chance: only a careful, scientific study of the algorithms can provide a good solution.

The last paper, Cooperation in Multi-Organization Scheduling, by F. Pascual et al., is again a good example of the Euro-Par vision but, this time, at the level of large-scale federations of clusters, also know as grids, spread over an entire country. The distributed nature of such architectures results in the problem of scheduling parallel jobs produced by several independent organizations that have partial control over the system. Of course, each organization wants its tasks to be completed as soon as possible. Nothing new under the sun, but, this time, there is a free lunch! In fact, the paper shows that, in this very specific model, it is always possible to produce a collaborative solution that respects participants' selfish goals, at the same time improving the global performance of the system.

Concluding this preface, we would like to thank Prof. Geoffrey Fox and Prof. Luc Moreau, editors of this journal, for their support of this special issue. Euro-Par will continue the tradition of annual special issues in the years to come. We would also like to thank our peers who assisted us in reviewing the papers and helped strengthen the final versions. Last, but not least, we also appreciate the support of Springer-Verlag, who agreed to the publication of the extended versions of the articles that appeared originally in the series Lecture Notes in Computer Science.