COMMENTS -------- p22: The last two paragraphs of Section 2.1 would become more clear if it were remarked explicitly that: (1) the definitions are with respect to one execution of the entire system (2) the precedence relation on events (and intervals) spans concurrent threads (3) intervals are defined only for events on the same thread p84: The read() method in Fig 4.12 should at line 23 not write the value to a_table[me][me]. Because it is a single-writer register, and the writer is already writing to the diagonal. Moreover, else the resulting MRSW register is not regular, as shown by the following scenario: - thread A_k reads locations a_table[i][k], and picks a value v with largest timestamp t - the writer writes (w,t+1) to a_table[k][k], and completes - A_k writes (v,t) to a_table[k][k], and returns v - A_k in a subsequent read returns v again p87: "register values that existed together in the same system state." Here "existed" should be "can have existed". The actual execution is linearizable to one in which the returned register values existed together. p101: In Def 5.1.1, "consensus protocol" should read "consensus protocol for $n$ threads" p115: In the proof of Thm 5.7.1 it should be stated that $v$ is the value of the register. (This also helps to clarify the quantifications in Def. 5.7.1; one might wrongly think that either all functions should commute or all functions should overwrite.) p132, Fig 6.7: Thread 7 does not try to help thread 2 at the start, because thread 2 announces its node later. And thread 7 does not try to help thread 2 after winning the consensus on the node with sequence number 2. Thread 7 should then try to help thread 3 instead (if it had announced a node). p186, Fig 8.10: The FifoReadWriteLock does not guarantee FIFO. A thread that is woken up first, may not get the lock first. This could be remedied by changing line 10 of Fig 8.10 into lock = new ReentrantLock(true); because then the longest waiting thread will get the lock after a signalAll(). p199: "it must be the case that if the abstraction map is applied to the representation at the linearization points, the resulting sequence of states and method calls defines a valid sequential set execution." It is not fully clear what is meant here. For instance, the linearization point for a successful add() for FineList, on p204, is when the 2nd node is locked; but the abstraction map only takes this add() into account when the link of the 1st locked node is redirected. I do not understand how this discrepancy between linearization points and abstraction map is in line with the description above. p202-203: It would be more clear if the initialization of nodes pred and curr were the same in the implementations of add() and remove() (lines 4,6 of Fig 9.6 versus line 30 of Fig 9.7). p204: In the paragraph on remove(a): - when the predecessor node is locked -> when the node containing a is locked - A successful call (a absent) -> An unsuccessful call (a absent) - the last sentence of this paragraph should move to the paragraph on add(a) p205: Since the next two synchronization paradigms are not starvation-free, it might be remarked that say a Bakery algorithm, to guarantee that each thread can eventually get the lock of the head, makes FineList starvation-free. p208: It might be remarked that OptimisticList is deadlock-free (because an unsuccessful validation means some other thread is successfully added or removed). p211: "Logical removal requires [...] logically or physically deleted." The same paragraph (minus half a sentence) can be found on p209-210. (In this paragraph, instead of "referred to by", it might be more clear to write "in", as else this might be confused with a reference between nodes.) p211: "The linearization points for LazyList [...] are the same as for the OptimisticList." Linearization points for OptimisticList were not discussed. p216: It would be helpful if it were explained in the text why Window uses get() to obtain reference and mark in one atomic operation. Would it not be possible (and more insightful) to replace it by an isMarked() followed by a getReference()? p217: The sentence "If the compareAndSet() call fails" (see errata of the authors) is unclear, because the previous sentence implicitly refers to another compareAndSet() call. p217: The short remark about "one small change" to contains() is hard to comprehend; get(marked) and marked[0] did not yet appear outside the figures. Also I do not see why get(marked) is needed here. Could lines 39-43 in Fig 9.27 not be changed into while (curr.key < key) { curr = curr.next.getReference(); } return (curr.key == key && !curr.next.isMarked()) p218: The compareAndSet() in Fig 9.26, line 27, is hard to understand. In principle one could in Fig 9.26 (I think) replace the lines from 26 on by the following steps: - apply getAndSet() to set the mark of curr to true, and obtain its previous value - if the mark was true, return false - if the mark was false: * succ = curr.next.getReference() * pred.next.compareAndSet(curr, succ, false, false) * return true However, getAndSet() on only the mark is not supported by the AtomicMarkableReference class. I guess that is the reason for applying compareAndSet() instead? p218: Should the linearization points of LockFreeList not be discussed? p225: I do not see why enqLock and deqLock must be reentrant. There does not seem to be a scenario in which a thread acquires enqLock or deqLock in a nested fashion. p231: "Its iplementation prevents method calls from starving" This suggests that the unbounded queue does not suffer from starvation, while it is lock-free but not wait-free. p232: it checks whether that node has a successor -> it checks whether that node has no successor (or in the next line: If so -> If not) p247: It would be more precise to make line 3 (instead of line 4) the linearization point of a pop() on an empty stack, because a concurrent push could complete between lines 3 and 4. p233: The linearization point of an unsuccessful deq() cannot be fixed at EmptyException() (Line 33 of Fig 10.11). If execution of this line is very slow, a successful enq() could in the meantime be invoked, and complete. p371: The split() method seems to implicitly assume that n is even. And the classes in Fig 16.3 and 16.4 seem to require that n is a power of 2. p383: The role of isEmpty() in Fig 16.10 is unclear. It does not re-appear anywhere (except for the discussion on linearization on p386). p386: "We linearize [...] popBottom calls when bottom is decremented or set to 0" I'd think successful popBottom's are linearized when it turns out bottom > oldTop, or compareAndSet succeeds, and unsuccessful popBottom's when compareAndSet fails. With the linearization points you propose, an unsuccessful popBottom may be linearized before a successful popTop that took the last task in the queue. p402: "The barriers so far either suffer from contention or have excessive communication." It is not clear to me why the static tree barrier improves on this. In case of a cache coherent architecture, the sense-reversing barier seems just as fine. In case of a cacheless NUMA architecture, the static tree barrier suffers from contention, or increased communication because notifications must be propagated down the tree. p405: In Fig 17.10, line 19, why is the counter (of the parent, see line 11) decremented with a getAndDecrement? A simple decrement seems sufficient. p423: It would be helpful if regarding Fig 18.6 a reference were given to Fig 8.5. p480: "The CAS call will replace e with v, but the application may not have done what it was intended to do." This should be removed, the same was said the line before. (It is slightly confusing that first an address is called a, and values e and v, and next values are called a,b,c. But this may have been done to explain the name of the ABA problem. By the way, in the description of CAS on p113, e and v are called e and u.) TYPOS ------ p-xvii: Michael Sipser is mentioned twice in the same ack Pearlman -> Perlman p3: references the end -> references at the end p22: threads typically -> Threads typically p24: some thread make p27: if one thread runs completely before the other -> if one thread never tries to get the lock p48, lines 2,6 of Fig 3.3: head=0 and tail=0 is done twice p48, line 4 of Fig 3.3: (T[])new p55: Empty Exception -> EmptyException p60: the cost ... are p85: In the description of Fig 4.13: reads a_table[0][1] => reads a_table[1][0] reads a_table[3][1] => reads a_table[1][3] p87: linearizable to) -> linearizable) to p106: can provide -> can we provide all the consensus protocol p108: for a threads p117: provides a get() -> provide a get() p129, Fig 6.5: Thread 2 appends -> Thread 7 appends Thread 7 loses -> Thread 2 loses p132: 1 mod n+ -> + 1 mod n p135: announced). thread C p149: the the critical section p151: its its own p181: until C leaves the critical section -> until D leaves the critical section p185, Fig 8.9: since the unlock() method does not take the lock, in principle it will get an IllegalMonitorStateException, as it signals without holding the monitor lock p187, Fig 8.12: idem (this unlock() method is erroneously missing a signalAll()) p188, Fig 8.13: Lines 14-22 should placed within try { ... } finally {lock.unlock} p189: initialze p197: any any ordered set p206: line 6: <= should be < p207: locking in line 58 should be before the try finally block p209: nodes has been -> node has been p214: Figure 9.22: The LazyList class -> Figure 9.22: The LockFreeList class p218: Fig 9.27, line 36: false{} -> {false} 40 curr = curr.next -> 40 curr = curr.next.getReference() is the almost the same again as when -> again when p219: The Lock-free p227: last line of the first paragraph: enqueuers => dequeuers p229: decremented by deq() -> incremented by enq() incremented by enq() -> decremented by deq() It would be good to remark that after adding deqSideSize to enqSideSize, the enqueuer resets deqSideSize to 0. p230, Fig 10.10: add a closing bracket } p232: "help"other p235: thread 1 observes -> thread A observes p236: line 5 of Fig 10.16 seems to be redundant, stamp[0] is not used. p237: the enqueuer then sets -> the enqueuer sets p249: If if fails p254: calls). -> calls. p255: EliminationArray [118] -> EliminationArray [120] (?) p317: and 25, and -> and 23, and p369: a_{ki}\cdot b_{jk} -> a_{ik}\cdot b_{kj} p374: line 56: bb[0][i] -> bb[0][j] line 58: aa[1][i], bb[i][1] -> aa[i][1], bb[1][j] p375, Fig 16.6, l8: arg > 2 -> arg > 1 p376, Fig 16.7 and p380, Fig 16.8: two of the fib(1) boxes should be named fib(0) p381: an overloaded task -> an overloaded thread p383: The pushBottom() method should throw an exception if bottom == capacity. reference the top and bottom -> reference the bottom and top p384: Thief A tries to increase top from 3 to 4, instead of decreasing it to 2. Moreover, thread B removes all tasks, so that top is set to 0. In the description of this scenario, 3 could be replaced by 0, and 2 by 1. removed a task that is already complete -> stolen a task that has already been completed, and removed a task that will never be completed p385, Fig 16.12: should the array not extend to place 0? p386: and the task has been claimed -> and the task has been claimed by the caller the the caller only rarely when -> only rarely, when p391: that that other threads p399: balancer's sense field -> barrier's sense field p401: $n=r^d$ threads -> $n=r^{d+1}$ threads p402: in the last two barriers -> in the last barrier p407: Lines 8 and 10 of Fig 17.13 should be exchanged (and corrected in the text on p406) p410, Fig 17.16, line 21: if (parent != null) should be only around parent.await(sense) in line 23; otherwise a node that arrives at the active side of the root does not wait p419, Fig 18.3, line 7: expected[i] -> expect[i] p420, Fig 18.4: the code where a thread helps another when multiCAS() fails is left out p422: Fig 18.5, line 12 should read: tail.next = node; another queue q0 -> another queue q1 p423, Fig 18.7, line 3: deq(x) -> enq(x) p424: walking though search first though p433: synchronization, These p435: symmetrically.). p436: seqential object (twice, in Fig 18.21) the a second object p447: placed in the cache -> placed in the cache line p469: We studied many ways -> We will study many ways p475: cache. and p480: discussed in detail in Chapter 16 -> discussed in detail in Chapter 10 p481: Hennessey -> Hennessy p484, in [14]: shared-money -> shared-memory (mistake in DBLP and IEEE Explorer) p489, in [103]: authors and title are duplicated p492, in [142]: Special Issue (10) -> 10(2) p496: sense-serving -> sense-reversing p498: Consenus protocols, generic EXERCISES --------- p41, exercise 9: It seems to me that the Peterson algorithm provides first-come-first-served, if line 9 of Fig 2.6 (victim = i) is included in the doorway. Maybe this is a trick question, and the answer is r=0? (Bertrand Meyer takes only line 8, flag[i] = true, as the doorway, and concludes that r=1.) p94, exercise 40: At the top of p75 a regular register is defined to be single-writer. While in this exercise, you ask to make the multi-writer register victim regular. p95, last line of exercise 41: atomic -> regular (?) At this point it was already concluded that even with a single writer the register is not atomic. p97, exercise 46: flickering -> regular p119, exercise 55: consensus protocol -> wait-free consensus protocol I guess the intention of the exercise is to show, using Lemma 5.1.3, that wait-free consensus is impossible. p119, exercise 57: 5.7 -> Fig. 5.7 p137, exercise 80: construction shown here -> wait-free universal construction to to append p137, exercise 82: A small addition -> In Fig. 6.6, a small addition p193, exercise 98: active method -> active thread p220, exercise 102: add() -> contains() (?) On p204, the linearization points for add() are already discussed, and the linearization points for contains() are promised as an exercise. p220, exercise 105: fine-grained -> coarse-grained (?) On p200, the implementation of contains() for the coarse-grained algorithm is promised as an exercise. p221, exercise 117: never finds -> may find same key -> key it is looking for its new added object -> the item it wants to add with same key -> with the same key p241, exercise 120: in lines 2,5 of Fig 10.20, head=0 and tail=0 is done twice A Lock-free p393, exercise 186: 65 steps -> 65 seconds p393, exercise 188: fastest -> longest I guess you want students to compute an upper bound for T_{10}. p394, exercise 190: Fig. 16.14 -> Fig. 16.4 Fig. 16.4 -> Fig. 16.5 (?) p395, exercise 191: I fail to do better than a critical path length of (log n)^2 (because the critical path length of vector addition is log n). p395, exercise 193: BoundedDEQueueoverflow p395, exercise 194: A reference should be given to Fig 16.15. p411, exercise 203: combining tree barrier -> tree barrier Fig. 17.6 -> Fig. 17.18 ERRATA ------ Finally, to start a new thread ErrataInErrata, some typos in the errata: p84: it is stated that line 32 should be "a_table [0][i] = value;", but this will make the writer write the values on the first row only. p137 ``Exercise 80 -> p137 ``Exercise 77 p156 First paragraph -> p157 Second paragraph p429 In Fig 18.16 -> p429 In Fig 18.15