From: Rini Kaushik [rinikaushik@yahoo.com] Sent: Thursday, March 11, 2010 12:38 PM To: Gupta, Indranil Subject: CS525 Review 03/11 Rini Kaushik CS 525 Epidemic Algorithms for Replicated Database Maintenance ------------------------------------------------------- The paper describes randomized anti-entropy and rumor mongering algorithms to distribute updates and maintain consistency in the replicas. Pros: 1) Randomized algorithms allow for simplicity in the design 2) Does not require a server to be cognizant of information at other servers Cons: Anti-entropy algorithm seems to have several issues: 1) It requires a comparison of the entire database content for resolving differences. Simple comparison would be exhaustive if the size of the database is huge. And, even though the authors propose checksums and inverted index to alleviate some of the comparison issues, even these situations are not really scalable. For example, if only a small record changes in the database, the entire database will be changed at the neighbor. It would be better to have some sort of incremental update instead of full update. Also, using Rabin fingerprints to identify the differences might be more scalable. 2) If the update rate is too high, the updates may not get reflected on time and may result in inconsistencies in the system. 3) Not sure if this algorithm can handle network partitions 4) It seems that the algorithm assumes single update at a time. What if there are multiple updates occurring in the same time? Rumor-mongering algorithm 1) Not sure how arbitration will be done in deciding which rumor is "hot" in case multiple updates are happening simultaneously. Exploring the Energy-latency Trade-off for Broadcasts in Energy-Saving Sensor Networks -------------------------------------------------------------------------------------- This paper explores the energy-latency-reliability trade-off for broadcast in multi-hop WSNs, by presenting a new protocol called PBBF (Probability-Based Broadcast Forwarding). PBBF protocol uses parameter p to tradeoff latency and reliability and parameter q to tradeoff energy and reliability. Pros: 1) PBBF gives control to the application developers to tune the parameters p and q and hence, allows for application-level control over the energy-latency-reliability tradeoff. Cons: 1) On one hand, giving control to the application developers to tune the system has its advantages. On the other hand, it also has some pitfalls. Results show that a PBBF performs worse than PSM at small values of q. If the applications developers are not cognizant of the right values of p and q, system behavior may degrade. It may be better to have allowed p and q to be self-adaptive. From: pooja agarwal [pooja.agarwal.mit@gmail.com] Sent: Thursday, March 11, 2010 12:34 PM To: Indranil Gupta Subject: 525 review 03/11 DS Review – 03/11/10 By: Pooja Agarwal Paper: Epidemic Algorithms For Replicated Database Maintenance Main Idea: This paper describes several epidemics based randomized algorithms to achieve mutual consistency among various versions of databases maintained at various sites. The approaches discussed in the paper revolve around three basic epidemics algorithms: 1) Direct Mail: Each new update is immediately mailed from it’s entry site to all other sites. Not reliable. 2) Anti-Entropy: A node chooses another node randomly and sends entire database to resolve any difference between them. Reliable however, too costly and slow. 3) Rumor mongering: It is a gossip based protocol in which a node sends hot rumor to random nodes and decreases it’s interest in rumor spreading if the contacted node already knew the rumor. Highly efficient but probabilistic. The paper presents various enhancements on last two protocols such as using checksums, time window based checksums, and keeping inverted time index of database in anti-entropy to reduce the overhead of sending complete database. It also presents various variations of rumor mongering scheme such as Blind: a node loses interest to gossip with probability 1/k regardless of recipient, Feedback: node loses interest with probability 1/k only if recipient already knew the rumor, Counter: interest is lost after k unnecessary contacts happened, Pull: a node contacts other nodes to check if update is available, Push: a node contacts other nodes to find out if other node needs any update. It also presents the tradeoffs involved with using push/pull mechanisms with connection limits. Since, the complex epidemic does not provide guarantee that all the nodes will be updated hence, anti-entropy can be used in background to transfer such updates. For deleting entries from nodes, death certificates are proposed which have two variants, simple death certificates that expire after a threshold in time, and dormant death certificates which are awakened when come in contact with old updates. It discusses the trade-offs involved in complex epidemic algorithms using spatial distribution in account. Pros: 1) This is a seminal work in the application of epidemics algorithm in replicated distributed databases which mentions various approaches and tradeoffs associated with each approach clearly in the paper. 2) The paper presents strong mathematical representation of each problem and the proposed solutions which provide a sound theoretical background. Cons: 1) The paper though gives sound theoretical background; however, it lacks extensive experimentation of the ideas presented in the paper. It would have been good to see how these different variations perform with respect to each other. 2) The paper could have used logical timestamps (Lamport’s clock) instead of global timestamps. I guess, they could have analyzed how different messages could be designed to incorporate logical timestamps briefly in a sub-section or appendix. Discussion Points: 1) Is it applicable and still useful in the current database centers? Considering the paper was published in 1987 so, many of the assumptions are based on the networks present during those days. So, can we use some of these algorithms in distributed cloud computing data centers? 2) How can efficient messages be defined to use Lamport’s clock for resolving timing of a database value so as to avoid synchronization to a global time at each node? 3) Will it be useful if the topology remains constant over time? Intuition is, if the topology is defined and constant then a deterministic approach will be more efficient. 4) What are the tradeoffs when spatial information is used in the epidemic algorithms. Paper: Exploring the Energy-Latency Trade-off for Broadcasts in Energy-Saving Sensor Networks Main Idea: This paper presents PBBF(Probability-Based Broadcast Forwarding) protocol which uses energy-latency trade-off for broadcasting in a sensor networks. It’s discussed that as higher latency is incurred by IEEE 802.11 PSM protocol in which each node broadcasts at the beginning of ATIM window, sleeps for a time window and rebroadcasts in the next wakeup window. These operations are deterministic in approach. However to achieve better energy saving, this paper presents a probabilistic scheme to choose the probabilities when a node can send a packet immediately in current window and when a node can decide to be active when it should ideally have slept. These two parameters are represented by p and q in the paper and these are to be set according to the application demand. The paper covers extensive analytical results for reliability, energy, latency and energy-latency trade-offs. For the analysis they used ns-2 simulator and considered a grid network topology. Through simulation, the analytical model was validated and it was shown that energy consumed increases linearly with q and latency is inversely related to p and q. PBBF uses the bond percolation theory and shows that there is a direct relationship between p and q for a given level of reliability. The effect of node density was also covered in the protocol. Pros: 1) Formulation of analytical model for their scheme and evaluating it through extensive experiments is a key selling point of this paper. The validation of the theoretical results through the evaluation considerably adds to the paper. 2) Since two of the major problems in sensor networks deals with power savings and latency, hence the paper provides a right balance in providing probabilistic way to choose the priority of one over the other. Cons: 1) Assumption of an ideal MAC and physical layer with no collisions and interference, is unrealistic in practice. They could have discussed how the system performs when such collisions and interference occur with their protocol. 2) The evaluation used only max of 50 nodes which is quite less when we talk of large sensor networks. The effect of node density is discussed in a brief paragraph but it is not clear how the protocol performs when the number of nodes/density increases (some simulation might have been helpful). From: Shivaram V [shivaram.smtp@gmail.com] on behalf of Shivaram Venkataraman [venkata4@illinois.edu] Sent: Thursday, March 11, 2010 12:20 PM To: Gupta, Indranil Subject: CS 525 review 03/11 Shivaram Venkataraman - 11 March 2010 Exploring the Energy-Latency Trade-off for Broadcasts in Energy-Saving Sensor Networks This paper presents the Probability Based Broadcast Framework (PBBF), a new protocol which explores provides parameters to achieve a better trade-off between energy, latency and reliability. PBBF is a probabilistic scheme which adds two parameters to any existing energy conserving MAC protocol: i. p - the probability that a node rebroadcasts a packet immediately without ensuring if any of its neighbors are awake. ii. q - probability that a node stays awake during a time duration when it should have been asleep, in expectation that it might be a receiver of an immediate broadcast. By setting different values for p and q, PBBF allows different applications to achieve the right energy-latency-reliability trade-off. Intuitively, a higher value of p means that latency is lowered and reliability is improved. Increasing 'q' would result in a greater energy usage but would increase reliability. Reliability The PBBF model of expressing a broadcast mechanism corresponds to the bond percolation problem in gossip theory. When any two neighboring nodes are awake, it can be said that the edge between them is 'open' and the reliability of PBBF can be equated to discovering the set of nodes that can be reached through the open edges. This leads to the derivation that if the probability that an edge is open p(edge) = 1-p(1-q) and p(edge) is greater than the critical probability, then the reliability of PBBF is high. Simulations prove that there is direct relationship between p and q for a given reliability. Energy Taking into account the extra time that nodes are awake in PBBF, it is found that the energy consumption increases linearly with 'q' and is independent of 'p'. Latency The packet could be delivered in time L1 if both the sender and receiver are awake for an 'immediate broadcast' or in time L1+L2 during the normal broadcast cycle. Additionally in a large network, there could be multiple hops before the packet reaches a node. Simulations show that as q increases and for higher p values, the per-hop latency is lowered. Pros - Protocol is very flexible and offers parameters that can be tuned, as required by specific applications. - The simulation results closely follow the results expected from the analytic model of bond percolation. Cons - It would have been interesting to note which applications would benefit from which chosen values of p and q. - Would be a good experiment to deploy applications like Trickle / TAG on top of PBBF and measure the overall gain. Epidemic Algorithms for Replicated Database Maintenance When a database has many replicas located at geographically separated locations, maintaining the consistency of the database across the replicas is a significant problem. This paper looks at how epidemic algorithms could be used to restrict the amount of network bandwidth used while ensuring that the update reaches every replica. There are three main strategies for replication that are described are: a. Direct mail: Every update is immediately sent from the origin-site to all the other replicas. This technique generates 'n' messages per update and the traffic is proportional to the number of sites times the average distance between the sites. However additional techniques are required to handle sites which are down. b. Anti-entropy: Every site choses another site at random and exchanges the entire database contents with it. This is a reliable scheme but it is very costly to examine the entire database. c. Rumor mongering: Each update is inserted as a 'hot rumor' in the system. A site propagates a 'hot rumor' periodically to another site chosen at random. After noticing that many of its updates have been seen by neighboring sites, the update is removed from the list of 'hot' updates and not propagated anymore. This scheme ensures lower network traffic but there is a chance the update may not reach some sites. There are 3 different ways in which the epidemics based schemes can be used, based on how the updates are originated: push, pull and push-pull. It is found that in practice, pull or push-pull are greatly preferable to push. It is also found that the rumor-mongering method works better when there is feedback from the remote site of whether it already knew the update or not. Furthermore, maintaining a counter which dictates when the propagation is stopped if found to perform better than nodes probabilistically losing interest. Deletions need to be handled differently in this scheme and to prevent old updates from affecting the consistency, a Death Certificate is issued for every delete. This death certificate is propagated like a normal update and then garbage-collected after a specified time period. To reduce the chances that a long lost replica re-instates a deleted record, the death certificates can be kept for a longer duration at certain 'retention sites'. Finally, it is also important that the replication schemes work well with topology of the underlying network. The update propagation should not heavily burden the important links in the network and also ensure that updates are sent reliably to remote sites. Pros - Proposed the model that eventually consistency may be more important than immediately ensuring consistency. Interesting points - The push and pull variants of rumor mongering are more sensitive than push-pull to the combination of non-uniform spatial distribution and irregular network topology. - Disagreement among sites led to more network traffic which in turn leads to a cycle of more disagreement among sites. From: Ashish Vulimiri [vulimir1@illinois.edu] Sent: Thursday, March 11, 2010 12:18 PM To: Gupta, Indranil Subject: 525 review 03/11 Epidemic algorithms for replicated database maintenance, A. Demers et al, PODC 1987. In this paper the authors describe simple, efficient randomization algorithms for the problem of maintaining consistency in a replicated database. They compare three solutions -- i) Direct mail: broadcast every update ii) Rumor mongering: spread updates through a gossip-based algorithm iii) Anti-entropy: nodes randomly pick other neighbors and synchronize with them, either by exchanging copies of the whole database (inefficient), or using more efficient methods such as doing an incremental reverse temporal correlation -- and demonstrate that the rumor mongering approach is the most efficient in terms of network traffic and delay. They then discuss how data deletion can be accomplished with a rumor mongering algorithm, and briefly explore optimizations based on knowledge of the spatial distribution of the nodes. Comments: * They seem to be assuming loosely synchronized timestamps. It is unclear what the exact tradeoff between synchronization accuracy and consistency guarantees is. * Some possible generalizations: -- The push/pull probabilities can be different at different nodes (depending on e.g. the bandwidth available at the nodes) -- Can have different mixes of push and pull. The authors only consider three possibilities: pure push, pure pull, and a 50% mix (every push associated with a pull action), but we can also have varying fractions of push and pull actions depending on network/node conditions. * Their analysis of the effect of network topology/spatial node distribution is fairly preliminary Exploring the energy-latency trade-off for broadcasts in energy-saving sensor networks, M. Miller, C. Sengul, I. Gupta, ICDCS 2005 This paper presents the Probabilistic-Based Broadcast Forwarding (PBBF) protocol, an extension to the MAC layer that allows the user to control the sleep scheduling strategy at the node, and therefore the effective energy-latency-reliability tradeoff, by configuring two simple numerical parameters. The two controllable parameters introduced are i) p, the probability that the node chooses to broadcast a packet immediately without waiting till the start of the next beacon interval (when the nodes are scheduled to wake up), and ii) q, the probability that a node remains active beyond its scheduled sleep time Broadcasting the packet immediately (i.e. a reasonably high value for p) reduces latency, but in order to ensure that at least one node is available to receive the communication, q must be reasonably high, which would increase energy consumption. p and q also directly affect how many nodes receive the communication, and thus the reliability. The authors try to characterize this tradeoff using a theoretical+simulation based analysis of the grid network topology (each node has four neighbours), and validate their results through an experimental evaluation. The analysis and evaluation focus on the broadcast scenario, although it would seem that allowing the user to control the sleep schedule should have a benefit with other communication requirements too (e.g. TAG-like data aggregation). Comments: * Is broadcast (as in end-to-end broadcast, sending out a packet that needs to go to every node on the network, as opposed to a single hop broadcast) a common operation in sensor networks? It seems surprising, given how resource constrained the nodes tend to be. (This may not cover all sensor network applications, but neither of the sensor network data aggregation papers we studied earlier required a full-fledged broadcast.) Again, as I noted above, allowing the user to control the sleep schedule might still help with other communication models. * Possible extension: try to tune the values of $p$ and $q$ dynamically (adaptively), assuming we have some model (say a utility function) of the users' energy and latency requirements. * One thing that wasn't considered was the impact of node failures on the progress of the broadcast, although I'm not sure how significant this is. From: vivek112@gmail.com on behalf of Vivek Kale [vivek@illinois.edu] Sent: Thursday, March 11, 2010 12:04 PM To: Gupta, Indranil Subject: 525 review 3/11 Paper #1: Exploring the Energy-Latency Trade-off for broadcasts in Energy-Saving Sensor Networks Throughout development of WSNs, power consumption has often been neglected in the picture. The tradeoff between energy and latency is established, particularly for broadcast communication. The authors introduce Probability-Based Broadcast Forwarding(PBBF), in an effort to understand and tune applications such that this tradeoff can be explored, and a proper balance between energy and latency can be understood. PBBF operates at the MAC layer, and it can be used along with a sleep scheduling protocol. The authors introduce two parameters, p and q. The q term refers to the probability that a node still remains active, after it is scheduled to sleep. The p term refers to the probability that a node sends or forwards a message as soon as it receives a broadcast message. Pros: -This is one of the few papers where the parameters are varied, so as to understand the best configuration and balance between energy efficiency and latency reduction - The paper addresses applications requiring real-time support (e.g. weather prediction), and PBBF addresses these types of applications well, particularly in terms of issues of latency involved. Cons: - It doesn't seem clear how the energy-latency trade-off will scale to a much larger configuration of nodes. - In the experimental section, it's not clear if there are any dependencies involved between p and q. If there isn't, it doesn't seem to be as well justified to the reader. What if by increasing probability of forwarding (p), the probability that a node still remains active is affected somehow? While this might be assumed, it doesn't seem convincing that this is the case. Paper #2: Bimodal Multi-cast This classic paper identifies some reliability issues in multi-cast protocols, discussing two different ends of the spectrum. One end has to do with atomicity guarantees. This is referred to as all-or-nothing delivery, delivery ordering, etc. The other end relates to "best effort" reliability, where local repair strategies are used to overcome packet loss. This paper introduces the idea of bimodal multi-cast, where the reliabilty model relates to bimodal probability distributions. They aim to show that bimodal multicast has stable performance as well as qualities of reliabity and scalability. Pros: - Rather than focusing on pure performance, this paper rightly takes the viewpoint that performance stability must be a priority in multi-cast protocols. - The paper discusses 6 different optimizations for pbcast, each of which can be applicable in a general sense to any network or infrastructure. This adds to the strength and applicability of the pbcast protocol, and suggests further optimizations that could be made as well. Cons: - While they introduce the two ends of the spectrum very clearly, it's not clear how they can tune their design to find a good balance between the two. They suggest just one protocol as the common ground, but being able to tune the parameter space can make the paper much more applicable. While the experimentation evaluates the system using many different parameters, is there a way to use all these parameters together so as to tune it effectively? - They do discuss additional parameters such as fanout, but this is left as a theoretical discussion point in the appendix. Is fanout not an important part of the experimentation in section 7. - The paper's experimentation is primarily based on NS2 simulations. Would these simulations apply to more real-world scenarios? Are the authors justified in making the claims about real applications as they do in section 8? - They also use fault-injection, which has been shown in previous papers that we have read, to not be as effective for distributed systems, and it's not convincing that these faults are representative of faults in real applications. From: Virajith Jalaparti [jalapar1@illinois.edu] Sent: Thursday, March 11, 2010 10:50 AM To: Gupta, Indranil Subject: 525 review 03/11 Review of “Epidemic algorithms for replicated database maintenance”: The paper deals with the problem of maintaining consistency among several replicated databases in which all of them are intended for the storage of the same data and any of them can initiate an update of a particular entry. It explores the use of simple epidemic algorithms for this purpose and the tradeoff they impose between the reliability with which an update is sent, the time for the propagation of the update through the entire database and the network traffic which results from such update propagation. In particular, they deal with both simple and complex epidemic algorithms: (a) simple epidemic or anti-entropy, in which every site regularly, randomly chooses another site and exchanges its database contents with it; (b) complex epidemic or rumor mongering, in which an update is introduced as a hot rumor (which spreads rapidly). A site that receives a hot rumor periodically chooses another site and sends it to and if it chooses several sites that have already seen the hot rumor, the rumor is no longer hot and it’s spreading stops. The paper further explores different aspects of these basic algorithms, including push, pull and push-pull variations. It also defines how death/dormant certificates can be used to propagate the updates of items being deleted from the system. It also deals with the practical constraint of bounded connectivity and tries to come up to schemes which take the spatial distribution into account. Pros: - The paper explores how epidemic algorithms can be used in maintaining consistency in a distributed database and presents a complete analysis of the pros and cons of the various approaches/mechanisms that can be used for along with the basic algorithms. - It takes into account practical issues like spatial distribution and comes up with a very generalized optimization for choosing probabilities for contacting various nodes that takes this into account. - The mechanism suggested are practical as the authors sight practical experiences with their database which is unique. Comments: - The anti-entropy algorithm presented in this paper requires a pair of sites for exchange their complete databases if they find that they are different. In practice this might impose a large traffic overhead (esp. if different sites sharing the same lan start such transfers simultaneously). It is worth exploring mechanism by which the sites can detect which part of their database has changed and just exchange that. The idea of hash/merkle trees presented in the UseNetDHT paper seems to be applicable here. - The author’s do not try to exploit the knowledge of the topology of the sites. It might be possible to construct routing trees (similar to those in sensor networks) which each child/parent being as close to its parent/child and propagate updates only along the try. Although the authors, present optimizations regarding spatial distributions, they are probabilistic. Deterministic algorithms like the routing tree can end up having more advantages than such probabilistic ones. Note that failures must be dealt with separately in such schemes. - The approach completely goes away from the centralized approach in favor of a completely distributed one - would it be possible to have a sweet spot between the two extremes: for example using clustering, periodic leader election which acts as the central node (cons: single point of failure). It might be the case that combination both of these can lead to better trade-offs than either separately. Review of “Exploring the energy-latency trade-off for broadcasts in energy-saving sensor networks”: The paper provides a generic framework, PBBF, in which the operators for wireless sensor networks can achieve the required tradeoff between energy consumed by the wireless nodes and the latency-reliability of a propagation of broadcast information in the network. It defines two parameters p, the probability that a node transmits a broadcast immediately after it is received and q, the probability that a node remains awake during its sleep schedule in anticipation of a broadcast from one of its neighbors. It is easy to see that while increases the energy consumption of the system (the broadcast because of p can lead to wasted transmission; a node might wake up but not receive a broadcast), it decreases the expected time for an update to propagate through the system. The paper presents analytical results for this mechanism for a grid network using existing work in percolation theory, which provides a constraint in which this mechanism can lead to every node in the network receiving a broadcast. The authors then go on to present results of simulations and show the tradeoff in this mechanism in realistic scenarios in which interference/collisions can be present. The framework provided in this paper is quite generic and can be employed irrespective of the MAC/sleep schedule being used in the network. PBBF allows the network operator to determine the operating point of the network – he can choose the required performance of the network and pay the corresponding increase in energy consumption. The paper tries to take a generic approach without any regard to the sleep schedule. However it is not clear if this is the right approach to solve this problem. It might be the case that a particular sleep schedule/MAC can be better adopted to use such a mechanism (Note that the authors don’t test their mechanism with different MACs/sleep schedules). In particular, considering a particular access/sleep pattern might help to improve the tradeoff provided by this/similar algorithms. Further, in PBBF each node acts on its own. But it might be possible that all the nodes in a single neighborhood cooperate and come up with a probabilistic schedule such that all of them are up with a very high probability at a particular instant of time when the broadcast can be scheduled. However, this new schedule would interfere with the original sleep schedule and result in increased energy usage, resulting in the trade off expected. -- Virajith Jalaparti PhD Student, Computer Science University of Illinois at Urbana-Champaign Web: http://www.cs.illinois.edu/homes/jalapar1/ From: Nathan Dautenhahn [dautenh1@illinois.edu] Sent: Thursday, March 11, 2010 10:27 AM To: Gupta, Indranil Subject: 525 review 03/11 Paper Reviews: March 11, 2010 Nathan Dautenhahn I. Exploring the Energy-Latency Trad-off for Broadcasts in Energy-Saving Sensor Networks Authors: Matthew J. Miller, Cigdem Sengul, Indranil Gupta 1. Summary and Overview This paper approaches the issue of broadcast messaging in wireless sensor networks. The problem is that these networks must be focused on saving energy as much as possible, and as such require attention. The authors propose a new routing protocol called Probability-Based Broadcast Forwarding (PBBF) that uses a probabilistic sleep scheduling algorithm. PBBF has two main pieces of functionality: the ability for a node to immediately send a packet if it has one, and the ability for a node to choose to stay awake to receive a packet if there is a high enough probability of the event occurring. The goal is to provide to the wireless sensor network application designer to use adjust parameters p and q, for immediate send probability and stay awake probability respectively, in ordert to identify what the best trade off is for latency verses energy costs. Another affected attribute is the reliability of a given protocol. 2. Questions, Comments, Concerns My considerations are as follows: • I'm confused how the PBBF works while integrated into the 802.11 PSM. How does the message start? Does node 1 initially get a message from somewhere else? Why does node 1 want to perform a fast transmit? Why include any wake/sleep periods at all? • They propose this work as a mechanisms that can be included into other broadcast protocols, but it appears as thought the protocol is quite complete. Why not just build the whole thing from scratch and get better control, rather than using something like PSM? I question how this will affect the analysis of the two protocols put together. What I mean is that PSM has some type of analytical guarantees, but then we implement PBBF on top of it, it is not considered what affect this will have on the original guarantees of the protocol. • One major assumption that is bad is that they assume perfect synchronization in the network. II. Epidemic Algorithms for Replicated Database Maintenance Authors: Alan Demers, Dan Green, Carl Hauser, Wes Irish, John Larson, Scott Shenker, Howard Sturgis, Dan Swinehart, and Doug Terry 1. Summary and Overview This paper discusses the development of algorithms to perform distributed data backup in the late 80s. The authors focus on the development of three types of algorithms: direct mail, anti-entropy, and rumor spreading. The primary problem that they are facing is the dealing with how to minimize the costs and messages to update remote databases. The major problem with the current algorithms is that they were deterministic, and required centralized control of the update mechanisms. The authors focus on taking these three algorithms and implementing randomized versions of the algorithms, and in the process negate the need for centralized control. A few things that I likes are the deletion and death certificate mechanisms, and the inclusion of spatial considerations into the selection of which hosts to update to. 2. Questions, Comments, and Concerns My considerations are as follows: • This work seems very incremental. The algorithms that they attack are already developed and have been explored. They provide very thorough analysis of theory, but it seems like this work is not quite novel. • Their work assumes that backups are somewhat small and not to frequent, which is a limitation. • This last point brings up an important concept, it is really hard to analyze papers that are this old because the assumptions, the networks, the technology is so different now. This made analyzing this paper somewhat hard because I didn't know what to really attack. III. Common Themes Both of these articles are discussing the idea of using probabilistic and randomized approaches to algorithms. They both implement new randomized schemes for their domains. The domains are different, but this is one common thread amongst the papers. *** Nathan Dautenhahn *** From: Giang Nguyen [nguyen59@illinois.edu] Sent: Thursday, March 11, 2010 10:26 AM To: Gupta, Indranil Subject: 525 review 03/11 CS525 review nguyen59 03/11 Exploring the Energy-Latency Trade-off for Broadcasts in Energy-saving Sensor Networks In wireless sensor networks, broadcasts of messages are useful to perform synchronization, routing tree construction, disseminating sensor data, instructions, and code updates. The simplest approach is to flood the network, which is inefficient because as each node broadcast, a node might receive multiple copies of the same packet from its neighbors. However there are more intelligent other protocols to perform broadcasts. Furthermore, wireless sensor nodes employ some MAC-layer sleep scheduling to conserve energy by putting the radio to sleep, during which time the node will miss packets. The idea is to use a time interval to signal intention to send packets, then neighbor nodes will stay on to receive the packet during the "active time". Otherwise they put their radios to sleep mode. In order to rebroadcast a received packet, a node has to wait until the next cycle to ensure that all its neighbors know about its intent to broadcast and to stay on to receive its packet. And! t! he nodes might still receive redundant copies of broadcast packets. This paper presents Probability-Based Broadcast Forwarding (PBBF), which strives to ensure that with high probability, a node receives at least one copy of each broadcast packet, while reducing the latency due to sleeping. It introduces two parameters: 1. "p" is the probability that a node rebroadcasts a packet in the current active time despite the fact that not all neighbors might be awake to receive its packet, which represents the trade-off between latency and reliability, and 2. "q" is the probability that a node remains on after the active time when it normally would sleep, which represents the trade-off between energy and reliability. This idea can be integrated into any kind of sleep scheduling protocol such as IEEE 802.11 PSM. Cons: - Assumes perfect synchronization in the multi-hop network. Since these coin flips regarding the probability parameters "p" and "q" likely use some kind of pseudo-random number generator on the sensor node, I wonder how the protocols would behave if some nodes picked the same "p" and "q" and generated the same sequence of coin flips. From: Jayanta Mukherjee [mukherj4@illinois.edu] Sent: Thursday, March 11, 2010 10:24 AM To: Gupta, Indranil Subject: 525 review 03/11 Epidemics Jayanta Mukherjee NetID: mukherj4 Epidemic algorithms for replicated database maintenance, A. Demers et al, The authors described several randomized algorithms for distributing updates and driving the replicas toward maintaining mutual consistency of the databases replicated across many sites. The algorithms are very simple and require few guarantees from the underlying communication system. The cost and performance of the algorithms are tuned by choosing appropriate distributions in the randomization step. In this work, the authors analyzed, simulated and develop some practical strategies for spreading updates by the following methods: Direct mail: each new update is immediately mailed from its entry site to all other sites. Anti-entropy: every site regularly chooses another site at random and by exchanging database contents with it resolves any differences between the two. Rumor mongering: sites are initially “ignorant,“; when a site receives a new update it becomes a “hot rumor”; while a site holds a hot. rumor, it. periodically chooses another site at random and ensures that the other site has seem the update. In the complex epidemics analysis, the authors used rumor spreading analogy and they were principally concerned with Residues, Traffic and delay. Pros: 1.This paper provides a lot of mathematical details which can be very useful in studying similar scenarios. 2.Anti-entropy is extremely reliable, although it falls in the Simple epidemics category. But, the authors stretch their analysis for Complex Epidemics, using rumor spreading techniques. 3.Rumor spreading has been used in the analysis in deterministic fashion. 4.Using rumor mongering instead of direct mail would greatly reduce the expected cost of redistribution. Rumor mongering generates less network traffic than introducing the rumor at a single site. 5.The authors made a nice observation that, anti-entropy behaves like a simple epidemic led us to consider other epidemic-like algorithms such as rumor mongering, which shows promise as an efficient, replacement for the initial mailing step for distributing updates. A backup anti-entropy scheme easily spreads the updates to the few sites that do not receive them as a rumor. Cons: 1.Rumor mongering is suitable for simple cases in which only a few sites fail to receive an update. 2.Neither the epidemic algorithms nor the direct mail algorithms ran correctly spread the absence of an item without assistance from death certificates. 3.Pathological network topologies has not been studied Comments: The experiments has been conducted on relatively larger systems, like, the Clearinghouse servers of the Xerox Corporate Internet, so, results are convincing. Exploring the energy-latency trade-off for broadcasts in energy-saving sensor networks, M. Miller, C. Sengul, I. Gupta: The authors described a new protocol called PBBF (Probability-Based Broadcast Forwarding). PBBF works at the MAC layer and can be integrated into any sleep scheduling protocol. The authors explored the energy-latency-reliability trade-off to broadcast in multi-hop WSNs. In this paper, problems related to broadcast has been addressed. They defined two probability p and q as follows: 1.p: The probability that a node rebroadcasts a packet immediately without ensuring that any of its neighbors are active 2.q: The probability that for a given node and a given time instant when it is supposed to be asleep due to its active-sleep schedule, the node instead stays awake in the expectation that it might be a receiver of an immediate broadcast. The authors showed that, using the bond percolation model, the two knobs, p and q, introduced by the PBBF protocol can be tuned to explore the energy-latency trade-off primarily for some particular region. The reliability of PBBF protocols can be analyzed using percolation models. The authors have presented, analyzed, simulated, and measured the performance of a class of probabilistic broadcast protocols for multi-hop WSNs. Pros: 1.The proposed PBBF works with MAC protocol, so no new protocols are needed for adopting PBBF strategy. It is an efficient probabilistic approach for broadcasting. 2.The analysis and simulation study quantify this relationship at the reliability boundary, as well as performance numbers to be expected from a deployment. 3.Energy-latency trade-off allowed by the protocols for different levels of reliability has been analyzed thoroughly in this work. 4.Fine-grained MAC-level simulation results have been used to quantify the performance numbers for a code distribution application that use broadcasts in WSNs. 5.PBBF essentially offers a WSN application designer considerable flexibility in choice of desired operation points. Cons: 1.According to the PBBF protocol, nodes have to stay active, regardless of their active-sleep schedules, based on the q parameter. 2.PBBF can improve reliability, but, how it impacts the performance has not been explicitly told and also, on similar note it can be said that, how performance can be improved for a probabilistic scheme like PBBF is really significant. Comments: All the results and based on the simulation on NS-2, which is just a simulator. So, how the probabilistic approach (PBBF) will provide more reliability on a real-time system is yet to be studied. -With regards, Jayanta Mukherjee Department of Computer Science University of Illinois, Urbana-Champaign Urbana-61801, IL, USA Mobile:+1-217-778-6650 From: gildong2@gmail.com on behalf of Hyun Duk Kim [hkim277@illinois.edu] Sent: Thursday, March 11, 2010 3:22 AM To: Gupta, Indranil Subject: 525 review 03/11 525 review 03/11 Hyun Duk Kim (hkim277) * Exploring the energy-latency trade-off for broadcasts in energy-saving sensor networks, M. Miller, C. Sengul, I. Gupta, ICDCS 2005 This paper presents a new protocol called PBBF, Probability-Based Broadcast Forwarding. Due to the constrained resources on sensor networks, they use various techniques for resource savings like energy saving. Instead of existing all or nothing sleepmode scheduling, PBBF uses two new parameters p and q. p is the probability that a node rebroadcasts a packet immediately without ensuring that any of its neighbors are active, and q is the probability that a node decides when it is supposed to be asleep. Authors executed various analyses on energy and latency trade-off and simulation using proposed algorithm. This paper well analyzes the proposed algorithm with various related factors. Authors show how p and q affects on reliability, energy and latency with equations. Also, they show energy-latency trade-off and how users should select p and q in practice. At last, they show simulation results of the proposed algorithm. As it is briefly suggested as one of the future works, dynamic adjustment of p and q is a good idea to improve the proposed algorithm. Authors suggest changing p and q depending on activities of each node. In addition to the activity history, each node may consider its energy level. That is, the node with low energy level should adjust p and q to have more sleep mode. * Epidemic algorithms for replicated database maintenance, A. Demers et al, PODC 1987. This paper introduces simple randomized update distribution algorithms. When a data is replicated a many sites, maintaining consistency among sites becomes issues. In this situation, designing efficient, robust and scalable update propagating algorithm is very important. Direct mail, sending notification to all sites, is the simplest way. Anti-entropy randomly checks differences between two databases and updates if they are different. Rumor mongering randomly selects nodes to send update messages. With basic three ideas, authors show several variations and compare pros and cons. This paper introduces basic epidemic algorithms with detail explanations. This is a pretty old and classic paper about epidemic algorithms. This paper well introduces simple updating methods with detail explanations. In addition to the basic algorithm description, authors suggests various options with trade-off explanations; e.g. death certificates, considering spatial distribution, blind vs feedback, counter vs coin and push vs pull. Authors use easy interesting intuitive terms for explaining algorithm operations. Authors use terms from epidemics like infected and susceptible. Terms like death certificates and dormant also make readers feel fun and understand intuitively. For efficiency of anti-entropy protocol, we may use update log. Drawback of anti-entropy is its big cost to compare entire database. Authors suggests using checksum, however, it still does not solve the problem. As a simple solution, each node may keep software update logs and compare them for checking difference. ------ Best Regards, Hyun Duk Kim Ph.D. Candidate Computer Science University of Illinois at Urbana-Champaign http://gildong2.com From: ashameem38@gmail.com on behalf of Shameem [ahmed9@illinois.edu] Sent: Thursday, March 11, 2010 1:57 AM To: Gupta, Indranil Subject: 525 review 03/11 ================================================================================================== Paper 1: Exploring the Energy-Latency Trade-off for Broadcasts in Energy-Saving Sensor Networks ================================================================================================== Reeducation of power consumption is one of the biggest challenges in WSN. However, for some applications (e.g. short term event detection, realtime data flow, etc.), latency becomes an important issue. In the paper titled "Exploring the Energy-Latency Trade-off for Broadcasts in Energy-Saving Sensor Networks", the authors identified that, power and latency are inversely related in WSN. To explore and quantify such trade-off, the authors proposed a new protocol called PBBF (Probability-Based Broadcast Forwarding). PBBF works in MAC layer and it can be adapted with any sleep scheduling protocol. To design PBBF, the authors introduced two parameters to sleep scheduling protocols: p and q. When a node is scheduled to sleep, it will remain active with probability q. And when a node receives a broadcast, it sends it immediately with probability p. The authors detailed the trade-off through both analytical and simulation results. Pros: 1. The idea of PBBF is simple yet effective protocol. 2. PBBF can be used with standard MAC protocol as well as with any protocol adheres the active-sleep cycle. 3. PBBF doesn't require any extra hardware. Cons / Discussion Points: 1. The evaluation didn't consider the collision and interference, which is very common in real-world WSN. 2. In simulation, the authors assumed that, perfect synchronization is present in the multi-hop network. Perfect clock synchronization is surely a challenging problem. How to achieve such perfect synchronization? Can we use any logical clock (e.g. Lamport clock, Vector clock) for that purpose? 3. Rather than considering immediate broadcast, which might cause large contention and interference, can we modify Beacon Interval size dynamically? 4. How power-latency trade-off will be affected with the increase of number of nodes? 5. What will happen if gossip based routing (site percolation) is used instead of broadcasting (node percolation)? 6. Is it possible to use a hybrid of site percolation and node percolation? 7. The authors considered grid-based network topology which might not be a realistic scenario. What will happen if PBBF is deployed in non-grid based network topology? ================================================================ Paper 2: Epidemic Algorithms for Replicated Database Maintenance ================================================================= The paper titled "Epidemic Algorithms for Replicated Database Maintenance" is a classic paper in distributed system. In this paper, the authors proposed some randomized algorithms based on the idea of epidemic for distributing database updates and driving replicas towards consistency. The authors mainly proposed three algorithms which are very simple yet effective. Those algorithms are: Direct mail, Anti entropy, and rumor mongering. In case of direct mail, as soon as a node gets an update, it mails to all other nodes. This algorithm is very fast and efficient, but not reliable. In case of anti-entropy, each node regularly chooses another node at random and then exchanges their update. This algorithm is very reliable bit slow and expensive. The final algorithm is called rumor mongering where, as soon as a node gets an update, it randomly picks another node and shares the update. This algorithm is less reliable and less expensive as compared to anti-entropy. Besides proposing these algorithms, the authors also described how to propagate the deletion. At first, the authors showed why deletion propagation is not as simple as insertion propagation and then they showed their "death certificate" and "dormant death certificate" approach to solve this. Finally, the authors showed how spatial distribution can be useful for their proposed algorithms. Pros: 1. I think this is the first attempt to use epidemic algorithms to maintain the database replication. 2. The proposed algorithms don't require much guarantee from the underlying network. 3. The proposed algorithms are very simple (both for understanding and implementing) yet effective. 4. One of the algorithms was implemented in Xerox clearinghouse. Cons/Discussion Points: 1. The algorithms don't provide 100% guarantee that all nodes will have the updates. 2. In case of anti-entropy, a new update needs to be checked with old update. This checking requires having clock synchronization, which is very difficult in a distributed system. Perhaps, logical clock might be better option in this case. 3. The topology information and nodes are pretty much static. Is it possible to exploit this static property to come up with deterministic algorithms? 4. How about scalability of dormant death certificate algorithm? From: liangliang.cao@gmail.com on behalf of Liangliang Cao [cao4@illinois.edu] Sent: Thursday, March 11, 2010 12:46 AM To: Gupta, Indranil Subject: 525 review 03/11 CS525 reviewed on Epidemics Liangliang Cao (cao4@illinois.edu) March 11, 2010 Paper 1: A. Demers et al, Epidemic algorithms for replicated database maintenance, PODC 1987. This paper considers the problem of maintaining mutual consistency in the database with multiple replications. Several randomized algorithms are discussed which ensure that all replicas are updated. These algorithms are closely analogous to epidemics: (a) direct mail algorithm, which mail every new update from its entry to all other sites. This is timely and reasonably efficient, but not reliable and sometimes leads to mail lost. (b) anti-entropy: every site randomly choose another site at random and resolves any differences between the two. Anti-entropy is extremely reliable but very costly. From simulation, reliable anti-entropy methods propagate much slower than direct mail. (c) rumor mongering: ignorant sites become “hot rumor” when receives a new updates, but stop treating the rumor as hot after too many sites told that they have already seen it. A hot rumor will be randomly sent to another site frequently, and stop propagating when it is regarded as “not hot”. Rumor mongering is efficient and also propagates fast, however, there is some chance that an update will not reach all sites. This paper employs epidemics models to analyze the three algorithms with potential different settings. Pros: (1) It is novel to use epidemic concept to analyze the problem of maintaining database consistency. (2) The performance on Xerox servers looks promising. Cons: (1) This paper does not consider the situation when two replica are modified in short interval by different requests. In this case, method (b) (c) might only keep the changes of a single action but not all. A better way is to employ methods (a) and (c) in the same system for different kinds of requests. (2) I wonder whether it is possible to propagate the epidemic in a group-fashion. In other words, we first divide sites into several groups, and build one “server” for each groups. A direct mail propagation is first propagate among these servers, and then rumor mongering is performed within each group. Paper 2: M. Miller, C. Sengul, and I. Gupta, Exploring the energy-latency trade-off for broadcasts in energy-saving sensor networks, ICDCS 2005 This paper considers the energy-latency-reliability trade-off for broadcast WSNs. It proposes Probability-Based Broadcast Forwarding (PBBF), which offers a WSN application designer considerable flexibility in choice of desired operation points by introducing two new parameters: (1) p: the probability that a node rebroadcasts a packet immediately without ensuring that any of its neighbors are active and (2) q, which is the probability that for a given node and a given time instant the node instead stays to receive an immediate broadcast. Pros: (1) The parameter of PBBF provides flexible interface for choose the appropriate trade-off for different applications (2) It is an intuitive but interesting observation that “given the level of reliability, the latency and the energy are inversely related”. In addition, this paper convinces this observation by quantitative studies. Cons: (1) To understand better energy-latency trade-off, it might be useful to take the environment factor into account. When there exist multiple path effects or high pack missing rates, we might expect the latency will be worse and it will be meaningful to quantitatively study these effects. (2) With the environment changes, the fixed p and q parameters might not work well for ever. It will be interesting to design adaptive way of adjusting p and q automatically. From: Shehla Saleem [shehla.saleem@gmail.com] Sent: Wednesday, March 10, 2010 11:06 PM To: Gupta, Indranil Subject: 525 review 03/11 Broadcasts in Energy-Saving Sensor Networks This paper presents a different look at the energy-latency-reliability tradeoff for broadcast in Wireless Sensor Networks: A probabilistic approach to understand and explore this crucial tradeoff along with a precise analysis. They present Probability Based Broadcast Forwarding (PBBF), which is a MAC layer approach designed to be energy aware and to be flexible enough to provide the user with a variety of operating points to choose from. PBBF makes two modifications to any MAC layer sleep protocol. First, a node probabilistically (with probability p) rebroadcasts a packet without knowing whether its neighbors are up or asleep. Second, a node probabilistically (with probability q) chooses to stay awake in a slot where it is scheduled to sleep. PBBF tunes these two parameters to explore the energy-latency tradeoff. The experiments are very thorough and provide detailed insights into how the protocol works and the improvements therein. The results provide detailed insights into the interactions of the parameters p and q with characteristics like reliability, energy consumption, latency etc. One enhancement, as has been identified in the paper too, is to explore the possibility of changing p and q dynamically as the network evolves. Nodes can do this on their own too, based on neighborhood information and some level of overhearing to get some idea of the network density etc. The biggest contribution of the paper, however, is that it provides control knobs to deal with the energy-latency-reliability tradeoff. Such kind of a control is very attractive since it can provide a basis to build on more sophisticated features eg the provision of a guaranteed Quality of Service to nodes that are willing to pay more in terms of the energy currency and so on. Differentiated services can be incorporated based on user demands etc. Epidemic Algorithms for Replicated Database Maintenance This paper presents several solutions for maintaining consistency in a highly replicated database. Maintaining consistent information becomes a concern when a large database is replicated at many sites and is frequently updated. Ideally, the updates should reach all the sites in the minimum possible time and the algorithm should not generate prohibitive amounts of traffic. These requirements define a kind of tradeoff. The paper presents analysis, simulation results and real world experience of three main update dissemination solutions that cover the spectrum of efficiency, reliability and timeliness. Direct Mail is the first algorithm where an update is sent out as soon as it becomes available. This solution lies at the high end of efficiency and timeliness spectrum but reliability can be low. On the other hand, Anti Entropy makes the database with randomly chosen sites. It is reliable, but total consistency may be achieved very slowly and may consume more resources since the whole database needs to be exchanged. This may make it unsuitable for being done frequently and it may be reasonable to use it as a backup with some other algorithm. They talk about using Push: an updated site explicitly tells a remote site to perform an update. Pull, on the other hand requires checking to see if the remote copy is more recent in which case an update is done locally. Push may be more useful when many sites need to get updated whereas Pull fits better in the scenario where most sites are up to date and only few need to be updated. A combination of push-pull may also be used. One way to cut down on the resources required by Anti Entropy is that instead of exchanging the whole database, sites can exchange some kind of checksum to see if they differ and then exchange the whole database only if a difference is found. Other optimizations include maintaining recent updates and exchanging those or maintaining inverted index of the database with respect to timestamps and exchanging information in the reverse order. Finally, Rumor Mongering exchanges only hot rumor updates and therefore uses lesser resources but is less reliable too. They paper uses three metrics to evaluate performance: Residue which is the number of sites not updated in the end. Secondly, they look at the traffic generated or required by an algorithm to maintain consistency and finally they consider the delay in receiving the updates. Overall, the paper provides a detailed study of the different ways of achieving consistency in large replicated databases. The paper is readable and provides an easy to understand look at both the problem and the solution. One key achievement of the paper is that the algorithms presented in it do not require any support or guarantees from the underlying communication protocols. It might be interesting, however to see if these solutions would work in the wireless scenario. The differences might be due to frequent node failures, packet losses which can even be bursty and so on. From: Fatemeh Saremi [samaneh.saremi@gmail.com] Sent: Wednesday, March 10, 2010 10:37 PM To: Gupta, Indranil Subject: 525 review 03/11 Paper 1: Epidemic Algorithms for Replicated Database Maintenance Maintaining mutual consistency among all the sites each containing a copy of a replicated database is a challenging problem. This paper aims at designing efficient and robust algorithms that scale well. Three different approaches are investigated in this paper: Direct mail, Anti-entropy, and Rumor mongering. In direct mail, each new update is immediately mailed to all other sites. In anti-entropy, every site regularly chooses another site at random and compares the content of the database of that site with its own; the sites will apply the updates if different. In rumor mongering, each new update acts as a hot rumor and is propagated through the network of sites; each site periodically chooses other sites at random and tells them the new update. Hearing from too many sites that they already know about the update, the site ceases the update propagation. Direct mail is timely and efficient, but unreliable. Anti-entropy is reliable but very expensive and therefore, cannot be done too frequently and is much slower than direct mail. Rumor mongering requires fewer resources and hence can be done more frequently, however there exists some probability of unreliability. They investigate the behavior of epidemic approaches through epidemic theory and simulation, and propose utilizing more complex epidemic algorithms like rumors instead of the simpler ones like anti-entropy (both are simple in implementation, however, different in efficiency and cost). They propose to use anti-entropy as a backup for rumors mongering. Then they mention about (Dormant) Death Certificates and spatial distributions to deal with distributed deletion and non-uniformity of cost of sending updates to different distances in the network. Two important issues they focus on in their analyses are the time the algorithms take to provide consistency, the required network traffic, and the residue (the remaining susceptibles when the algorithms finish). Utilizing epidemic approach for database maintenance is very interesting and the authors have explained and compared different aspects of different choices very well, e.g., push, pull, or push-pull. Using epidemic approach, though interesting, does not sound a good solution when the network is not highly dynamic. Topology information of the network can be exploited for designing much more effective algorithms. Paper 2: Exploiting the Energy-Latency Trade-off for Broadcast in Energy-Saving Sensor Networks The paper presents the trade-off between energy consumption and latency as well as reliability level of communication. They introduce two parameters p, the probability that a node broadcasts immediately regardless of the other nodes if they are awake or not, and q, the probability that a node stays awake at a time interval it was supposed to be asleep based on its schedule. Utilizing these parameters they propose a probability-based protocol called PBFT Probability-Based Broadcast Forwarding which works at MAC layer and can be integrated into any sleep scheduling protocol. They have studied their approach theoretically and presented the requirements on parameters for achieving different levels of reliability. They have performed a thorough simulation study of their protocol as well. The idea of the paper is very well presented and the energy-latency-reliability trade-off of the approach has been studied thoroughly which provides application designers the opportunity of making appropriate design decisions for tuning the system. Though probability-based sleep scheduling is not a new solution, the contribution of the paper is quantifying the resource-performance trade-off. Adaptively setting values of the probability parameters would make it more appropriate. From: ntkach2@illinois.edu Sent: Wednesday, March 10, 2010 8:34 PM To: Gupta, Indranil Subject: 525 review 03/11 Nadia Tkach – ntkach2 CS525 – paper review 9 Epidemics Paper 1: Epidemic Algorithms for Replicated Database Maintenance The paper describes a few algorithms that ensure consistent and accurate data replication and update distribution across multiple servers or data stores. The authors analyzed three main types of distribution schemes, they are direct mail, anti-entropy, and rumor mongering. Direct mail is the simplest but probably the greediest algorithm, it is based on broadcasting the updates to all sites, although it can’t handle missing messages, doesn’t verify if the information up-to-date and creates a high network traffic. Anti-entropy works in a way that each server that receives an update randomly chooses another server and compares its database state checksum with its own. When both servers are up-to-date the checksums should be identical, otherwise the two servers perform push, pull or push-pull operation to ensure the consistency and accuracy in data between the two. Rumor mongering is considered a complex epidemic and works such that it randomly chooses another server and ensures that it has seen the latest update. The algorithm stops when it encounters a certain number of positive responses. The rest of the paper describes and analysis new additions and improvements to these algorithms such as death certificates, dormant death certificates, spatial distributions, etc. Pros: • While anti-entropy and rumors are slower in their nature, they still guarantee that the consistency between servers will eventually be reached • Reduce the amount of traffic on the network Cons: • Rumors can’t handle very well dynamic network topology • The time to propagate changes to all servers might be higher than the appropriate period on a particular network. Consider the case when the updates are generated at higher rate when they can be propagated to all sites • In my opinion these still are partially greedy algorithms Paper 2: Exploring the Energy-Latency Trade-off for Broadcasts in Energy-Saving Sensor Networks The paper describes a new Probability-Based Broadcast Forwarding (PBBF) protocol that works at MAC layer, and is based and integrated with sleep scheduling protocol. PBBF takes in p and q values, which are respectively the probabilities of a node rebroadcasting a message in current active time and a node staying awake in its sleep time interval. Using these values a designer can tune up the network system in order to meet the threshold value and achieve the most appropriate energy-latency-reliability trade-off of broadcast. The authors conclude that p represents the trade-off between latency and reliability and q is trade-off between energy and reliability, they analyze, test and evaluate these trade-offs, and make their final proposal on the optimal trade-off values. Pros: • Allows to manually adjust p and q values to a specific system to achieve the best trade-offs • Can save energy, reduce latency and improve reliability in certain cases Cons: • While the protocol seems to be quite generic, it is not suitable for all network systems. In some cases you can see a worse performance when q is small than PSM protocol. The protocol is more robust when values of p and q increase. • Consider modifications to the protocol to create dynamic values of p and q based on the history of encounters and traffic. Also consider different values of p and q for different nodes. From: gh.hosseinabadi@gmail.com on behalf of Ghazale Hosseinabadi [ghossei2@illinois.edu] Sent: Wednesday, March 10, 2010 6:13 PM To: Gupta, Indranil Subject: 525 review 03/11 EPIDEMIC ALGORITHMS FOR REPLICATED DATABASE MAINTENANCE This paper considers the problem of maintaining mutual consistency among the sites in which the data base is replicated at the event of data updates. This paper presents some randomized algorithms to solve this problem. These algorithms are similar to some methods in epidemiology. Each database update is injected at a single site and must be reflected to several hundreds or thousand sites. Important parameters in design of such algorithms are as follows: 1. Time needed for an update in all sites 2. Network traffic generated after each update In this paper the authors presented and compared three methods: 1. Direct Mail: each update is immediately mailed from its entry site to all other sites. 2. Anti-entropy: every site regularly chooses another site at random and their data bases are compared such that updates are exchanges. 3. Rumor mongering: sites are initially ignorant. When a site receives a new update it becomes a hot rumor. A hot rumor periodically chooses another site at random and ensures that the other site has received the update. After enough number of update exchange the site is not anymore a hot rumor. Both Anti-entropy and rumor mongering are inspired from epidemiology algorithms. The authors also discussed how an item is deleted in a database using death certificates. Death certificate includes time stamp that determines if an item should be deleted or not. Centralized and distributed methods for finding the correct threshold are discussed. The distributed method they use is called dormant death certificates. Pros: In this work, randomized algorithms for replicated database consistency are discussed and compared. Randomized algorithms mainly avoid flooding of the whole network of sites. The paper shows that these algorithms are quite efficient in exchanging updates, compared with deterministic algorithms, while by efficiency we mean efficient both in time and also number of messages exchange. This paper mainly presents the power of randomized scheme. Theoretical performance analysis of different methods are presented. Cons: No comparison with semi-randomized algorithms is provided. In different fields it is been shown that semi-randomized methods perform better compared with pure-randomized methods. By semi-randomized method, we mean method in which some steps are deterministic while some are random. None of these methods are robust to malicious sites that might try to inject wrong updates to the sites. Exploring the Energy-Latency Trade-off for Broadcasts in Energy-Saving Sensor Networks In this paper, energy-latency-reliability trade-off for broadcasting in multi-hop wireless sensor networks is presented. The authors designed the whole protocol called PBBF (Probability-Based Broadcast Forwarding) to achieve their design objectives. PBBF is based on active-sleep cycle method. In this method, nodes are in active phases and sleep phases periodically. Moreover, PBBF uses the redundancy in broadcast communication and forwards packets using a probability-based approach. The main design goal is to ensure that, with high probability, a node receives at least one copy of each broadcast packet. A node rebroadcasts a packet in the current active time with probability p. On the other hand, a node remains on after the active time when it normally would sleep with probability q. Changing p tunes the trade-off between latency and reliability. Changing q tunes the trade-off between energy consumption and reliability. The authors find a bound on the value of p and q to achieve high reliability. By high reliability we mean that the broadcast is received at infinitely many nodes. They also find the relationship between energy consumption of PBBF and q, relationship between latency and p and q and also trade-off between latency and energy consumption. They also verified their equations through simulations. Pros: The performance objectives (high energy consumption, low latency) are obtained by tuning two probabilities p and q. Theoretical analysis to show the relationship of energy consumption and latency with p and q are presented. Simulations for understanding the effect of p and q on performance in presented. Cons: It is not clear why p and q should be two independent variables. Maybe if they are some how related to each other higher performance can be achieved. They shouldn’t be picked independently a priori. In other words, better energy-latency trade-off might be obtained by tuning only one parameter (for example p), while the second parameter is a function of the first one (p=f(q)). Their designed method can not be incorporated to the existing deployments of sensor networks, since the authors completely designed a new protocol. So, if it is going to be used in practice, the whole protocol stack in nodes might be changed. Other solutions in the literature that can be used in the existing 802.11 protocol are more applicable in practice. Given an objective value for latency (L) and energy consumption (E), equations should be centrally solved to find p and q that achieves these objectives. In other words, sensor nodes can not find corresponding p and q by themselves. A central authority should inform them those values. In networks where such an authority doesn’t exist, nodes can not figure out best p and q. Distributed methods for finding p and q seems interesting. From: Ashish Vulimiri [vulimir1@illinois.edu] Sent: Wednesday, March 10, 2010 12:33 AM To: Gupta, Indranil Subject: 525 review 03/09 Hi Indy, Sorry, I forgot to email you my review earlier. I did submit a paper copy on time though. Thanks, Ashish TAG: A Tiny Aggregation service for ad-hoc sensor networks, S. Madden, et al, OSDI 2002 The authors present the Tiny Aggregation service, a framework that allows users to obtain aggregate information from TinyOS ad hoc sensor networks using simple SQL-like declarative queries. In particular, they model the information in the entire network as a single unmodifiable relational table, and allow the users to obtain information by exeucting SELECT queries on this virtual table. These queries allow computing several aggregate functions, such as AVERAGE, COUNT etc., and the authors describe how these values may be computed efficiently in the network over the routing tree. They evaluate the performace of TAG using a simulation-based analysis and a small-scale experimental setup. + This seems to be one of the earliest papers on data aggregation in WSNs -- and evaluated from that perspective its contributions seem very novel. - It is not clear if they chose the tree model because it was what TinyOS networks use, or if it was because trees are truly the best choice for supporting the network requirements they impose (viz., paths between the source and every other node, and no message duplication). - The tree model seems like a poor choice efficiency-wise. A single node failure can cause a large amount of route recomputation. Also, in the evaluation section, it would have been useful to see message/computation overhead figures for failures (they only measured the effect failures had on the /accuracy/ of the computed values). - The evaluation section seems somewhat weak. The simulation-based analysis is fine, but some metrics (such as energy-efficiency) can only be realistically evaluated on a live deployment. - Related to above: they don't consider energy-efficiency at all. An evaluation of energy usage would be useful. - They don't investigate the optimizations they propose very thoroughly. E.g.: with caching, it is not clear what the tradeoff is between efficiency and the accuracy of the aggregate value. Synopsis diffusion for robust aggregation in sensor networks, S. Nath et al, ACM TOSN, 2008. The authors present synopsis diffusion, a novel aggregation mechanism for WSNs that works by separating the message routing problem from the data aggregation problem. The authors present energy-efficient algorithms that are capable of calculating the values of aggregate functions (such as count, average etc.) of the data at the sensor nodes even when messages are duplicated. This enables using redundant multipath topologies which are more resilient to network and node failures than, for e.g., the simple tree structures that TAG uses. They present formal proofs of the correctness of their algorithms, and demonstrate efficiency, accuracy and energy-efficiency using results from an extensive simulation study. Comments: * The authors argue that using broadcast doesn't really add to energy consumption at the sender, which is true, but broadcast could cause an increase in the total number of messages processed in the network -- and higher message complexity => higher message processing overhead (both computational and network overhead) => higher energy consumption. * Synopsis diffusion can handle omission and crash failures, but it might also be possible to extend to general Byzantine failures. There are known approximation algorithms -- such as the MSR family first defined by Nancy Lynch et al -- for computing COUNT and AVERAGE (not sure about the other functions) in asynchronous fully connected networks, as well as in some other special topologies; it might be useful to see how well these methods extend to the WSN scenario. * The programming model is not as well developed as in TAG. The most significant missing component is support for partial/conditional queries (such as those by using the GROUP and HAVING clauses in TAG), although it does not seem like this would be too problematic to implement in synopsis diffusion.