IFIP WG2.2 40th Anniversary Meeting (1)
From 11th to 13th September 2006 I attended a meeting of IFIP WG2.2 in Udine.
I am still thinking about issues that arose at the meeting. There was a considerable clash of views - in particular between those presented by Leslie Lamport and those of Gordon Plotkin.
I am hoping that the video produced at the conference becomes publically available so that I can check the correctness of my impressions.
Lamport made some extremely negative comments about Process algebras, Petri nets etc. He claimed that all you needed to understand concurrency was "mathematics", by which he intended set theory and first order logic.
He claimed that Process algebras had produced no results (undertanding?) about concurrency, illustrating his remarks by a challenge: is it possible to obtain mutual exclusion between processes (at a high level)without already *assuming* mutual exclusion with respect to access to the memory?
Part of the problem of answering this question is what physical assumptions you make on reading and writing to memory.
My opinion:------------------------------------------------
It is fundamental to make the assumption that it is possible to read and write to the same memory in the same discrete time interval; i.e. reading and writing may be made simultaneously.
This is not to say that for all mechanisms for reading and writing this is possible. In addition we are looking at the world at the level of discrete behaviour - that is, a continuous implementation involves arbiters.
Argument (N. Sabadini): If it is impossible to read and write at the same time, then it is impossible to listen to someone speaking.
Argument (mathematical): the identity process I, which outputs exactly the signal input, has the property that reading occurs simultaneously with writing. If you require that reading occurs after writing then this process does not act as an identity under composition with other processes - I*P is not P but P with added delay. The identity process is as important for an algebra of processes as zero is for an algebra of quantities.
------------------------------------------------------------------------
Under this assumption about reading and writing Lamport showed in 1974 that mutual exclusion with respect to the memory is not necessary for higher level mutex [A New Solution of Dijkstra's Concurrent Programming Problem, Communications of the ACM 17, 8 (August 1974), 453-455].
I am still thinking about issues that arose at the meeting. There was a considerable clash of views - in particular between those presented by Leslie Lamport and those of Gordon Plotkin.
I am hoping that the video produced at the conference becomes publically available so that I can check the correctness of my impressions.
Lamport made some extremely negative comments about Process algebras, Petri nets etc. He claimed that all you needed to understand concurrency was "mathematics", by which he intended set theory and first order logic.
He claimed that Process algebras had produced no results (undertanding?) about concurrency, illustrating his remarks by a challenge: is it possible to obtain mutual exclusion between processes (at a high level)without already *assuming* mutual exclusion with respect to access to the memory?
Part of the problem of answering this question is what physical assumptions you make on reading and writing to memory.
My opinion:------------------------------------------------
It is fundamental to make the assumption that it is possible to read and write to the same memory in the same discrete time interval; i.e. reading and writing may be made simultaneously.
This is not to say that for all mechanisms for reading and writing this is possible. In addition we are looking at the world at the level of discrete behaviour - that is, a continuous implementation involves arbiters.
Argument (N. Sabadini): If it is impossible to read and write at the same time, then it is impossible to listen to someone speaking.
Argument (mathematical): the identity process I, which outputs exactly the signal input, has the property that reading occurs simultaneously with writing. If you require that reading occurs after writing then this process does not act as an identity under composition with other processes - I*P is not P but P with added delay. The identity process is as important for an algebra of processes as zero is for an algebra of quantities.
------------------------------------------------------------------------
Under this assumption about reading and writing Lamport showed in 1974 that mutual exclusion with respect to the memory is not necessary for higher level mutex [A New Solution of Dijkstra's Concurrent Programming Problem, Communications of the ACM 17, 8 (August 1974), 453-455].
Labels: computing
posted by Unknown at 6:25 AM
0 Comments:
Post a Comment
<< Home