tag:blogger.com,1999:blog-199044882024-03-07T23:34:51.423-08:00Mundaú - Distributed Computing (or not)<p>Ideas, opinions and curiosities about distributed computing and related (or not) research topics.</p>
<a href='http://en.wikipedia.org/wiki/Munda%C3%BA_Lake'>What does <i>Mundaú</i> mean?</a>Elizeu Santos-Netohttp://www.blogger.com/profile/01894064232549942032noreply@blogger.comBlogger69125tag:blogger.com,1999:blog-19904488.post-71326751096823190102011-10-26T15:41:00.000-07:002011-10-26T15:46:10.017-07:00This blog is movingDear reader,<br /><br />This blog is moving to a new address. Please update your subscriptions to: <a href="http://blogs.ubc.ca/elizeu/">http://blogs.ubc.ca/elizeu</a>Elizeu Santos-Netohttp://www.blogger.com/profile/01894064232549942032noreply@blogger.com0tag:blogger.com,1999:blog-19904488.post-69918939346067363162011-03-23T10:32:00.001-07:002011-03-24T22:02:52.216-07:003MT CompetitionRecently, the <a href='http://www.ece.ubc.ca'>ECE Department</a> joined a Campus-wide initiative: <a href='http://www.grad.ubc.ca/3-minutes-change-world'>the Three Minutes Thesis Competition</a>. <br /><br />It was a really fun event (see <a href='http://www.ece.ubc.ca/news/201103/3mt-competition-winners'>3MT Competition Winner</a>)! More importantly, we had the chance to discuss the projects other graduate students are working on. I'm looking forward for the next round.Elizeu Santos-Netohttp://www.blogger.com/profile/01894064232549942032noreply@blogger.com0tag:blogger.com,1999:blog-19904488.post-91939460695256652412010-12-01T01:54:00.001-08:002010-12-26T23:46:41.167-08:00Theory Tuesdays -- What do Wikipedia, car-pooling, couch surfing, and social bookmarking have in common?Last fall, I worked for four months in Google, Zürich. It was a fun and enriching experience, indeed. The opportunity to learn and contribute to the technology that is used by millions of people daily is quite exciting. <br /><br />Besides enjoying the Google-life, during my days in Zürich, I was invited by two artist friends, <a href='http://amarelo.ch'>Silvan Käelin</a> [1,2,3] and <a href='http://www.philipmatesic.com/'>Philip Matesic</a> [4,5,6]), to give a talk about my PhD thesis research at <a href='http://perla-mode.net/'>Perla Mode</a> -- as part of the <a href='http://theorytuesdays.blogspot.com'>Theory Tuesdays</a> project. <br /><br />Philip organizes a weekly event at Perla Mode named Theory Tuesdays. The goal is to bring together artists, researchers (of multiple disciplines), and the public to discuss a variety of topics such as art, technology, society, and their intersection. <br /><br />I received the invitation with surprise and interest. It was a new experience to talk to an audience completely outside my field of research. Also, it was a chance to receive feedback (from such non-technical group) about what I think it is a relevant topic of study. <br /><br />The idea was to have a middle ground between what I have been investigating (i.e., <a href='http://doi.ieeecomputersociety.org/10.1109/SocialCom.2010.69'>techniques to assess the value of contributions in peer production systems</a> [<a href='http://www.ece.ubc.ca/~elizeus/papers/santos_neto_SIN-10.pdf'>pdf</a>]) and a the broader topic that could interest the attendance.<br /><br />Therefore, it seemed appropriate to introduce the notion of <a href='http://theorytuesdays.blogspot.com/2010/11/session-45-tuesday-november-16-2010.html'>peer production systems</a> [7], hint the questions I am interested in answering in this context, and asking the participants related questions such as: how do they perceive the value of information they consume online? do they often perceive themselves contributing to others by producing information online? what is the main incentive to do so? What are the aspects they take into account to decided whether an information provider produces value to them?<br /><br />I am glad that the "talk" turned into a lively conversation about about all these questions and other aspects related to online peer production. We covered topics from the basic notion of social production (and why it works so well in certain scenarios), passed through specifics about the utility of tagging (e.g., classification languages may emerge through collaboration), and talked about the intuition behind the techniques I am designing to assess the value of contributions in social tagging systems. <br /><br />Although anecdotal, it was possible to observe from the discussion two explicit trends on the perception of value of online peer-produced information: <i>novelty</i> and <i>trust on the information producer</i>. These aspects came up in the discussions as crucial to the users to assess the value of peer-produced information. It is important to note that the information consumer's interest is an implicitly aspect considered in the value assessment. <br /><br />The observations are somehow intuitive, but for me it was quite important and helpful to have a first-hand discussion with the real users of the systems I study. It does help one to tune the questions to ask and where the relevancy of one's research. I hope to have more opportunities like this. Thanks to Silvan and Philip for the first one.<br /><br />References: <br /><br />[1] <a href='http://amarelo.ch/index.php?/oneman/about-the-project/'>One Man</a><br />[2] <a href='http://amarelo.ch/index.php?/lagoa/o-mundo-cultura-e-natureza/'>Lagoa do Ouro</a><br />[3] <a href='http://amarelo.ch/index.php?/works/temps-de-poussiere/'>Temps de Poussiére (Time of Dust)</a><br />[4] <a href='http://www.philipmatesic.com/page_6C706564786E7575457E787F75817A747470424345454C3D887A8180594D4E515852.html'>An Bonus</a><br />[5] <a href='http://www.philipmatesic.com/page_6C706564786E7575457E787F75817A747470424345454C3D887A8180594D4E515858.html'> Mau Series</a><br />[6] <a href='http://www.philipmatesic.com/page_6C706564786E7575457E787F75817A747470424345454C3D887A8180594D4E51585A.html'> To Don Pedro with Mr. Gonzalez</a><br />[7] Y. Benkler. "<a href='http://cyber.law.harvard.edu/wealth_of_networks/Main_Page'>The Wealth of Networks: How Social Production Transforms Markets and Freedom</a>"Elizeu Santos-Netohttp://www.blogger.com/profile/01894064232549942032noreply@blogger.com0tag:blogger.com,1999:blog-19904488.post-10561848952532070342010-10-01T02:34:00.000-07:002010-10-01T02:44:18.475-07:00The Small World of File SharingThe <a href="http://www.computer.org/portal/web/tpds">IEEE TPDS</a> has recently published a preprint of an interesting piece of work that I had the pleasure to collaborate with. <br /> <br /><a href="http://www.cse.usf.edu/~anda">Adriana Iamnitchi</a>, <a href="http://www.ece.ubc.ca/~matei">Matei Ripeanu</a>, <a href="http://www.ece.ubc.ca/~elizeus">Elizeu Santos-Neto</a>, <a href="http://people.cs.uchicago.edu/~foster">Ian Foster</a>, "<a href="http://doi.ieeecomputersociety.org/10.1109/TPDS.2010.170">The Small World of File Sharing</a>," IEEE Transactions on Parallel and Distributed Systems, 28 Sept. 2010. IEEE computer Society Digital Library. IEEE Computer Society.<br /> <br /><span style="font-weight:bold;">Abstract</span>:<br /><br /><blockquote>Web caches, content distribution networks, peer-to-peer file sharing networks, distributed file systems, and data grids all have in common that they involve a community of users who use shared data. In each case, overall system performance can be improved significantly by first identifying and then exploiting the structure of community's data access patterns. We propose a novel perspective for analyzing data access workloads that considers the implicit relationships that form among users based on the data they access. We propose a new structure —the interest-sharing graph— that captures common user interests in data and justify its utility with studies on four data-sharing systems: a high-energy physics collaboration, the Web, the Kazaa peer-to-peer network, and a BitTorrent file-sharing community. We find small-world patterns in the interest-sharing graphs of all four communities. We investigate analytically and experimentally some of the potential causes that lead to this pattern and conclude that user preferences play a major role. The significance of small-world patterns is twofold: it provides a rigorous support to intuition and it suggests the potential to exploit these naturally emerging patterns. As a proof of concept, we design and evaluate an information dissemination system that exploits the small-world interest-sharing graphs by building an interest-aware network overlay. We show that this approach leads to improved information dissemination performance.</blockquote>Elizeu Santos-Netohttp://www.blogger.com/profile/01894064232549942032noreply@blogger.com0tag:blogger.com,1999:blog-19904488.post-83240777050694429112010-07-08T06:27:00.000-07:002010-07-08T06:48:11.453-07:00Assessing the Value of Contributions in Tagging SystemsDuring the past two and a half months, I have been visiting the <a href='http://www.inweb.org.br'>InWeb/UFMG</a> at Belo Horizonte - MG - Brazil. Besides enjoying the great 'Cozinha Mineira', in this opportunity, we studied the problem of assessing the value of contributions in social tagging systems, and took the first steps towards a solution. The ideas will be presented in an article at the <a href='http://www.iisocialcom.org/conference/socialcom2010/ws_sin-10.html'>2nd IEEE International Symposium on Social Intelligence and Networking (SIN-10)</a> in 20-22August 2010. Next stop: to give a talk at the <a href='http://www.lsd.ufcg.edu.br'>Laboratório de Sistemas Distribuídos (UFCG)</a>. <br /><br /><blockquote><b>Abstract</b> -- Assessing the value of individual users' contributions in peer-production systems is paramount to the design of mechanisms that support collaboration and improve users’ experience. For instance, to incentivize contributions, file-sharing systems based on the BitTorrent protocol equate value with volume of contributed content and use a prioritization mechanism to reward users who contribute more. This approach and similar techniques used in resource-sharing systems rely on the fact that the physical resources shared among users are easily quantifiable. In contrast, information-sharing systems, like social tagging systems, lack the notion of a physical resource unit (e.g., content size, bandwidth) that facilitates the task of evaluating user contributions. For this reason, the issue of estimating the value of user contributions in information sharing systems remains largely unexplored. This paper introduces this problem and takes the first steps towards a solution. More precisely, it presents a framework to design algorithms that estimate the value of user contributions in tagging systems, proposes three complementary success criteria for potential solutions, and outlines the methodological evaluation challenges. </blockquote>Elizeu Santos-Netohttp://www.blogger.com/profile/01894064232549942032noreply@blogger.com3tag:blogger.com,1999:blog-19904488.post-53093035054242460432010-01-29T15:39:00.000-08:002010-02-11T14:00:38.839-08:00Object-to-Object SimilarityRecently, I read a paper published at <span class="blsp-spelling-error" id="SPELLING_ERROR_0">VLDB</span>'2008 titled: <span style="font-style: italic;">Accuracy Estimates and Optimization Techniques for <span class="blsp-spelling-error" id="SPELLING_ERROR_1">SimRank</span> Computation </span>by <span class="blsp-spelling-error" id="SPELLING_ERROR_2">Lizorkin</span> <span class="blsp-spelling-error" id="SPELLING_ERROR_3">et</span> <span class="blsp-spelling-error" id="SPELLING_ERROR_4">al</span>. [1].<br /><br />In summary, the paper studies a specific algorithm -- <span class="blsp-spelling-error" id="SPELLING_ERROR_5">SimRank</span> -- that determines similarity scores between objects by augmenting an available link structure that connects the objects (e.g., hyperlinks between pages, friendship links in online social networks, similar tags between photos in <span class="blsp-spelling-error" id="SPELLING_ERROR_6">Flickr</span>). The intuition behind <span class="blsp-spelling-error" id="SPELLING_ERROR_7">SimRank</span> is that "<span style="font-style: italic;">two objects are similar if they are referred to by similar objects</span>".<br /><br />As the title indicates, the work contributions can be divided into two parts: <span style="font-style: italic;">1</span>) it provides accuracy estimates for the iterative computation of <span class="blsp-spelling-error" id="SPELLING_ERROR_8">SimRank</span> scores; and, <span style="font-style: italic;">2</span>) it proposes and analysis three optimization techniques that reduces the computational complexity of the original algorithm from O(n^4) to O(n^3).<br /><br />One point, which seems to need a deeper investigation, is whether the similarity scores produced by <span class="blsp-spelling-error" id="SPELLING_ERROR_9">SimRank</span> have high quality (by quality I mean they do capture the true similarity between objects). Indeed, the original <span class="blsp-spelling-error" id="SPELLING_ERROR_10">SimRank</span> work by <span class="blsp-spelling-error" id="SPELLING_ERROR_11">Jeh</span> & <span class="blsp-spelling-error" id="SPELLING_ERROR_12">Widom</span> [2] and <span class="blsp-spelling-error" id="SPELLING_ERROR_13">Lizorkin's</span> paper lack a discussion (and experiments) on the quality of scores.<br /><br />Nevertheless, the beauty of <span class="blsp-spelling-error" id="SPELLING_ERROR_14">Lizorkin's</span> paper resides on the fact that the proposed optimization techniques may be helpful in other contexts, though they originate from a specific context -- improving <span class="blsp-spelling-error" id="SPELLING_ERROR_15">SimRank</span>. In the following, I briefly describe the intuition behind each optimization.<br /><br /><span style="font-weight: bold;">Essential nodes</span> -- by exploiting the graph structure, the authors are able to define the set of essential nodes of a particular node<span style="font-style: italic;"> v, </span>and more importantly, to prove that if a given node <span style="font-style: italic;">b </span>is outside the set of essential nodes of <span style="font-style: italic;">v</span>, the similarity score between them is zero. It turns out, that computing the set of essential nodes is much cheaper than computing the similarity score. Hence, it leads to the first optimization.<br /><br /><span style="font-weight: bold;">Partial sums</span> -- <span class="blsp-spelling-error" id="SPELLING_ERROR_16">SimRank</span> similarity is recursive by definition. This implies that the similarity score of between some pairs may be <span style="font-style: italic;">reused (</span>without <span class="blsp-spelling-error" id="SPELLING_ERROR_17">recomputation</span>) to compute the similarity between several other pairs of nodes. The idea applied here was to use<span style="font-style: italic;"> <span class="blsp-spelling-error" id="SPELLING_ERROR_18">memoization</span></span> to reduce the cost of computing parts of the sum in the computation of a final score. It occurs to me that <span class="blsp-spelling-error" id="SPELLING_ERROR_19">memoization</span> may be good even in a dynamic graph (i.e., a graph that changes over time), depending, of course, on the trade off between accuracy of the scores and the computational cost implied by the <span class="blsp-spelling-error" id="SPELLING_ERROR_20">recomputation</span>.<br /><br /><span style="font-weight: bold;"><span class="blsp-spelling-corrected" id="SPELLING_ERROR_21">Threshold</span>-sieved similarity</span> -- here, the idea relies on the fact that setting a minimum threshold on the similarity that should be considered enables a reduction in the number of node pairs that the similarity have to be computed. The interesting point is that the threshold does not break the relative ranking between similarity scores, as one could expect due to the fact that some nodes are discarded.<br /><br />Currently, I am investigating the applicability of one or two of the techniques above in a problem that I have in hands now. More about it soon.<br /><br />References:<br /><br />[1] <a href="http://www.citeulike.org/user/elsantosneto/article/6509946">http://www.citeulike.org/user/elsantosneto/article/6509946</a><br />[2] <a href="http://www.citeulike.org/user/ldietz/article/349900">http://www.citeulike.org/user/ldietz/article/349900</a>Elizeu Santos-Netohttp://www.blogger.com/profile/01894064232549942032noreply@blogger.com1tag:blogger.com,1999:blog-19904488.post-91096574709891819192009-10-23T08:41:00.000-07:002009-10-23T08:45:11.196-07:00Spam in social softwareFrom the Greg Linden's <a href=" http://glinden.blogspot.com">blog</a>:<br /><br />An arms race in spamming social software<br />by Greg Linden (16 Oct 2009)<br />http://glinden.blogspot.com/2009/10/arms-race-in-spamming-social-software.html<br /><br />The post presents an ultra-short, yet interesting, summary of spam strategies observed in social software. In particular, Greg Linden mentions several observed <span style="font-style:italic;">badmouthing</span> strategies -- the spammer tries to taint competitors reputation, as opposed to attempt to use spam to obtain benefits directly. Interestingly, Chen and Friedman [1] conjecture that <span style="font-style:italic;">badmouthing</span> attacks are harder to tackle than attacks that attempt to artificially boost one's reputation.<br /><br />The post ends suggesting that incentive-based approaches to deter spam are (possibly good) alternatives compared to techniques that detect spam by focusing on content analysis (e.g., detection of commercial intent on blog comments). I would say they are complementary, though.<br /><br />[1] Chen & Friedman. "Sybilproof Reputation Mechanisms".<br />http://doi.acm.org/10.1145/1080192.1080202Elizeu Santos-Netohttp://www.blogger.com/profile/01894064232549942032noreply@blogger.com1tag:blogger.com,1999:blog-19904488.post-13942444967597662542009-08-26T11:25:00.000-07:002009-08-26T12:13:47.526-07:00Relationship between cross-field citations and work impactA recent work by Shi, <a href="http://mblog.lib.umich.edu/~ladamic/">Adamic </a>, Tseng and Clarkson has an interesting analysis on the relationship between works that draw from different areas (i.e., cite papers outside their fields) and their subsequent impact. [1]<br /><br />One of the interesting bits:<br /><br />[...]<br />Intuitively, any individual citation will at most have a very weak impact on the success of a citing paper. It will only be one of possibly dozens of references made in an article or patent. Other factors, such as the publication venue and the reputation of the authors, are more likely to contribute to the impact of the article than any individual citation the authors include. <span style="font-style:italic;">We nevertheless see a significant relationship between the interdisciplinarity of citations and the impact of the publication</span>.<br />[...]<br /><br />This reminds me of previous results on the relationship between network constraint and value of ideas [2]. The intuition is that a person who is in a <span style="font-style:italic;">bridge</span> position in her social network (i.e., connecting two distinct groups) is more exposed to different ways of thinking, which may lead to that person having more valuable ideas. Here, the social network is the citation network, and the bridges are papers that cite otherwise unconnected clusters (i.e., fields).<br /><br />A recipe for higher impact research?<br /><br />[1] Shi et al. 2009. <a href="http://www.plosone.org/article/info%3Adoi%2F10.1371%2Fjournal.pone.0006547">The Impact of Boundary Spanning Scholarly Publications and Patents</a>. PLoS ONE.<br />[2] Burt, R., 2003. <a href="http://faculty.chicagobooth.edu/ronald.burt/research/SHGI.pdf">Structural Holes and Good Ideas</a>. American Journal of Sociology.Elizeu Santos-Netohttp://www.blogger.com/profile/01894064232549942032noreply@blogger.com0tag:blogger.com,1999:blog-19904488.post-70789002098047218082009-07-15T09:02:00.000-07:002009-07-15T15:40:30.851-07:00The Internet and its TopologyA while ago, I came across an article that discusses points related to network modeling and characterization [1], particularly the Internet physical topology. <br /><br />The motivation used by the authors is, as the article puts it, the <i>power-law argument</i>. In particular, the authors highlight important points researchers should focus when performing similar studies. They also go further and challenge the now traditional assumption that the Internet topology resembles a scale free network. In this post, I briefly summarize the paper.<br /><br />The paper recounts the now well known and accepted <i>scale-free Internet argument</i> (i.e., that the Internet topology is well modeled by a network with a power-law node degree distribution). The arguments, as presented by the authors, are rooted on the limitations of <span style="font-family: courier new;">traceroute</span> on accurately determining the <i>physical</i> topology, as it only captures interfaces of routers instead of physical boxes.<br /><br />In short, the work proposes to focus on the decision making process an Internet service provider goes through when planning and deploying its physical infrastructure, as opposed to using traceroute traces to inspire models for the Internet topology. Moreover, the authors suggest that the right tool to do that is <i>constrained optimization</i> that allows to formalize the referred decision making process.<br /><br />Other interesting points extracted from the paper:<br /><br /><span style="font-weight:bold;">a</span>). <blockquote>A node high degree implies low capacity links, conversely low degree implies high capacity links, this is due to the limited capacity on processing traffic. Thus, the high degree nodes would be on the edge of network, as opposed to the core, which is different from what most of the traceroute studies claim.</blockquote><br /><br /><span style="font-weight:bold;">b</span>). <blockquote>To avoid confusion and to emphasize the fact that preferential attachment is just one of many other mechanisms that is capable of generating scale-free graphs, we will refer here to the network models proposed in [2].</blockquote><br /><br />Suggested principles on characterization and modeling, which, I think, are sufficiently general to be applied in fields other than network topology characterization:<br /><br /><span style="font-weight:bold;">1</span>. <span style="font-style:italic;">Know your data</span>: <blockquote>The data used by Faloutsos, Faloutsos, and Faloutsos [3] was not intended to capture the physical topology, rather to "<span style="font-style:italic;">get some experimental data on the shape of multicast trees one an actually obtain in the real Internet"</span></blockquote><br /><br /><span style="font-weight:bold;">2</span>. <span style="font-style:italic;">When modeling is more than data fitting</span>: <blockquote>If we wish to increase our confidence in a proposed model, we ought also to ask what new types of measurements are either already available or could be collected and used for validation. (By new they mean completely new types of data not involved whatsoever with the original modelling exercise).</blockquote><br /><br /><span style="font-weight:bold;">3</span>. <span style="font-style:italic;">Know your statistic</span>: <blockquote>Once agreeing that the data set is problematic, one could try to use a more robust statistic to avoid the mistakes.<br /></blockquote><br /><br />[1] W. Willinger, D. Alderson and C. Doyle. "<a href="http://www.ams.org/notices/200905/rtx090500586p.pdf">Mathematics and the Internet: A source of enormous confusion and great potential</a>", <a href="http://www.ams.org/journal/notices">Notices of the AMS</a>, Vol. 56, no. 5, May 2009.<br /><br />[2] A.-L. Barabási and R. Albert, <a href='http://www.sciencemag.org/cgi/content/abstract/286/5439/509'>Emergence of scaling in random networks</a>, Science 286 (1999).<br /><br />[3] M. Faloutsos, P. Faloutsos, and C. Faloutsos, <a href='http://doi.acm.org/10.1145/316188.316229'>On power-law relationships of the Internet topology</a>, ACM SIGCOMM (1999).Elizeu Santos-Netohttp://www.blogger.com/profile/01894064232549942032noreply@blogger.com0tag:blogger.com,1999:blog-19904488.post-64496269210301972092009-06-23T01:10:00.000-07:002009-06-23T01:34:33.441-07:00The role of the scientific methodHere is an interesting article by <a href='http://www.utoronto.ca/jpolanyi/'>John Polanyi</a> published by <a href='http://www.theglobeandmail.com'>The Globe and Mail</a>.<br /><br /><a href='http://www.theglobeandmail.com/news/opinions/hope-lies-in-the-scientific-method/article1152473/'>Hope lies in the scientific method</a> by John Polanyi.<br /><br />The article discusses the role of science, and in my opinion, more importantly, the importance of the critical view of scientists on the impact that political decisions may have on the lives of many.<br /><br />Food for thought, indeed.Elizeu Santos-Netohttp://www.blogger.com/profile/01894064232549942032noreply@blogger.com0tag:blogger.com,1999:blog-19904488.post-88936974419115027202009-06-03T09:38:00.000-07:002009-06-03T13:05:50.770-07:00Data Reliability Tradeoffs<a href='http://www.ece.ubc.ca/~abdullah'>Abdullah Gharaibeh</a> (my colleague at the <a href='http://netsyslab.ece.ubc.ca'>NetSysLab</a>) has a recent work that explores a combination of heterogeneous storage components in terms of cost, reliability and throughput.<br /><br />The work proposes a storage architecture that leverages idle storage resources, located on volatile nodes (e.g., desktops), to provide high throughput access at low cost. Moreover, the system is designed to provide durability with a low throughput durable storage component (e.g., tape).<br /><br />What I like in the solution is that it shows nicely how to decouple components that provide two important features for data-intensive applications: availability and durability. Moreover, this separation (together with the evidence showed by the experiments) helps system administrators to reason about the deployment cost.<br /><br />Here is the abstract:<br /><br />Abdullah Gharaibeh and Matei Ripeanu. <a href='http://www.ece.ubc.ca/~abdullah/papers/hpdc168-gharaibeh.pdf'><i>Exploring Data Reliability Tradeoffs in Replicated Storage Systems</i></a>. ACM/IEEE International Symposium on High Performance Distributed Computing (HPDC 2009), Munich, Germany, June 2009. <br /><br /><br /><blockquote>This paper explores the feasibility of a cost-efficient storage architecture that offers the reliability and access performance characteristics of a high-end system. This architecture exploits two opportunities: First, scavenging idle storage from LAN connected desktops not only offers a low-cost storage space, but also high I/O throughput by aggregating the I/O channels of the participating nodes. Second, the two components of data reliability – durability and availability – can be decoupled to control overall system cost. To capitalize on these opportunities, we integrate two types of components: volatile, scavenged storage and dedicated, yet low-bandwidth durable storage. On the one hand, the durable storage forms a low-cost back-end that enables the system to restore the data the volatile nodes may lose. On the other hand, the volatile nodes provide a high-throughput front-end. While integrating these components has the potential to offer a unique combination of high throughput, low cost, and durability, a number of concerns need to be addressed to architect and correctly provision the system. To this end, we develop analytical- and simulation-based tools to evaluate the impact of system characteristics (e.g., bandwidth limitations on the durable and the volatile nodes) and design choices (e.g., replica placement scheme) on data availability and the associated system costs (e.g., maintenance traffic). Further, we implement and evaluate a prototype of the proposed architecture: namely a GridFTP server that aggregates volatile resources. Our evaluation demonstrates an impressive, up to 800MBps transfer throughput for the new GridFTP service</blockquote>Elizeu Santos-Netohttp://www.blogger.com/profile/01894064232549942032noreply@blogger.com0tag:blogger.com,1999:blog-19904488.post-54076982282461869262009-04-22T12:31:00.001-07:002009-04-22T13:05:46.890-07:00Individual and Social Behavior in Tagging SystemsAs part of a much broader investigation on the <i>peer production of information</i>, <a href='http://www.ece.ubc.ca/~elizeus/ht102-santos-neto.pdf'>Individual and Social Behavior in Tagging Systems</a> [1] is a recent work that focuses on the quantitative aspects of <i>tag reuse</i>, <i>item re-tagging</i> and the <i>implicit social relation</i> inferred from the similarity of user interests.<br /><br />The observations point to interesting directions on the design of systems, such as recommendation systems, that aim at exploiting past user activity. For instance, it providers quantitative evidence why item recommendation tends to be less efficient than tag recommendations in these systems (based on the relatively higher level of tag reuse, compared to the item re-tagging). <br /><br />I must mention that this work is a result of a collaboration with an enthusiastic team: <a href='http://www.lsd.ufcg.edu.br/~nazareno'>Nazareno Andrade</a>, David Condon, <a href='http://www.cse.usf.edu/~anda'>Adriana Iamnitchi</a> and <a href='http://www.ece.ubc.ca/~matei'>Matei Ripeanu</a>, <br /><br />Reference:<br /><br />[1] Elizeu Santos-Neto, David Condon, Nazareno Andrade, Adriana Iamnitchi and Matei Ripeanu. "<a href='http://www.ece.ubc.ca/~elizeus/ht102-santos-neto.pdf'>Individual and Social Behavior in Tagging Systems</a>". In <a href='http://www.ht2009.org'>the 20th ACM Conference on Hypertext and Hypermedia</a>. Torino, Italy, June 29-July 1, 2009.Elizeu Santos-Netohttp://www.blogger.com/profile/01894064232549942032noreply@blogger.com0tag:blogger.com,1999:blog-19904488.post-61547021899913206802009-03-10T02:04:00.000-07:002009-03-10T02:52:43.659-07:00Tracing Influenza Epidemics via CrowdsourcingResearchers from Google (Mountain View,CA,USA) and Centers for Disease Control and Prevention (Atlanta, GA,USA) recently reported a method to build a model that helps detecting the spread of Influenza.<br /><br />The article describes the analysis of search logs in combination with records of doctor visits related to Influenza-like Illness (ILI). The goal of the model is to predict the percentage of doctor visits that are ILI-related. The authors report a correlation of up to 0.96 between the model predictions and the Centers for Disease Control (CDC) reports.<br /><br />Citation:<br /><br />Jeremy Ginsberg, Matthew H. Mohebbi, Rajan S. Patel, Lynnette Brammer, Mark S. Smolinski and Larry Brilliant. <a href='http://www.nature.com/nature/journal/v457/n7232/abs/nature07634.html'>Detecting influenza epidemics using search engine query data</a>. Nature 457, 1012-1014 (19 February 2009).Elizeu Santos-Netohttp://www.blogger.com/profile/01894064232549942032noreply@blogger.com0tag:blogger.com,1999:blog-19904488.post-28124092645368450302009-03-03T21:52:00.000-08:002009-03-03T22:23:35.585-08:00One Microsoft WayLast week, at Redmond, Microsoft Research showcased a list of projects from its labs located worldwide during the <a href='http://research.microsoft.com/en-us/events/techfest2009/default.aspx'>TechFest 2009</a>. As part of my internship last year, at the lovely <a href='http://research.microsoft.com/en-us/groups/camsys/default.aspx'>Microsoft Research Cambridge - UK</a>, I worked on the Mobile Content-Casting project, which was also showcased.<br /><br /><a href='http://arstechnica.com'>Ars Technica</a> has an article summarizing some of the projects presented at <a href='http://research.microsoft.com/en-us/events/techfest2009/default.aspx'>TechFest 2009</a>.<br /><br />It is worth taking a look: <a href='http://arstechnica.com/microsoft/news/2009/03/microsoft-research-techfest-2009-a-glance-at-the-road-ahead.ars'>Microsoft Research TechFest 2009: a glance at the road ahead</a>.<br /><br />I particularly found the SecondLight and the suite of Social-Digital demos really cool. Both are from MS Research at Cambridge - UK.Elizeu Santos-Netohttp://www.blogger.com/profile/01894064232549942032noreply@blogger.com0tag:blogger.com,1999:blog-19904488.post-7451062509553705992009-02-27T12:33:00.000-08:002009-02-27T12:41:27.333-08:00A nice short storyThis is a fun short story published by Nature that I came across recently. <br /><br />"<a href='http://www.nature.com/doifinder/10.1038/4571174a'>Lost in sun and silence -- The golden age of communication</a>"<br />by Vincenzo Palermo. Nature, Vol 457, 26 February 2009.Elizeu Santos-Netohttp://www.blogger.com/profile/01894064232549942032noreply@blogger.com0tag:blogger.com,1999:blog-19904488.post-56098348170817408552008-08-13T00:52:00.000-07:002008-08-14T10:43:35.425-07:00The Anticommons<a href='http://www.newyorker.com'>The New Yorker</a>'s Financial Page has an interesting article: <a href='http://www.newyorker.com/talk/financial/2008/08/11/080811ta_talk_surowiecki'>The Permission Problem</a> by <a href='http://www.newyorker.com/search/query?query=authorName:%22James%20Surowiecki%22'>James Surowiecki</a> (the author of <a href='http://www.citeulike.org/user/elsantosneto/article/158650'>Wisdom of Crowds</a>). <br /><br />James Surowiecki discusses the notion of <i>anticommons</i> as presented by <a ref='http://www.law.columbia.edu/fac/Michael_Heller'>Professor Michael Heller</a> (<a href='http://www.gridlockeconomy.com/'>The Gridlock Economy</a>). <br /><br />To illustrate the point, Surowiecki points out two extreme scenarios of the resource sharing problem -- i) common good model: the resource is deemed public and it is shared among individuals without the notion of individual ownership over the shared resource; ii) private property model: the notion of unlimited property, where the resource is owned by a subset of individuals, who may charge other individuals that want to consume units of that resource.<br /><br />The article says that, on the one hand, common goods may lead to the well-known <a href='http://en.wikipedia.org/wiki/Tragedy_of_the_commons'>tragedy of the commons</a>: <i>overuse</i>. On the other hand, unlimited property rights may lead to the exactly opposite: <i>waste of resources</i> (or the <a href='http://en.wikipedia.org/wiki/Tragedy_of_the_anticommons'>Tragedy of the anticommons</a>.<br /><br />The article has nice examples:<br /><br /><br /><blockquote><br />[...]<br />The commons leads to overuse and destruction; the anticommons leads to underuse and waste. In the cultural sphere, ever tighter restrictions on copyright and fair use limit artists’ abilities to sample and build on older works of art. In biotechnology, the explosion of patenting over the past twenty-five years—particularly efforts to patent things like gene fragments—may be retarding drug development, by making it hard to create a new drug without licensing myriad previous patents. Even divided land ownership can have unforeseen consequences. Wind power, for instance, could reliably supply up to twenty per cent of America’s energy needs—but only if new transmission lines were built, allowing the efficient movement of power from the places where it’s generated to the places where it’s consumed. Don’t count on that happening anytime soon. Most of the land that the grid would pass through is owned by individuals, and nobody wants power lines running through his back yard.<br />[...]<br /></blockquote><br /><br />It seems to me that certain computational environments present an interesting middle ground between these two extremes discussed above. For example, <a href='http://nazaga.blogspot.com/'>Nazareno</a> pointed out a while ago to a <a href='http://nazaga.blogspot.com/2008/07/large-scale-commons-based-wi-fi.html'>Large-scale commons-based Wi-fi</a>: users, who <i>own</i> an Internet connection, may share the spare capacity in exchange for either using the spare capacity of others later or being paid for it. The wonderful insight of this resource sharing model is that people buy more Internet bandwidth (as many other computational goods -- if I can name it like this) than they are able to use. Hence, resources are mostly underutilized. So, why not sharing it (the spare capacity)in exchange for access to others spare capacity in the future? <br /><br />Finally, a question comes to my mind: besides the fact that certain resource units bear an extra capacity by definition (e.g. often my CPU is 99% idle), does any other intrinsic resource characteristic play a role in suggesting which model is suitable for the sharing of that resource?Elizeu Santos-Netohttp://www.blogger.com/profile/01894064232549942032noreply@blogger.com1tag:blogger.com,1999:blog-19904488.post-30359115806920664742008-07-27T22:07:00.000-07:002008-07-28T10:40:30.333-07:00Information Management in Living Organisms<a href='http://www.nature.com'>Nature</a> has an article by <a href=''>Paul Nurse</a> (<a href='http://www.nature.com/nature/journal/v454/n7203/full/454424a.html'>Life, Logic and Information</a>), where he discusses some ideas on studying living organisms as information management systems. <br /><br />Paul Nurse suggests that analyzing the information flow in living organisms would help to understand certain behaviors, which are not completely clear nowadays. <br /><br />From a computer systems researcher standpoint, the interesting aspect of Paul Nurse's idea is that it goes on the opposite direction of previous studies: instead of drawing inspiration from nature to build information management systems (e.g. <a href='http://en.wikipedia.org/wiki/Ant_colony_optimization'>ant inspired algorithms</a>), the author proposes to use information science tools to study the nature.<br /><br />A piece from the article:<br /><br /><blockquote>Systems analyses of living organisms have used a variety of biochemical and genetic interaction traps with the emphasis on identifying the components and describing how these interact with each other. These approaches are essential but need to be supplemented by more investigation into how living systems gather, process, store and use information, as was emphasized at the birth of molecular biology.</blockquote><br /><br />This sounds exciting, as a better understanding of living systems could feedback into the bio-inspired approach of designing distributed computational systems. <br /><br />A couple of years ago, I briefly explored the design of a distributed storage system based on the behavior of the Messor Barbarus ants (for more details on the M. Barbarus ants see <a href='http://www2.isye.gatech.edu/~carl/publications.htm'>Anderson, C., J.J. Boomsma, and J.J. Bartholdi, III. 2002. Task partitioning in insect societies: bucket brigades. Insectes sociaux 49(2): 171-180</a>). <br /><br />The rationale behind it is quite simple: every time an <i>unloaded</i> larger ant encounters a <i>loaded</i> smaller ant, the load is passed from the smaller to the larger ant. This naturally spread the work among the workers according to their capacity (strength and speed). <br /><br />Bringing it back to the context of distributed storage systems, the idea is to enable a self-organizing load balance scheme by making larger nodes to request more load from lower capacity nodes. The goal is to improve throughput and data availability.<br /><br />Obviously, a comprehensive performance evaluation is necessary to claim that this strategy would lead to an globally efficient system.Elizeu Santos-Netohttp://www.blogger.com/profile/01894064232549942032noreply@blogger.com1tag:blogger.com,1999:blog-19904488.post-6155201840932307692008-07-03T10:44:00.000-07:002008-07-08T10:03:17.414-07:00HPDC'08 - Part II<a href='http://www.lri.fr/~fedak/'>Gilles Fedak</a> delivered an invited talk at the UPGRADE-CN workshop (part of the HPDC'08). He presented the BitDew - a programmable environment that targets data management in Desktop Grids [1]. <br /><br />The rationale behind BitDew is that applications can define routines for data manipulation. These routines are expressed via predefined metadata, which are used by the infrastructure mechanisms to perform data management tasks, such as replication.<br /><br />In a <a href='http://www.lri.fr/~fedak/thesis/bitdew.RR-6427.pdf'>Technical Report</a>, Gilles and colleagues present use cases and performance evaluation of mechanisms that provide data management functionality in BitDew.<br /><br />In particular, I found the approach of leveraging metadata interesting. The predefined set of metadata allows the application layer to communicate requirements to the infrastructure regarding the desired level of fault tolerance and transfer protocols, for example. <br /><br />In fact, this intersects with one of our projects at the <a href='http://netsyslab.ece.ubc.ca/'>NetSys Lab</a>, where we investigate the use of custom metadata as a cross-layer communication method for storage systems <a href='http://www.ece.ubc.ca/~elizeus/'>[2]</a>.<br /><br />As we use the file system interface to separate between the application and the storage layers, the two approaches (BitDew and our Custom Metadata approach) seem complementary. The metadata passed by the applications via BitDew could propagate to the file system, where it would interact with the Extended Attributes interface (which is exploited by our solution). <br /><br />More coding fun to come...<br /><br />[1] Fedak et al. "<a href='http://www.lri.fr/~fedak/thesis/bitdew.RR-6427.pdf'>BitDew: A Programmable Environment for Large-Scale Data Management and Distribution</a>". Technical Report, 6427, INRIA. <br /><br />[2] Elizeu Santos-Neto, Samer Al-Kiswany, Nazareno Andrade, Sathish Gopalakrishnan and Matei Ripeanu. "<a href='http://ece.ubc.ca/~elizeus/hpdc4hot-santos-neto.pdf'>Enabling Cross-Layer Optimizations in Storage Systems with Custom Metadata</a>". In HPDC'08 - HotTopics. Boston, MA, USA. September, 2008.Elizeu Santos-Netohttp://www.blogger.com/profile/01894064232549942032noreply@blogger.com0tag:blogger.com,1999:blog-19904488.post-39156908502099697622008-06-30T12:20:00.000-07:002008-07-02T08:27:27.848-07:00HPDC'2008 - Part ILast week I participated to two great conferences: the <a href='http://www.hpdc.org'>International Symposium in High Performance Distributed Computing</a> (HPDC) and the <a href='http://www.usenix.org/events/usenix08'>USENIX</a>. Both events took place in Boston, MA, USA.<br /><br />There a lot of interesting things to mention. Thus, to avoid a single long post, I will describe a few presentations that I attended (and discuss some ideas) in a series of short posts. <br /><br />In the first two days at HPDC, there were two interesting workshops: <a href='http://2008.upgrade-cn.org/'>UPGRADE-CN</a> (P2P and Grids for the Development of Content Networks) and <a href='http://www.cercs.gatech.edu/mmcs08/'>MMS</a> (Managed Multicore Systems).<br /><br />The two workshops had works related to the research projects I am currently working on. <br /><br />Molina [1] presented his work on designing two protocols that enable collaborative content delivery in mobile transient networks. By transient networks, the authors mean networks composed of devices that are geographically co-located for a short period such as a music festival. <br /><br />The authors suggest to exploit the multiple network interfaces currently available in most mobile devices and to enable collaborative use of these multihomed devices.<br /><br />The idea is quite interesting. In particular, it raises some issues from the perspective of distributed resource sharing. It would be good to understand whether incentive mechanisms are necessary in transient networks. The idea is to encourage users to share their connections with a community for collaborative downloading/streaming of content. <br /><br />On top of that, a nice follow-up work would be to investigate the feasibility of collaborative data dissemination protocols, which are widely used in the Internet (e.g. BitTorrent), in the transient networks scenarios. <br /><br /><br />[1] Molina et al. "A Social Framework for Content Distribution in Mobile Transient Networks". In <a href='http://2008.upgrade-cn.org/'>UPGRADE-CN'2008</a>.Elizeu Santos-Netohttp://www.blogger.com/profile/01894064232549942032noreply@blogger.com0tag:blogger.com,1999:blog-19904488.post-44831971619108135642008-06-05T10:11:00.000-07:002008-06-05T11:01:08.633-07:00IPTV Viewing Habits and Netflix PlayerThe <a href="http://www.cs.toronto.edu/iptps2008/">IPTPS 2008</a> has an interesting paper on exploiting TV Viewing Habits to reduce the traffic on the ISP backbone generated by IPTV consumers. <br /><br /><blockquote>"<a href="http://www.cs.toronto.edu/iptps2008/final/45.pdf">On Next-Generation Telco-Managed P2P TV Architectures</a>" by Meeyoung Cha (KAIST), Pablo Rodriguez (Telefonica Research, Barcelona), Sue Moon (KAIST), and Jon Crowcroft (University of Cambridge).</blockquote><br /><br />In this paper the authors analyze the utilization o P2P content distribution techniques to reduce network overhead in a Internet Service Provider IPTV infrastructure. To exploit the patterns of channel holding time, channel popularity and the correlation between the time of the day and the number of viewers, the authors propose a locality-aware P2P content distribution scheme that reduces the traffic on the ISP backbone. <br /><br />From the paper:<br /><br /><blockquote>we ascertain the sweet spots and the overheads of server-based unicast, multicast, and serverless P2P and also show the empirical lower bound network cost of P2P (where cost reduction is up to 83% compared to current IP multicast distribution<br /><br />[...]<br /><br />We believe that our work provides valuable insights to service providers in designing the next-generation IPTV architecture. Especially, it highlights that dedicated multicast is useful for few of the extremely popular channels and that P2P can handle a much larger number of channels while imposing very little demand for infrastructure.<br /></blockquote><br /><br />This week I saw some news on the internal characteristics of the <a href="http://www.hothardware.com/News/Inside_The_Tech_Of_The_Netflix_Player_With_Roku1/">Netflix Player</a>. Immediately, I thought of the paper from IPTPS as a possible optimization to the <a href="http://news.cnet.com/8301-10784_3-9947582-7.html">Netflix Player</a>. <br /><br />The NetFlix player is supposed to use the conventional broadband connection, as opposed to well provisioned IPTV architectures described in Cha et al. Perhaps, the locality-aware P2P content distribution technique is even more interesting in the Netflix Player case.<br /><br />Nevertheless, the viewing habits and interest sharing among Netflix users may differ dramatically from what is observed in the IPTV environment, which would impact the efficiency of the locality-aware P2P content distribution.Elizeu Santos-Netohttp://www.blogger.com/profile/01894064232549942032noreply@blogger.com0tag:blogger.com,1999:blog-19904488.post-23495789608353159082008-06-03T07:54:00.000-07:002008-06-03T08:02:07.194-07:00Oh My Goosh!If you like typing your commands away to interact with your computer, you will like this: <a href='http://goosh.org/'>Goosh</a> :-)<br /><br />From Slashdot: <a href='http://tech.slashdot.org/article.pl?sid=08/06/02/222234'>goosh, the Unofficial Google Shell</a> posted by kdawson on Monday June 02, @07:26PM.<br /><br /><blockquote>It's essentially a browser-oriented, shell-like interface that allows you to quickly search Google (and images and news) and Wikipedia and get information in a text-only format.</blockquote>Elizeu Santos-Netohttp://www.blogger.com/profile/01894064232549942032noreply@blogger.com0tag:blogger.com,1999:blog-19904488.post-14257809795203642332008-05-28T10:46:00.000-07:002008-05-29T00:30:58.556-07:00"Yes, There Is a Correlation"This week I came across an interesting paper: "<a href='http://www2008.org/papers/pdf/p655-singla.pdf'>Yes, There is a Correlation - From Social Networks to Personal Behavior on the Web</a>" by <a href='http://www.cs.wahsington.edu/~parag'>Parag Singla</a> (University of Washington) and <a href='http://research.microsoft.com/~mattri/'>Matthew Richardson</a> (Microsoft Research) in <a href='http://www2008.org'>WWW'2008</a>. <br /><br />In summary, they show that the similarity between the personal interests and attributes of two users who are MSN contacts is much higher than two random users. Moreover, I've found the problem formulation elegant and the scale of data non-trivial to handle (approx. 13 million unique users).<br /><br /><br />From the paper:<br /><br /><blockquote>Summarizing the results, we showed that people who talk to each other on the messenger network are more likely to be similar than a random pair of users, where similarity is measured in terms of matching on attributes such as queries issued, query categories, age, zip and gender. Further, this similarity increases with increasing talk time. The similarities tend to decrease with increasing average time spent per message. Also, we showed that even within the same demographics, people who talk to each other are more likely to be similar. Finally, as we hop away in the messenger network, the similarity still exists, though it is reduced.</blockquote><br /><br />I wonder whether a similar level of correlation would be observed in online communities with other purposes, such as content-sharing (e.g. <a href="http://www.flickr.com">Flickr</a> and <a href="http://www.youtube.ca">YouTube</a>).Elizeu Santos-Netohttp://www.blogger.com/profile/01894064232549942032noreply@blogger.com0tag:blogger.com,1999:blog-19904488.post-72950349984248390712008-05-16T02:09:00.000-07:002008-05-16T02:32:42.742-07:00OurGrid 4.0 releasedGood news from the South! The <a href='http://www.ourgrid.org/?p=downloadAndDocumentation'>OurGrid 4.0</a> is out.<br /><br />In summary: OurGrid is an open source, free-to-join, peer-to-peer grid, where users trade computational resources. The loosely coupled computational infrastructure is ideal for the execution of embarrassingly parallel applications.<br /><br />I am particularly glad with this release, as <a href='http://www.ourgrid.org'>OurGrid</a> has been a useful tool in my previous studies. I used it to analyze traces of activity of <a href='http://www.ece.ubc.ca/~elizeus'>content sharing communities</a>. OurGrid makes it easy to harness the idle times of our desktop machines and monitor the progress of the computations in a much easier way. <br /><br />Next week I will definitely give a try on the new version (as we are still using version 3.3).<br /><br />The new site looks great too. Congratulations, OurGrid Community! :-)Elizeu Santos-Netohttp://www.blogger.com/profile/01894064232549942032noreply@blogger.com0tag:blogger.com,1999:blog-19904488.post-58239116902442791652008-05-15T13:07:00.000-07:002008-05-15T14:01:28.914-07:00Deep Water(*) at 45rpmA bit about recent music experiences... <br /><br />It has been a while, since I listened to the voice of <a href='http://en.wikipedia.org/wiki/Beth_Gibbons'>Beth Gibbons</a>. So, I recently indulged myself with the addition of a new <i>record</i> to my collection. The <a href='http://www.portishead.co.uk/'>Portishead</a> new album: <a href='http://www.myspace.com/PORTISHEADALBUM3'>Third</a>. By record, I mean an <a href='http://en.wikipedia.org/wiki/LP_album'>LP</a>. :-)<br /><br />The immediate surprise after playing the first song was to hear some voices in Portuguese. For a moment, I thought that the record player switch was set to FM Radio on some independent radio station. <br /><br />The second big surprise was that record sound dark, with very slow beats and bass sounds. After a couple of seconds, I noticed that the album is an 45 RPM LP, as opposed to the usual 33 RPM records (more popular today). A quick adjustment on the player rotation speed and <i>voilá!</i>.<br /><br />Overall, Portishead's new album sounds quite different from the previous works. I feel that there is more emphasis on the drums, which is really nice. Beth Gibbons voice is more discrete than in her solo album or in the previous Portishead recordings. <br /><br />In my opinion, the best song of the album so far is <a href='http://hypem.com/track/548528'>Magic Doors</a> (side 4, as the package comes with 2 LPs). :-)<br /><br />Unfortunately, I missed their <a href='http://www.coachella.com/'>Coachella's concert</a>, but I hope to have another opportunity soon...<br /><br />(*) Deep Water is one of the songs of the album. I think it would work as a nice title for it.Elizeu Santos-Netohttp://www.blogger.com/profile/01894064232549942032noreply@blogger.com0tag:blogger.com,1999:blog-19904488.post-67995734346705528532008-04-27T18:51:00.001-07:002008-04-27T18:57:02.759-07:00Non-absolute numbersAs you come back to life (after a series of conference and project deadlines), you are able to recover clever and funny pieces of literature such as the explanation of what is <a href="http://www.arndt-bruenner.de/mathe/Allgemein/bistromathics.htm">Bistromathics</a> and its relation to the non-absolute numbers.Elizeu Santos-Netohttp://www.blogger.com/profile/01894064232549942032noreply@blogger.com0