----------------------- REVIEW 1 ---------------------
PAPER: 82
TITLE: Effectiveness of Delaying Timestamp Computation
AUTHORS: Sandeep Kulkarni and Nitin Vaidya
Overall evaluation: 1 (weak accept)
----------- Overall evaluation -----------
The authors define the notion of inline timestemps for capturing causality,
and show that it more efficient than online (vector clock) timestemps.
That is, the size of the timestamps can be reduced by exploiting
knowledge about the underlying communication topology. They show that:
(1) for a graph with vertex cover VC, there is an inline timestamps
which contains only 2|VC|+2 elements (the number of elements is the size of the clock),
and (2) the size of a timestamp for any event is at most
log n +(2|VC|+1)log(K+1)) bits (n is the number processes and K
is the number of events per process).
Unlike online timestems, in inline timestemps it is not required that
a permanent timestamp is assigned as soon as an event is created, and
the timestamps are not compared using the standard vector clock comparison.
As pointed out (page 1) online and Offine timestamps can be viewed as
two extreme instantiations of the inline timestamps.
All the motivation/benfits for using inline timestamps is
discussed only in the Appendix. That is, examples regarding the feasibility
of using inline timestamps for solving several problems.
For these examples, do you need the inline timestamps or maybe the
special case of offline timestamps is sufficient?
Lamprot's happens-before relation is extensively used by never defined.
Inline timestemps is an interesting concept and might have practical applications.
The subjects is relevant, the presentation is reasonable but can be improved.
----------------------- REVIEW 2 ---------------------
PAPER: 82
TITLE: Effectiveness of Delaying Timestamp Computation
AUTHORS: Sandeep Kulkarni and Nitin Vaidya
Overall evaluation: 2 (accept)
----------- Overall evaluation -----------
The paper addresses the callenge of reducing the size of the vector clock needed to track causality by leveraging knowledge on the network topology and also on when timestamps are needed. It offers results for online and inline algorithms.
The paper has merits and addresses a non trivial problem. The results for the inline algorithm are of particular interest. In fact that authors show than in the online case, for several topologies, few savings can be achieved.
The inline algorithm is more intricate. In fact, although it allows to reduce the size of the timestamps it requires additional communication. I particular, nodes in the vertex cover need to send control messages when receiving data messages. Even if these control messages can be piggybacked with the next data message, they contribute to an increase in the size of the metadata carried in each data message. This somehow defeats one of the goals of this sort of algorithm, that is to reduce the amount of metadata that needs to be piggybacked with each message (and local storage is general not a major issue, unless when using vert resource contrained devices). It would be interesting could include a discussion of this tradeoff.
Still, despite the shortcomings above, I find that the paper offers and interesting twist on the strategies to keep track of causal order in distributed systems.
Finally, I find that there apperas to be some connection with the work of [RV], where a nodes in a cut can filter metadata from one partition, when sending a message to the other partition, by sending a control message to the other nodes of the cut.
[RV] Luís E. T. Rodrigues, Paulo Veríssimo: Causal Separators for Large-Scale Multicast Communication. ICDCS 1995: 83-91
----------------------- REVIEW 3 ---------------------
PAPER: 82
TITLE: Effectiveness of Delaying Timestamp Computation
AUTHORS: Sandeep Kulkarni and Nitin Vaidya
Overall evaluation: 1 (weak accept)
----------- Overall evaluation -----------
This paper asks whether we can detect causality in an asynchronous message-
passing system using timestamps that are smaller than vector clocks, by
exploiting the structure of the network, i.e., which nodes can communicate
directly. (If all-to-all communication is possible, a lower bound of $n$
entries by Charron-Bost exists.) The paper shows that the answer is
negative, and so proposes "inline timestamps", a relaxation of causality
detection in which the timestamp of an event gets computed some time after
the event. The paper shows an algorithm with inline timestamps of 2V+2
entries, where V is the size of some vertex cover of the network.
The construction exploits the fact that happens-before chains have to go
through the vertex cover. Suppose (for simplicity) that we have a ring;
the center assigns a unique time to each of its events, and timestamps at
radial nodes contain an interval [A,B], where A is the latest value of
the center's time that the radial node is aware of, and B is the time at
which the center hears about the event. (This is why B cannot be assigned
by the radial node when the event occurs.) Then events are concurrent iff
their intervals overlap. (The actual construction generalizes this using
vector clocks inside the vertex cover.)
The paper also shows how its inline timestamps can be used in some
applications: predicate detection and replay/recovery
Strengths:
+ Fresh perspective on a fundamental and much-studied problem.
+ Nice and non-trivial algorithm.
Weaknesses:
- The work is conceptually quite similar to the lazy replication work of
Ladin et al.
- The algorithm seems needlessly complicated (see below).
I liked this paper because it has a new twist on an old problem. But
I don't know if the results constitute an improvement on prior work or are
simply different. This work relies on a small set of nodes---the vertex
cover---to relay all communication, and thus it proxies causality detection
onto these relay nodes. But if this is the case, why not use the vector
clock at the first relay as an event's timestamp? (Which would be the
straightforward generalization of lazy replication.) Why do we need this
new algorithm? I don't have a good answer except for "because it's new,"
and I don't know if that's enough for PODC.
Comments to the authors:
* Is there some parameter in which your algorithm is better than the
straightforward solution above? The current discussion on lazy
replication just says that (1) timestamp comparison is different, and
(2) that lazy replication assumes a clique of servers whereas you don't.
But I don't see how (2) is important: you assume a connected network,
so any node in the vertex cover (VC) can talk to any other node in the
VC.
* It would be good to discuss whether inline timestamps can support another
important application of vector clocks: dependency tracking (i.e.,
holding off on merging a remote update into the local state until all
of its dependencies have arrived). I think that they can, because the
VC node that forwards a message can embed the original event's "post"
field inside, but maybe I'm missing something.
Minor comments:
* On page 3: "By event $e^i_{n-2}$" should be "By event $e^0_{n-2}$"
* Figure 1: after "If e is a local/send event at C", shouldn't all
occurrences of $ctr_j$ be $ctr_C$ instead?
* Figure 1: after "If e corresponds to receiving m at C", shouldn't
occurrences of $ctr_j$ be $ctr_C$ instead?