Call for Nominations: The 2008 Edsger W. Dijkstra Prize in Distributed Computing

The call for nominations for the 2008 Edsger W. Dijkstra Prize in Distributed Computing is now out. See here. The prize is given for outstanding papers on the principles of distributed computing, whose significance and impact on the theory and/or practice of distributed computing has been evident for at least a decade, and is sponsored jointly by the ACM Symposium on Principles of Distributed Computing (PODC) and the EATCS Symposium on Distributed Computing (DISC). The award is presented annually, with the presentation taking place alternately at ACM PODC and EATCS DISC - this year it will be presented at PODC 2008.

Let's think up outstanding nominations!

Complete Scientific Programme for ICALP 2008

The scientific programme for ICALP 2008 is now available here. It looks like we are going to have a scientific feast, and hopefully many of you will come and join us.

ICALP 2008: Bird's Eye Programme

In case you are wondering what is going to happen at ICALP 2008, and when, I encourage you to look at the skeleton of the conference programme, which is available here. Some more detail is presently available for track B.

The conference organizers strongly recommend that you register for the ICALP conference and book accommodation before May 5th, as that date is the deadline for registering at the lower fee. After May 5th hotel rooms will also start to get released since July is the prime holiday season in Iceland and the demand for hotel accommodation is very high.

NOTE: For those who have not decided yet which workshop(s) they are going to attend when registering for the conference, it is possible to register for workshops at the lower fee until June 5th by sending an e-mail to the Conference Secretariat.

Look Who's Doping

The inimitable Dr. Z wrote in his April 1, 2008, opinion:

But I strongly disagree with the unfortunate decision to forbid the use of any result, or solve any open problem posed by, the great Paul Erdös, on the grounds that he was "doping" by using stimulants like amphetamines. While I definitely do not recommend anyone to start taking prescription drugs, mathematics is not (yet) the tour-de-France, and if we start forbidding them, what's next? coffee?. It is no coincidence that Erdös quipped that a mathematician is a machine that turns coffee into theorems. Without coffee (and unfortunately other stimulants) we would not have progressed beyond Euclid. Coffee is so much part of our culture that it would take much more than one committee to disallow it at AMS meetings.

On the same day, a press release written by evolutionary biologist Jonathan Eisen of the University of California, Davis, declared that the US National Institutes of Health is to crack down on scientists 'brain doping' with performance-enhancing drugs such as Provigil and Ritalin.

These were, of course, intended as two funny pranks. Now, however, Nature is spotlighting a study on the use of cognition-enhancing drugs by academics. (Alas, a subscription is needed to access the text.) The article in Nature reports on the results of a survey conducted by that journal on whether readers of Nature (scientists) would consider “boosting their brain power” with drugs. The article states that 1,400 people from 60 countries responded to the online poll.

Apparently "one in five respondents said they had used drugs for non-medical reasons to stimulate their focus, concentration or memory." Moreover, use of drugs did not differ greatly across age-groups. According to the article, "the numbers suggest a significant amount of drug-taking among academics." So, not only academics drink more than rest of population on average (or so I seem to recall reading somewhere recently), but they also enhance their performance by taking drugs :-) Will we soon have to sign declarations that our work was not done under the influence of performance-enhancing drugs as well as copyright release forms? Or will we have to have drug tests taken when we submit papers to conferences or journals? And will all authors of an article have to take such tests?

On a more serious note, as a parent, I was a little concerned when I read that

When asked whether healthy children under the age of 16 should be restricted from taking these drugs, unsurprisingly, most respondents (86%) said that they should. But one-third of respondents said they would feel pressure to give cognition-enhancing drugs to their children if other children at school were taking them. Morein-Zamir found this coercive factor very interesting. “These numbers strongly suggest that even if policies restricted their use by kids, pressure would be high for parents,” she says.

(The emphasis is mine.) Would you give drugs to your children to enhance their mental performance?

Sometimes I wonder what our answer would be if we were offered a Faustian pact promising that we would solve, say, two fundamental problems of our choice at the price of our "soul". What would your reaction to this "two-for-the-price-of-one" offer be? Has any science-in-fiction novel ever been written on this theme?

Addendum: After I wrote this post, Luca Trevisan pointed out to me the delightful short story "The devil and Simon Flagg" by Arthur Porges. I recommend it!

Accepted Papers for ICALP 2008--Track C

The list of accepted papers for track C of ICALP 2008 is now available here. You can get an overview of all of the accepted papers from this web page.

I strongly encourage all of you who are planning to come to Iceland for ICALP 2008 to start planning your trips now. In addition, if you register now you can take advantage of the present strength of many foreign currencies vis-a-vis the Icelandic crown :-)

I also strongly recommend signing up for the conference dinner. The conference dinner will be held at Perlan (The Pearl). (See the photo above.) The Perlan restaurant is consistently one of the best restaurants in town and is Reykjavik's latest landmark. Towering over the city from one of its highest hills, Perlan sits atop the geothermal reservoir tanks overlooking the city. The top floor restaurant is enclosed in a glass dome and the floor rotates 360^o degrees every 90-120 minutes. The restaurant offers a stunning panoramic view of Reykjavik and the surrounding areas.

See also the other events in the social programme. I'll post more information on ICALP 2008 on this blog at a later date. In particular, the Gödel prize winner for 2008 will be announced very soon.

Terence Tao Receives NSF Award

The NSF has bestowed the Waterman Award to Terence Tao. (The press release is here.) The list of Tao's awards is already very long, and includes the Salem Prize in 2000, the Bochner Prize in 2002, the Fields Medal and SASTRA Ramanujan Prize in 2006, and the MacArthur Fellowship and Ostrowski Prize in 2007.

And he even finds the time to write very detailed and informative blog posts!

Accepted Papers for ICALP 2008, Track B

The list of accepted papers for track B of ICALP 2008 is now available. The list of accepted papers for ICALP Track A has been posted yesterday evening, and already a few blogs have pointed to it. See the Complexity Weblog, David Eppstein, and Michael Mitzenmacher. It seems to me that the PCs for the ICALP tracks have faced some very hard choices this year since the quality of the submissions was very high.

I'll post the list of accepted papers for track C when it becomes available.

Rankings of CS Departments in the USA

I learned from Mihai Patrascu's blog that the US News rankings for 2008 have been released. The rankings for computer science, for CS theory, and for mathematics do not show any truly major surprises.

In your opinion, what are the best CS departments in theory outside the US? And how would you compare them with the top departments in the US News ranking? Perhaps more modestly, what are the best CS departments in TCS in your country?

The Equational Theory of Prebisimilarity over Basic CCS with Divergence

I recently posted the short paper

Luca Aceto, Silvio Capobianco, Anna Ingolfsdottir and Bas Luttik. The Equational Theory of Prebisimilarity over Basic CCS with Divergence. March 2008.

This paper studies the equational theory of prebisimilarity, a bisimulation-based preorder introduced by Hennessy and Milner in the early 1980s, over basic CCS with the divergent process Omega.

It is well known that prebisimilarity affords a finite ground-complete axiomatization over this language. This finite axiomatization is obtained by adding the inequation

Omega <= x

to the complete axiomatization of bisimilarity over basic CCS. In the above paper, we prove that this ground-complete axiomatization is also complete in the presence of an infinite set of actions. Moreover, in sharp contrast to this positive result, we show that prebisimilarity is not finitely based over basic CCS with the divergent process Omega when the set of actions is finite and non-empty.

February 2008 Issue of the BEATCS

Volume 94 of the Bulletin of the EATCS is now available on line, freely and to everybody as it should be.

Of course, you should read the two pieces that make up the concurrency column :-) In addition, apart from the contributions to the other columns in the Bulletin, I encourage you to have a look at A "big-ideas" approach to teaching Computation Theory , a contribution to the educational column by Arnold L. Rosenberg. I have not had time to mull over his proposal yet, but it is certainly worth thinking about it and contributing our two-cent worth to what is an interesting opinion on how to teach one of our flagship courses.

Let me encourage you to support the EATCS by becoming a member of that association. For a mere 25 € 30 € per year (25€ if you are also a SIGACT member), you will make sure that the EATCS can continue supporting TCS research as a whole.

What is the Shortest PhD Thesis in TCS?

Gmail's webclips feature alerted me to the availability of Edmund Landau's PhD thesis in English translation. The thesis is 13 pages, which is substantially shorter than any PhD thesis in CS I am aware of.

I suspect that PhD theses in mathematics are, by and large, shorter than those in TCS. What is the shortest PhD thesis in either subject you are aware of? (In the case of mathematics, let's restrict ourselves to modern times, but if anyone knows of a thesis that is shorter than Landau's I'd be interested in knowing the details.)

Here is my own contribution. Off the top of my head, I recall that Jay Loren Gischer's PhD thesis from Stanford (year: 1984; topic: the theory of pomsets; supervisor: Vaughan Pratt, see also here) was between 45- and 50-page long.

Abel Prize 2008

The Norwegian Academy of Science and Letters has decided to award the Abel Prize for 2008 to John Griggs Thompson, University of Florida and Jacques Tits, Collège de France. Thompson and Tits receives the Abel Prize “for their profound achievements in algebra and in particular for shaping modern group theory”.

The committee's citation can be read here. Thompson and Walter Feit are the authors of the famous Odd Order Paper, filling a whole issue of the Pacific Journal of Mathematics. Georges Gonthier is leading an effort that aims to produce a computer-checked proof of this famous result in group theory.

The Usefulness of Bisimilarity Checking in Practice

I am collecting information as well as opinions on the practical usefulness of bisimulation checking. I feel that there are disparate views out there and they may be worth recounting. I plan to solicit opinions from experts in the verification community, but I am also interested in the thoughts on this topic of the readers of this blog. Feel free to email me your opinions or to post a comment. I would also appreciate receiving bibliographic references where the usefulness of bisimulation checking and bisimulation minimization are discussed.

Thanks in advance!

Accepted Papers for LICS 2008

The list of accepted papers for LICS 2008 is now available here. Some of the accepted papers that, judging by their titles, ought to be of interest for a concurrency theorist are the following ones.

- Christel Baier, Nathalie Bertrand, Patricia Bouyer, Thomas Brihaye and Marcus Groesser. Almost-Sure Model Checking of Infinite Paths in One-Clock Timed Automata

- Taolue Chen and Wan Fokkink. On the Axiomatizability of Impossible Futures: Preorder versus Equivalence

- Ivan Lanese, Jorge A. Perez, Davide Sangiorgi and Alan Schmitt. On the Expressiveness and Decidability of Higher-Order Process Calculi

- Emmanuel Beffara. An Algebraic Process Calculus

- Tomas Brazdil, Jan Kretinsky, Antonin Kucera and Vojtech Forejt. The Satisfiability Problem for Probabilistic CTL

- Sam Staton. General Structural Operational Semantics through Categorical Logic

I'll try to find some time to write a few lines on at least some of them when they are available on line.

Axiomatizing Restriction and Relabelling

Time flies somehow. At some point in late February I posted the following paper:

Luca Aceto, Anna Ingolfsdottir, Bas Luttik and Paul van Tilburg. Finite Equational Bases for Fragments of CCS with Restriction and Relabelling. Technical Report CSR-08-08, TU/Eindhoven, February 2008.

I meant to write a blog entry on the paper then, but that intention has not materialized until now.

So what is the above study about? We investigate the equational theory of several fragments of Milner's CCS modulo (strong) bisimilarity with special attention to restriction and relabelling. The largest fragment we consider includes action prefixing, choice, parallel composition without communication, restriction and relabelling. We present a finite equational base (i.e., a finite ground-complete and omega-complete axiomatisation) for it, including the left merge from ACP as auxiliary operation to facilitate the axiomatisation of parallel composition.

Perhaps surprisingly, no complete axiomatisations of bisimilarity over languages including restriction and relabelling have been given to date. In a classic paper, Milner studied an algebra of flowgraphs with operations of (parallel) composition, restriction and relabelling, and provided a complete axiomatisation for it. In that reference, however, the notion of equivalence between expressions is purely “structural”, since two expressions are equated when they denote the same flowgraph up to isomorphism.

I hope that some of you will find the paper worth looking at. I enjoyed working on it a lot, thanks to my co-authors.

Four IFIP Scholarships for ICALP 2008

IFIP TC1 has kindly provided sponsorship for four 500-euro scholarships. The four scholarships will be used to support participation in ICALP 2008 by young researchers from countries where access to funds is limited by covering registration and some of the local expenses. Preference will be given to PhD students presenting papers at the conference.

To apply for one of the IFIP scholarships, please send an email to the address icalp08 AT ru DOT is. The application should be sent by Wednesday, 30 April 2008, at 12:00 GMT, and should contain a motivation for the sponsorship request together with an indication of whether the applicant is a co-author of one of the papers selected for the conference.

Proving Non-finite Axiomatizability Results Via Reductions

I recently completed the writing of two papers before the final rush towards ICALP 2008. The first of these papers, in chronological order, is

Luca Aceto, Wan Fokkink, Anna Ingolfsdottir and MohammadReza Mousavi. Lifting Non-Finite Axiomatizability Results to Extensions of Process Algebras. Technical Report CSR-08-05, TU/Eindhoven, February 2008.

The general setting for the work reported in this paper is that of process algebras, which are prototype languages for the description of reactive systems. Since these languages may be used for describing specifications of process behaviour as well as their implementations, an important ingredient in their theory is a notion of equivalence or approximation between process descriptions. The equivalence between two terms in a process algebra indicates that, although possibly syntactically different, these terms describe essentially the same behaviour. Behavioural equivalences are therefore typically used in the theory of process algebras as the formal yardstick by means of which one can establish the correctness of an implementation with respect to a given specification.

In the light of the algebraic nature of process algebras, a natural question is whether the chosen notion of behavioural equivalence or approximation can be axiomatized by means of a finite collection of equations. The first negative results concerning finite axiomatizability of process algebras go back to the Ph.D. thesis of Faron Moller. Since then, several other non-finite axiomatizability results have been obtained for a wide collection of very basic process algebras; see here for a survey of such results dated mid-2005.

In general, results concerning (non-)finite axiomatizability are very vulnerable to small changes in, and extensions of, the formalism under study. Furthermore, proofs of non-finite axiomatizability results in the concurrency-theory literature are extremely delicate, rather long and error-prone. Hence, it would be useful to find some general techniques that can be used to prove non-finite axiomatizability results. Such a general theory would allow one to relate non-finite axiomatizability theorems for different formalisms, and spare researchers (some of) the delicate technical analysis needed to adapt the proofs of such results. The search for such general results is what inspired our research leading to this paper.

In the aforementioned paper, we present a theorem offering a general technique that can be used to prove non-finite axiomatizability results, and present some of its applications within concurrency theory. In this theorem, we give sufficient criteria to obtain new non-finite axiomatizability results from known ones.

The technique we propose is based on a variation on the classic idea of reduction mappings, which underlies the proofs of many classic undecidability results in computability theory and of lower bounds in complexity theory. In this setting, reductions are translations between languages that preserve sound (in)equations and (in)equational proofs over the source language, and reflect families of (in)equations responsible for the non-finite axiomatizability of the target language. In other words, the existence of a reduction shows that

• "nasty" families of (in)equations over the target language are also present in the source language, and
  
• if they were provable by means of a finite collection of valid (in)equations in the source language, they would also be "finitely provable" in the target language.
  

We show the applicability of our reduction-based technique by obtaining seven, to our knowledge novel, non-finite axiomatizability results for timed and stochastic process algebras. We also investigate some limitations of our approach. In particular, we show that prebisimilarity is not finitely based over CCS with the divergent process Omega, but that this result cannot be proved by a reduction to the non-finite axiomatizability of CCS modulo bisimilarity.

There are a few promising areas of further research in this area, and we are currently exploring some of them (ICALP organization and other tasks permitting).

I'll write a few lines on the second paper soon, but those of you who are interested in looking at it may find it here.

CS/Math Blogging and Social Skills

A very recent post by David Eppstein discusses the risks untenured academics may run into when blogging. David mentions the following typical quote: “pretenured professors should be aware of the risks of blogging and develop strategies to avoid or mitigate the pitfalls of blogging without a tenure net.”

I have the feeling, however, that at times what is needed is not the development of strategies for "safe blogging", but rather an appreciation of the fact that academics live in a society of peers, and that social skills and tact are needed for most of us to thrive in the scientific community. When supervising budding academics, we focus a lot on their scientific development, and rightly so. I am starting to believe, however, that at the same time we should pay more attention to the development of their "social skills". Being able to maintain a good working relationship with one's colleagues is a definite plus at work. Being perceived as an arrogant oddball typically isn't. Spurting gratuitous vitriolic remarks may be even funny in the very short term, but I believe that it soon becomes tiring.

We are part of a community, and a certain amount of respect for the work of our peers is healthy, if not altogether necessary, for the proper working of our society. I do not think that it is a proper thing to do to refer to one's colleagues as "losers" or to conferences as "worthless". We are all in this business to try and offer our modest contributions to (theoretical) computer science. Some of us are definitely more successful than others, but we (and most of our scientific conferences and journals) all have a role, no matter how tiny, to play. When a conference or workshop is not playing a useful role for the community it addresses, either it stops running or it redefines its scope.

Sheer arrogance serves neither the community as a whole nor the individuals who exhibit it. It will lead us nowhere. We should teach our students to exercise their freedom in judging their future colleagues with care, and make them aware of the dangers of considering themselves geniuses who are not bound by the minimal social conventions that apply to most common mortals. In fact, reading the blogs of, or talking to, scientists whose work I admire, I have always been struck by their courtesy and professionalism. We should all learn from their good example.

As an aside, Timothy Gowers, in his lovely little book "Mathematics: A Very Short Introduction", writes:

It is my impression, and I am not alone in thinking this, that, among those [the mathematicians] who do survive the various culls, there is usually a smaller proportion of oddballs than in the initial student population.

While the negative portrayal of mathematicians may be damaging, ...., the damage done by the word 'genius' is more insidious and possibly greater.....

The last quality [exceptional strategic ability] is, ultimately, more important than freakish mental speed: the most profound contributions to mathematics are often made by tortoises rather than hares.

I strongly recommend the book. It is really well written.

ACM SIGPLAN Third Workshop on Programming Languages and Analysis for Security (PLAS 2008)

Úlfar Erlingsson has asked me to advertise this event. So, here is the CFP. Do submit! Submission Deadline: March 24, 2008.



ACM SIGPLAN Third Workshop on
Programming Languages and Analysis for Security (PLAS 2008)

Tucson, Arizona, June 8, 2008

Sponsored by ACM SIGPLAN
Co-located with PLDI '08
Supported by IBM Research and Microsoft Research

http://research.ihost.com/plas2008/

Submission Deadline: March 24, 2008

Second Call for Papers

PLAS aims to provide a forum for exploring and evaluating ideas on the
use of programming language and program analysis techniques to improve
the security of software systems. Strongly encouraged are proposals of
new, speculative ideas; evaluations of new or known techniques in
practical settings; and discussions of emerging threats and important
problems.

The scope of PLAS includes, but is not limited to:

* Language-based techniques for security
* Verification of security properties in software
* Automated introduction and/or verification of security enforcement
mechanisms
* Program analysis techniques for discovering security vulnerabilities
* Compiler-based security mechanisms, such as host-based intrusion
detection and in-line reference monitors
* Specifying and enforcing security policies for information flow
and access control
* Model-driven approaches to security
* Applications, examples, and implementations of these techniques


Important Dates and Submission Guidelines

* March 24, 2008: Submission due date
* April 21, 2008: Author notification
* May 12, 2008: Revised papers due
* May 30, 2008: Student travel grant applications due
* June 8, 2008: PLAS 2008 workshop

We invite papers of two kinds: (1) Technical papers about relatively
mature work, for "long" presentations during the workshop, and (2)
papers for "short" presentations about more preliminary work, position
statements, or work that is more exploratory in nature. Short papers
marked as "Informal Presentation" will only have their abstract
printed in the proceedings. All other papers will be included in the
formal proceedings and must describe original work in compliance with
the SIGPLAN republication policy. Page limits are 12 pages for long
papers and 6 pages for short papers.

Student Travel Grants

Student attendees of PLAS can apply for a travel grant (in addition to
any PLDI grants), thanks to the generous support of IBM Research and
Microsoft Research. The application forms are on the workshop Web site.


Program Organization
* Úlfar Erlingsson, Reykjavík University, Iceland, Program Co-Chair
* Marco Pistoia, IBM T. J. Watson Research Center, Program Co-Chair

Program Committee
* Gilles Barthe, INRIA Sophia-Antipolis, France
* Bruno Blanchet, École Normale Supérieure, France
* Andy Chou, Coverity, USA
* Mads Dam, Royal Institute of Technology, Sweden
* Úlfar Erlingsson, Reykjavík University, Iceland
* Heiko Mantel, Technische Universität Darmstadt, Germany
* Isabella Mastroeni, Università di Verona, Italy
* Greg Morrisett, Harvard University, USA
* Andrew Myers, Cornell University, USA
* David Naumann, Stevens Institute of Technology, USA
* Marco Pistoia, IBM T. J. Watson Research Center, USA
* Eijiro Sumii, Tohoku University, Japan
* Dan Wallach, Rice University, USA

The Importance of Being Mobile

A comment on this post reads:

....the musical chairs that us academics play in our careers serves to disseminate our knowledge.

I agree that mobility is important in the career of most academics. Indeed, most of us have studied and worked at several institutions.

I was reminded of this comment yesterday, when I was asked to fill in a EU questionnaire on the mobility of researchers. One of the multiple-choice questions on the form read: "How often should a researcher move at different stages in her/his career?" (I was asked to answer this question since I claimed that mobility is important in the career of a researcher.) For instance, how often should one move over a four-year period at the early stages of one's career? I assumed that this question was referring to the first four years after one's PhD, and my answer off the top of my head was 1-2 times. (What I really meant was twice, but I thought 3-5 times was too much; the rationale being that one should be mobile at that crucial time in one's career, but that being overly mobile might cause too much overhead---especially if this involves changing countries. Later I looked back at my movements in the period 1991-1994 and realized that I actually moved 5 times myself.)

What is your opinion? Is mobility important at all stages of one's career? And how often should a researcher be mobile during the first four years of one's career?