D-CON 2016

This page is about the annual D-CON meeting of German scientists working in the area of Concurrency Theory, to be held on March 7-8, 2016 in Saarbrücken.

Please observe this page for up-to-date info.



Invited Talk by Rupak Majumdar

Verification of Population Protocols


Population protocols are a model for parameterized systems in which a set of identical, anonymous, finite-state processes interact pairwise through rendezvous synchronization. In each step, the pair of interacting processes is chosen by a random scheduler.
Angluin et al. (PODS 2004) studied population protocols as a distributed computation model. They characterized the computational power in the limit (semi-linear predicates) of a subclass of protocols (the well-specified ones). However, the modeling power of protocols go beyond computation of semi-linear predicates and they can be used to study a wide range of distributed protocols, such as asynchronous leader election or consensus, stochastic evolutionary processes, or chemical reaction networks.
Correspondingly, one is interested in checking specifications on these protocols that go beyond the well-specified computation of predicates.

We characterize the decidability frontier for the model checking problem for population protocols against probabilistic linear-time specifications.
We show that the model checking problem is decidable for qualitative objectives, but as hard as the reachability problem for Petri nets. However, it is undecidable for quantitative properties.
Our decidability proof uses techniques from Petri net theory, and the characterization of limit behaviors of population protocols.
In particular, our results show decidability of the following basic verification problems: Is a given protocol well-specified (i.e., computes a predicate in the sense of Angluin et al.)? Does a protocol compute a given predicate?

[Joint work with Javier Esparza, Pierre Ganty, and Jerome Leroux]


Dates & Times

On Monday, March 7, the meeting starts at 09:00 in the morning. We expect to finish at lunch time on Tuesday, March 8. Especially for those intending to stay on we will provide office space and meeting facilities.

The workshop dinner will take place on Monday, March 7, at the Café am Schloss, commencing at 19:30.

An informal get-together on Sunday evening will take us to the Stiefelbräu at the corner of St. Johanner Markt. We meet there at 19:30 (entrance on Fröschengasse), or at 19:20 at the fountain on St. Johanner Markt.

Programme

A draft programme is available now. Please send comments or suggestions to Holger Hermanns.

Accommodation

Recommendable hotels (all downtown, with connectivity to university Campus by bus) are:

Christa Schäfer can assist with hotel room bookings if desired. Be advised to book your hotel as soon as possible.

Venue

Map

The meeting takes place in Buiding E1 1, room 407 and 306. Opening and plenaries are in 407.


View D-CON 2016 in Saarbrücken in a larger map

Getting there

Getting to Saarbrücken by train

Saarbrücken central train station ("Saarbrücken Hbf") is easy to reach by train:

  • From Paris Est: < 2 hours by ICE/TGV
  • From Frankfurt Hbf/Frankfurt Airport: ~ 2 hours by ICE/TGV
  • From Mannheim: ~ 1 hour 30
  • From Mainz, Trier, Koblenz via regional trains

Use bahn.de for timetables.

Getting to Saarbrücken by car

Plan your route to Saarbrücken or directly to Campus.

Parking on Campus

If you arrive on Campus by car, use the parking deck "Universität Ost", which is closest to the computer science buildings (see Campus map; you want to park next to the letter E). Draw a normal parking ticket when entering. We will exchange that ticket for a free exit ticket on site.

Getting to Saarbrücken by plane

There are direct connections between Saarbrücken Airport (IATA: SCN) and Berlin Tegel (Air Berlin), Hamburg (Luxair), Luxemburg (Luxair), and Palma de Mallorca (Air Berlin). There is an hourly bus connection between the airport and the city centre. Getting to Campus will be significantly faster by taxi, though.

Bus connections to Campus

From Saarbrücken Central Station (for B&B, Mercure, La Residence) take bus line 102, 112 or 124 to the 'Universität Busterminal' stop. Timetables: PDF
From central downtown 'Rathaus' stop (for Motel One, Leidinger Madeleine), take bus line 101, 102, 109 or 111 to the 'Universität Busterminal' stop. Timetables: PDF
Hotel Weller is served by 101, 112, 124 from stop 'An der Trift'. Timetables: PDF

The ticket price is 2.60 € for a single bus ride. Tickets can be bought from the driver. The 'Universität Busterminal' stop is reached once you have crossed the entire Campus, between a parking deck (right) and the Fraunhofer-Institut (left). Get off, and walk back some 200 meters to the Campus. Right after the gate, the CS buildings are to your left and right (quiet new).

You might also want to manage your bus connections via your smartphone.