Name
Abstract | ||
|---|---|---|
Linearizability, the key correctness condition that most optimized concurrent object implementations comply with, imposes tight synchronization between the object concurrent operations. This tight synchronization usually comes with a performance and scalability price. Yet, these implementations are often employed in an environment where a more relaxed linearizability condition suffices, where strict linearizability is not a must. Here we provide a quantitative definition of limited non-determinism, a notion we call Quasi Linearizability. Roughly speaking an implementation of an object is quasi linearizable if each run of the implementation is at a bounded "distance" away from some linear run of the object. However, as we show the limited distance has to be relative to some operations but not all. Following the definition we provide examples of quasi concurrent implementations that out perform state of the art standard implementations due to the relaxed requirement. Finally we show that the Bitonic Counting Network non-deterministic behavior can be quantified using our Quasi Linearizable notion. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/978-3-642-17653-1_29 | OPODIS |
Keywords | Field | DocType |
optimized concurrent object implementation,object concurrent operation,limited non-determinism,linear run,quasi concurrent implementation,tight synchronization,improved concurrency,limited distance,quasi linearizable notion,quasi linearizability,key correctness condition | Linearizability,Synchronization,Thread pool,Computer science,Concurrency,Correctness,Real-time computing,Implementation,Theoretical computer science,Distributed computing,Bounded function,Scalability | Conference |
Volume | ISSN | ISBN |
6490 | 0302-9743 | 3-642-17652-6 |
Citations | PageRank | References |
41 | 1.88 | 9 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yehuda Afek | 1 | 1840 | 176.95 |
| Guy Korland | 2 | 80 | 4.73 |
| Eitan Yanovsky | 3 | 41 | 2.21 |