1
$\begingroup$

I have a question about a homework problem. Basically, let's say we have $100$ transactions, and we want to run as many as we possibly can at the same time. We have $20%$ contention.

I want to find out how many out of the $100$ we can run in parallel, on average. I went about it this way:

Say we run the first transaction. Then there are $20$ transactions we can't run. Say we run the $2$nd transaction as well. At worst, there are $16$ others ($20%$ of $100$ - $20$) that we can't add. So after $2$ transactions added to the "run set," we have $62$ options to choose from and we keep going.

I don't think that works, and I wanted a mathematical way to do it. Any help would be greatly appreciated.

  • 0
    As I understand your question, right at the start we can run 80 of the transactions at the same time, and the other 20 conflict in some unknown way. Is this correct?2012-02-27
  • 0
    @Patrick - Sorry I clarified my problem. Essentially, 20% contention suggests that each element conflicts with 20% of the elements.2012-02-27
  • 0
    Suggests, or is defined as? Let $E_{ij}$ be the event that transaction $i$ conflicts with transaction $j$. What, precisely, do you know or can you assume about these events? For example, are they independent?2012-02-28
  • 0
    It is precise. We can create the transactions, and we create 100 active transactions, so we are guaranteed that every transaction will conflict with 20 others. Conflicting transactions can't run at the same time, but that's the only limitation.2012-02-28
  • 0
    It depends on the pattern of mutual contention. In the worst case, you can only run five at a time, where the $100$ come for example in five groups of $20$ mutually exclusive transactions.2012-02-28
  • 0
    Can we not generalize for the average case though?2012-02-28
  • 0
    I don't understand the "20% of 80" in your example. Seems like when we run the first transaction T1, there are 19 others that can't run at the same time as T1. And if we choose the second transaction T2 from among the remaining 80, then there are at worst 19 new ones that can't run at the same time as T2. So now we have only 60 left to choose from for the third transaction T3. That's at worse. But at best T2 conflicts with the same 19 that conflict with T1, so we'd have 79 left to choose from for T3. Is this even close?2012-02-29
  • 0
    Start with probability basics: What is your sample space? What events interest you?2012-03-01

0 Answers 0