Talk:Concurrency (computer science)

From Wikipedia, the free encyclopedia

 This article is within the scope of WikiProject Computer science, which aims to create a comprehensive computer science reference for Wikipedia. Visit the project page for more information and to join in on related discussions.
Start rated as Start-Class on the assessment scale
Top rated as Top-importance on the assessment scale

Contents

[edit] Safety and liveness

The words safety and liveness have an exact meaning in the context of concurrency. I cannot get at my source -- the handouts for a summerschool course taught by Robin Milner -- but it would be great if someone else familiar with this can provide more formal definitions. The following are informal definitions from what I recall, which I may eventually include in this article if no one objects:

Safety: The state of a concurrent system in which no constraints on any shared resource are being violated. An example of a violation may be a lack of effective exception handling in response a failed attempt to insert data into an already full queue. More simply the safety property can be stated as: "Something bad does never happen"

Liveness: The ability of a concurrent system to remain active, namely, to not halt. From the previous example, an unhandled exception would either hang the system, or terminate its execution althogether. Such a system would not have the liveness property. The word liveness corresponds to the original meaning in computer science of the word robust. Unfortunately, robust has been overhyped and conflated.

More simply the liveness property can be stated as : "Something good will eventually happen"

Vonkje 15:45, 31 August 2005 (UTC)

This discussion concerns the following text that had since been deleted:
Its base goals include safety and liveness which impact non-functional properties like reliability. Higher-level goals involve quality of service criteria that seek to optimize throughput and response time. Vonkje 16:39, 26 September 2005 (UTC)
By contrast, quality of service, throughput, etc. are primarirly engineering terms. We need to talk about both the theoretical underpinnings of concurrency and implementation issues. But mixing and matching terminology is not really a good idea. Greg Woodhouse 14:14, 28 March 2007 (UTC)

Safety and Liveness are important theoretical concepts that I think ought to be incorporated into the article, but their definitions are a bit subtle. for one approach, see Nancy A. Lynch, "Distributed Algorithms", pp. 218-220. Greg Woodhouse 14:08, 28 March 2007 (UTC)

[edit] Concurrency wikiproject

I have put up a proposal for a concurrency wikiproject at User:Allan McInnes/Concurrency project. Input from all interested parties (especially those who will actually contribute) is most welcome. --Allan McInnes 21:32, 20 January 2006 (UTC)

I was persuaded that we'd be better off coordinating through Wikipedia:WikiProject Computer science. --Allan McInnes 01:15, 28 January 2006 (UTC)

[edit] Temporal logics

I'm unfamiliar with the tree logics mentioned here but I'm guessing that they are temporal logic with branching time. If that is so, shouldn't the text be modified so as to indicate that they are a type of temporal logic? Or, for that matter, maybe we should only mention that temporal logic may use either branching or non-branching time, and drop the specific references? Greg Woodhouse 05:24, 27 March 2007 (UTC)

I'm afraid that I don't understand. Doesn't the text already talk about the tree logics as being types of temporal logic? (And yes, they are branching-time logics) Apparently not in a clear enough fashion, I guess. Please feel free to rewrite to make this fact more clear. I'd rather include the specific references, since (a) LTL and CTL in particular are both important, especially for things like model-checking, and it's nice to give readers a direct reference to them, and (b) making specific references also makes it possible to highlight the difference between state-based and action-based logics. --Allan McInnes (talk) 06:41, 28 March 2007 (UTC)

Fair enough. As a non-specialist, I don't think I had ever seen the specific term tree logic before, but I suppose it's self-explanatory. I don't think there's any need to change anything. Greg Woodhouse 12:37, 28 March 2007 (UTC)

[edit] References and Further Reading

I added one more title to the Furter Reading section, namely Blackburn, et al. I don't think this needs to become a long list of links, but this seems to me to be an essential reference. By all means, use it as a reference in the body of the article if you feel it is appropriate. Greg Woodhouse 13:07, 28 March 2007 (UTC)

I also have a technical question: I note there are multiple references to the same work in the body of the article. In XML, if you assign an id attrribute, later refeences to the same object can use the ref attribute (ref=ID). Is the same syntax supported on the Wiki? The superscripts a b c in reference [1] look a bit odd to me. Being a newcomer to Wikis, I'm not sure if that's intended behavior, or a side-effect of reproducing the references in full. Greg Woodhouse 13:15, 28 March 2007 (UTC)

Oops. Yeah, I guess I did end up repeating myself a bit there. I'll clean that up now. But the multiple superscripts will still appear, even if I use names to refer to an already-defined full reference - that just seems to be the way the Wikipedia citation handler works. --Allan McInnes (talk) 01:56, 29 March 2007 (UTC)

[edit] Representation Theorem

Shouldn't there be some discussion of the Representation Theorem? It's one of the fundamental unifying principles of the different models?--24.23.212.54 04:19, 4 April 2007 (UTC)

I assume that you are referring to the Actor representation theorem (not the million and one other representation theorems out there). As far as I know, it is only applicable to the Actor model. While one might speculate that it is equally applicable to other models of concurrency, I am not aware of any published material which demonstrates that applicability. To claim that it's "one of the fundamental unifying principles of the different models" seems premature, since it hasn't actually been used to provide any kind of unification between the different existing models of concurrency.
If we were going to discuss unifying approaches to understanding different models of concurrency, I'd suggest that Lee and Sangiovanni-Vincentelli's Tagged Signal Model, or some of the work by Nielsen and Winskel on using category theory to relate different models of concurrency, would be a more appropriate choice, since the published literature on them actually does demonstrate some kind of unification of different models.
--Allan McInnes (talk) 06:50, 4 April 2007 (UTC)

[edit] Merge?

Does anyone who knows more about this article think it could be merged with Concurrent computing or does the interaction make a big difference?

Joe Llywelyn Griffith Blakesley talk contrib 14:14, 4 June 2007 (UTC)

Concurrent computing largely deals with implementation issues. Thr study of concurrency includes theoretical aspects that don't enter into concurrent computing, and is also a broader topic (having recently been applied to areas as diverse as systems biology and business process modeling). I don't think that the articles should be merged. --Allan McInnes (talk) 02:44, 5 June 2007 (UTC)