3 ms·
The top level comments strategy with queues seems similar, in that it isn't always possible. It requires the queues form a DAG, which is another word for partia
by syrrim 4y ago
The top level comments strategy with queues seems similar, in that it isn't always possible. It requires the queues form a DAG, which is another word for partial ordering. Thus, requiring the locks form a partial ordering doesn't seem like a comparatively excessive restriction.
- chrisseaton 4y ago> doesn't seem like a comparatively excessive restriction I think there are some applications and algorithms that we just don't know a way to create an ordering for realistically fine-grained locks. For example airline seat reservation. Someone clicking on seats to reserve them. You can't apply locks in a total order because... you can't read the person's mind on what seat they're going to click next. Or Lee's algorithm. (I wrote the first half a PhD on this.) https://chrisseaton.com/research-symposium-2012/seaton-irregular-parallelism-poster.pdf https://chrisseaton.com/research-symposium-2012/seaton-irreg...
- anonymoushn 4y agoYou don't need a DAG. It's fine to have a complete graph!