How about a national database for tracking when everyone uses the restroom. We could put little sensors on all toilets to track how often they're flushed!
"If there are features in our products that are subpar or need to be added, then I have great confidence that we are an organization that responds pretty quickly and effectively to that."
Excerpt from the next Ballmer memo:
"Security is not a feature! Security, security, security!!!"
If I recall correctly, the Microsoftie who said he installed Firefox immediately followed by denouncing its security because he had to install a patch (to go from 0.9 to 0.9.1, IIRC).
I thought the sentiment here was that it's okay to install and try your competitors products -- God knows Microsoft's done it enough times to see what to include in their own product line. Sometimes you have to -- the division that writes MS Office for Mac has no choice but to use OS X, right? But it's pretty low to bring up a competitor's product in an interview just to mention a critical flaw when your own track record is at the bottom of the heap.
Even the Windows kernel developers rejected them as a bad idea.
MS Developer #1: I was thinking we could put exceptions in the kernel. MS Developer #2: Are you insane? Why on earth would you want to do that? I don't think I've heard a stupider suggestion for a kernel addition. MS Developer #1: Really? Well uhh... how about we put an Internet browser in the kernel? MS Developer #2: FREAKIN BRILLIANT, let me call Bill.
FireFox is already extremely bloated (on Windows) compared to other Windows applications and the source code is hundreds of meg in size, the reason - it has an entire platform.
Maybe the Mozilla suite, but not Firefox. In my downloads folder at work:
These are the setup executables for Windows. And if memory serves me correctly, the Thunderbird client has been getting smaller with each new version even more dramatically...
I suspect the exact details of the erasure codes they're using can be found here, which by no coincidence is written by Petar Maymounkov and David Mazieres (both the authors of the original Kademlia paper). A good primer for erasure codes would be to read up on Reed-Solomon codes, which seek to provide similar end-results as erasure codes.
Rateless codes are important because they are the first step to a "digital fountain" model of data transfer. The idea is this: say you have a file of 10KB. Using erasure codes, you can "oversample" this file -- that is, turn this file into 40 1KB chunks. Now by collecting ANY 10 of these 1KB chunks, you can reconstruct the original file.
The reason the digital fountain is so cool (and the reason for its name) is because it would make the most amazing BitTorrent client ever. Why? In BitTorrent, you're doing things like choking/unchoking, aggressively seeking the rarest pieces, and hoping that some guy who has the ONLY COPY of piece X doesn't leave the network before it is replicated. Using Erasure Codes, everyone would just blindly get whatever data is sent to them (where each data unit is an "oversample"), and blindly forward it on all outbound links. But if you're getting data in this manner, isn't there a chance you'd get the same piece of data twice (which is like getting the same piece twice in BitTorrent, which is no use)? If you oversample enough, you can make the chance of this happening approach 0. Note in this scheme, there's no choking or unchoking here (so you'll never go through a period of time on a rare torrent where EVERYONE is choking you, and your download rate is 0KB/s), and you don't have to worry about that one guy leaving the swarm with some critical piece -- not just because you can always reconstruct it, but also because that piece is no more critical than any other.
It's beautiful, really. So why aren't we doing it? Simple -- erasure codes are computationally expensive to compute, although they're getting easier as new sorts of erasure codes are being developed, and PCs get faster. The first big breakthrough was with Tornado codes, if I remember correctly. Anyway, we'll see what the future holds...
... when a server can sense a Slashdoting approaching from over 4 hops away.
Re:UCLA discovers ultrapeers!
on
P2P Web searches
·
· Score: 4, Interesting
Not quite... Note: I'm about to karma whore here.
About a year ago, right before starting my senior year at UCLA, I was offered an opportunity to work on this P2P project. At the time it was called "Gnucla," and was being developed by the UCLA EE department's Complex Networks Group. I turned it down, because I had already committed to working on a p2p system in the CS department. But since in all honesty their research was more novel than ours (and my friend was in their group), I subscribed to their mailing list and kept informed on what they were doing.
What they've done isn't find a novel way of picking ultrapeers. Let's review what motivated ultrapeers -- in the beginning, there was Gnutella. Gnutella was a power-law based network. What this meant is that there was no real "topology" to it, unlike peer to peer networks that were emerging and based on Distributed Hash Tables (such as Chord, Pastry, Kademlia [on which Coral is based]). It had nice properties: a low diameter, and very resilient to attacks common on p2p networks. (Loads of peers dropping simultaneously could not partition the network, unlike, say, in Pastry -- unless they are high degree nodes.) But the big problem was that to search the network, you had to flood it. And that generated so much traffic that the network eventually tore itself apart under its own load.
So someone thought that maybe if only a few, select, high-capacity nodes participated in the power-law network, it wouldn't tear itself apart because they could handle the load. These would become the ultrapeers. The nodes that couldn't handle the demands of a flooding, power-law network would connect to ultrapeers and let the ultrapeers take note of their shared files, and handle search requests for them. Thus, when a peer searches, no peer connected to an ultrapeer ever sees the search unless they have the file being searched for, because the searching happens at a level above them. Between low-capacity nodes and ultrapeers, it's much like a client-server model. Between ultrapeers, it's still a power-law network.
But the ultrapeer network has problems in itself, so this group sought to find a way to search a power-law based network, such as Gnutella, without flooding. They exploited the fact that, in a power-law network, select nodes have very high degree connectivity. If you take a random walk on a power-law based network (meaning, starting from your own PC, randomly jump to a node connected to you, randomly jump to a node connected to that node, etc...) you'll end up at or passing through a node with very high connectivity. Thus, they were a natrual spot rendezvous point for clients wishing to share files, and clients wishing to download files. Perhaps, in this sense, they are an "ultrapeer," but we haven't separated the network into two different architectures like before. The network is still entirely power-law based, and retains all its wonderful properties.
But that's not the entire story, just the gist of it. There are other neat tricks to it... Trust me, this is really good stuff we're talking about here. They recently won Best Paper Award at the 2004 IEEE International Conference on Peer-to-Peer Computing. (See paper here.)
"Brunet," as they call it, is designed to be a framework for any peer-to-peer application that could exploit the percolation search outlined above. Google-like searching is just one possible approach (and perhaps a little unrealistic...). Right now I can tell you that they have a chat program in the works, and it is working well. The framework should be released when it's ready.
Please don't flood me with questions -- remember, I'm not actually in their research group:)
Since a great deal of discussion and awe comes up anytime one of the millenium problems is mentioned (solved?) on Slashdot, I'd just like to say that any layman interested in learning more about the millenium problems should run to his/her library/bookstore and pick up
The Millennium Problems: The Seven Greatest Unsolved Mathematical Puzzles of Our Time. Although, perhaps, for the layman, the end may become a bit tricky (the problems are explained simply in order of increasing difficulty), it's a book worth sticking with, and ultimately worth a read.
- sm
Re:Microsoft is not going down without a fight
on
SIGGraph and Open Source
·
· Score: 4, Insightful
They had a huge booth at SIGGRAPH this year, lots of vapor and FUD.
From the link you provide:
This week at SIGGRAPH 2004, the world's leading computer graphics conference, computer scientists from Microsoft Research's Beijing, Cambridge, U.K. and Redmond, Wash., labs will present the results of 12 research papers, nine of which were done in partnership with universities around the world.
Look, I know it's cool to bash Microsoft and call them "M$" and whatnot, but not just any paper can get accepted to SIGGRAPH. It has to have some merit -- they have very high standards. No papers fly into the SIGGRAPH/SIGCOMM preceedings based on vapor and FUD alone.
Furthermore, Microsoft (in particular, MS Research in Beijing) has been doing some excellent work in graphics technology, and the academic institutions that usually make up the bulk of the research presented aren't afraid to admit it:
"MS Research is by far the biggest contributor to graphics in the corporate world. It's a powerhouse" - Paul Debevec, USC Institute for Creative Technologies "They're really doing first class research." - Victor Zue, MIT CSAIL
Technology Review Magazine has a good look at the advancements of the MS Beijing lab in its June 2004 issue.
Look, I'm no fan of MS either, but please... In the case where they actually do innovate, do research, give credit where credit is due? Double standards help nobody.
These days, in my spare time, I'm writing a p2p program -- think of it as a swarm-download system, like BitTorrent, on an overlay network topology, like eMule (only eMule uses Kademlia, and I'm using Pastry). It has been shown, here and here, that Bloom Filters can drastically reduce the traffic generated when searching peer to peer networks. I recently coded a Java implementation of a Bloom Filter for my p2p program, and it works great in testing. (But the p2p program isn't anywhere near done, so don't ask about it;)
Furthermore, Bloom Filters can be compressed -- see Michael Mitzenmacher's work here. The idea that you can compress a Bloom Filter is a little counter-intuitive, because the size of the bit vector and the number of hash functions are derived using calculus to maximize the compactness of the set, for a given false positive rate -- thus, in this state, it is non-compressable (it is "already compressed" by simply being an optimal Bloom Filter). To compress a bloom filter, you must choose a large bit vector, and a non-optimal number of hash functions, then apply the compression algorithm (typically arithmetic coding). Because the bit vector is so large, it is sparsely populated -- and so compression works.
Often you can save 10% and 20% on the size of your bloom filter, while having a lower false positive rate. Score!
A very nice, very interesting survey of all the applications of Bloom Filters can be found here.
Indeed, there are infinitely many unique bit strings we may take the hash of, and yet only 2^160 hash values they can map to. By the pigeonhole principle, some hash value is mapped to by at least two unique bit strings.
(The pigeonhole principle says that if you shoot N pigeons with N+1 bullets, and don't miss, one pigeon has two holes... or something like that.)
Now hash functions can be classified as either weak collision resistant or strong collision resistant.
A hash function h is weak collision resistant if, given h and a bitstring x, it is impossible to find some other x' such that h(x) = h(x'). Note that x is specified.
A hash function h is strong collision resistant if it is infeasible to compute any collision (x, x') of h.
So, if a collision was found in MD5, it's no longer strong collision resistant (since the person found a pair x, x' such that h(x) = h(x')). Its when MD5 is no longer weak collision resistant that things start to get scary -- meaning, given any arbitrary bit vector, I can find another bit vector that generates the same hash value in a reasonable amount of time. This means that, after you download your favorite Linux ISO, just making sure the MD5 hash checks out does not garuantee the authenticity of the file.
But no worries. There's still SHA-1. And if that isn't good enough, there's its bigger cousins, SHA-256, SHA-384, and SHA-512.
Because the story submitter absent-mindedly forgot, here's the link to Playboy.... Like you didn't know it already, lonely geek! (I bet all the images on the site are "mysteriously" pre-cached.)
Schemes like this to make p2p anonymous have been around for awhile. The problem is that such systems have very high end-to-end latency, so in practice it's not really ideal for a constantly evolving network -- like peer-to-peer. A scheme similar to this, using mixes, is Tarzan. From its ACM paper:
Tarzan is a peer-to-peer anonymous IP network overlay. Because it provides IP service, Tarzan is general-purpose and transparent to applications. Organized as a decentralized peer-to-peer overlay, Tarzan is fault-tolerant, highly scalable, and easy to manage.Tarzan achieves its anonymity with layered encryption and multi-hop routing, much like a Chaumian mix. A message initiator chooses a path of peers pseudo-randomly through a restricted topology in a way that adversaries cannot easily influence.
Such systems right now have too high a latency and too much overhead (such as a peer sending "noise" into the network when not having the need to send any real data, just to deter packet analysis) that they aren't terribly practical... for now. So you most likely won't see the technology bundled in the next KaZaA, BitTorrent, etc., but we'll see what the future holds.
Slashdot Mirror
How about a national database for tracking when everyone uses the restroom. We could put little sensors on all toilets to track how often they're flushed!
There is a prototype here.
- shadowmatter
I like this one better.
"And I'm very pissed off at you god-damned panda-fuckers."
- sm
"If there are features in our products that are subpar or need to be added, then I have great confidence that we are an organization that responds pretty quickly and effectively to that."
Excerpt from the next Ballmer memo:
"Security is not a feature! Security, security, security!!!"
- sm
If I recall correctly, the Microsoftie who said he installed Firefox immediately followed by denouncing its security because he had to install a patch (to go from 0.9 to 0.9.1, IIRC).
I thought the sentiment here was that it's okay to install and try your competitors products -- God knows Microsoft's done it enough times to see what to include in their own product line. Sometimes you have to -- the division that writes MS Office for Mac has no choice but to use OS X, right? But it's pretty low to bring up a competitor's product in an interview just to mention a critical flaw when your own track record is at the bottom of the heap.
- sm
Even the Windows kernel developers rejected them as a bad idea.
MS Developer #1: I was thinking we could put exceptions in the kernel.
MS Developer #2: Are you insane? Why on earth would you want to do that? I don't think I've heard a stupider suggestion for a kernel addition.
MS Developer #1: Really? Well uhh... how about we put an Internet browser in the kernel?
MS Developer #2: FREAKIN BRILLIANT, let me call Bill.
- sm
FireFox is already extremely bloated (on Windows) compared to other Windows applications and the source code is hundreds of meg in size, the reason - it has an entire platform.
Maybe the Mozilla suite, but not Firefox. In my downloads folder at work:
FirefoxSetup-0.8.exe: 6348KB
FirefoxSetup-0.9.exe: 4845KB
Firefox Setup 1.0PR.exe: 4630KB
These are the setup executables for Windows. And if memory serves me correctly, the Thunderbird client has been getting smaller with each new version even more dramatically...
- sm
I suspect the exact details of the erasure codes they're using can be found here, which by no coincidence is written by Petar Maymounkov and David Mazieres (both the authors of the original Kademlia paper). A good primer for erasure codes would be to read up on Reed-Solomon codes, which seek to provide similar end-results as erasure codes.
Rateless codes are important because they are the first step to a "digital fountain" model of data transfer. The idea is this: say you have a file of 10KB. Using erasure codes, you can "oversample" this file -- that is, turn this file into 40 1KB chunks. Now by collecting ANY 10 of these 1KB chunks, you can reconstruct the original file.
The reason the digital fountain is so cool (and the reason for its name) is because it would make the most amazing BitTorrent client ever. Why? In BitTorrent, you're doing things like choking/unchoking, aggressively seeking the rarest pieces, and hoping that some guy who has the ONLY COPY of piece X doesn't leave the network before it is replicated. Using Erasure Codes, everyone would just blindly get whatever data is sent to them (where each data unit is an "oversample"), and blindly forward it on all outbound links. But if you're getting data in this manner, isn't there a chance you'd get the same piece of data twice (which is like getting the same piece twice in BitTorrent, which is no use)? If you oversample enough, you can make the chance of this happening approach 0. Note in this scheme, there's no choking or unchoking here (so you'll never go through a period of time on a rare torrent where EVERYONE is choking you, and your download rate is 0KB/s), and you don't have to worry about that one guy leaving the swarm with some critical piece -- not just because you can always reconstruct it, but also because that piece is no more critical than any other.
It's beautiful, really. So why aren't we doing it? Simple -- erasure codes are computationally expensive to compute, although
they're getting easier as new sorts of erasure codes are being developed, and PCs get faster. The first big breakthrough was with Tornado codes, if I remember correctly. Anyway, we'll see what the future holds...
- shadowmatter
... when a server can sense a Slashdoting approaching from over 4 hops away.
Not quite... Note: I'm about to karma whore here.
:)
About a year ago, right before starting my senior year at UCLA, I was offered an opportunity to work on this P2P project. At the time it was called "Gnucla," and was being developed by the UCLA EE department's Complex Networks Group. I turned it down, because I had already committed to working on a p2p system in the CS department. But since in all honesty their research was more novel than ours (and my friend was in their group), I subscribed to their mailing list and kept informed on what they were doing.
What they've done isn't find a novel way of picking ultrapeers. Let's review what motivated ultrapeers -- in the beginning, there was Gnutella. Gnutella was a power-law based network. What this meant is that there was no real "topology" to it, unlike peer to peer networks that were emerging and based on Distributed Hash Tables (such as Chord, Pastry, Kademlia [on which Coral is based]). It had nice properties: a low diameter, and very resilient to attacks common on p2p networks. (Loads of peers dropping simultaneously could not partition the network, unlike, say, in Pastry -- unless they are high degree nodes.) But the big problem was that to search the network, you had to flood it. And that generated so much traffic that the network eventually tore itself apart under its own load.
So someone thought that maybe if only a few, select, high-capacity nodes participated in the power-law network, it wouldn't tear itself apart because they could handle the load. These would become the ultrapeers. The nodes that couldn't handle the demands of a flooding, power-law network would connect to ultrapeers and let the ultrapeers take note of their shared files, and handle search requests for them. Thus, when a peer searches, no peer connected to an ultrapeer ever sees the search unless they have the file being searched for, because the searching happens at a level above them. Between low-capacity nodes and ultrapeers, it's much like a client-server model. Between ultrapeers, it's still a power-law network.
But the ultrapeer network has problems in itself, so this group sought to find a way to search a power-law based network, such as Gnutella, without flooding. They exploited the fact that, in a power-law network, select nodes have very high degree connectivity. If you take a random walk on a power-law based network (meaning, starting from your own PC, randomly jump to a node connected to you, randomly jump to a node connected to that node, etc...) you'll end up at or passing through a node with very high connectivity. Thus, they were a natrual spot rendezvous point for clients wishing to share files, and clients wishing to download files. Perhaps, in this sense, they are an "ultrapeer," but we haven't separated the network into two different architectures like before. The network is still entirely power-law based, and retains all its wonderful properties.
But that's not the entire story, just the gist of it. There are other neat tricks to it... Trust me, this is really good stuff we're talking about here. They recently won Best Paper Award at the 2004 IEEE International Conference on Peer-to-Peer Computing. (See paper here.)
"Brunet," as they call it, is designed to be a framework for any peer-to-peer application that could exploit the percolation search outlined above. Google-like searching is just one possible approach (and perhaps a little unrealistic...). Right now I can tell you that they have a chat program in the works, and it is working well. The framework should be released when it's ready.
Please don't flood me with questions -- remember, I'm not actually in their research group
- sm
- sm
From the link you provide:
Look, I know it's cool to bash Microsoft and call them "M$" and whatnot, but not just any paper can get accepted to SIGGRAPH. It has to have some merit -- they have very high standards. No papers fly into the SIGGRAPH/SIGCOMM preceedings based on vapor and FUD alone.
Furthermore, Microsoft (in particular, MS Research in Beijing) has been doing some excellent work in graphics technology, and the academic institutions that usually make up the bulk of the research presented aren't afraid to admit it:
"MS Research is by far the biggest contributor to graphics in the corporate world. It's a powerhouse" - Paul Debevec, USC Institute for Creative Technologies
"They're really doing first class research." - Victor Zue, MIT CSAIL
Technology Review Magazine has a good look at the advancements of the MS Beijing lab in its June 2004 issue.
Look, I'm no fan of MS either, but please... In the case where they actually do innovate, do research, give credit where credit is due? Double standards help nobody.
- sm
I heard Apple put up a big billboard across the street from Real's main office, with only one word in big bold letters across it:
BUFFERING
- sm
The Birth of the Lightsaber
Heaven forbid that thing turn on while still in the womb.
- sm
Indeed, Bloom Filters are the shit.
;)
These days, in my spare time, I'm writing a p2p program -- think of it as a swarm-download system, like BitTorrent, on an overlay network topology, like eMule (only eMule uses Kademlia, and I'm using Pastry). It has been shown, here and here, that Bloom Filters can drastically reduce the traffic generated when searching peer to peer networks. I recently coded a Java implementation of a Bloom Filter for my p2p program, and it works great in testing. (But the p2p program isn't anywhere near done, so don't ask about it
Furthermore, Bloom Filters can be compressed -- see Michael Mitzenmacher's work here. The idea that you can compress a Bloom Filter is a little counter-intuitive, because the size of the bit vector and the number of hash functions are derived using calculus to maximize the compactness of the set, for a given false positive rate -- thus, in this state, it is non-compressable (it is "already compressed" by simply being an optimal Bloom Filter). To compress a bloom filter, you must choose a large bit vector, and a non-optimal number of hash functions, then apply the compression algorithm (typically arithmetic coding). Because the bit vector is so large, it is sparsely populated -- and so compression works.
Often you can save 10% and 20% on the size of your bloom filter, while having a lower false positive rate. Score!
A very nice, very interesting survey of all the applications of Bloom Filters can be found here.
- sm
Indeed, there are infinitely many unique bit strings we may take the hash of, and yet only 2^160 hash values they can map to. By the pigeonhole principle, some hash value is mapped to by at least two unique bit strings.
(The pigeonhole principle says that if you shoot N pigeons with N+1 bullets, and don't miss, one pigeon has two holes... or something like that.)
Now hash functions can be classified as either weak collision resistant or strong collision resistant.
A hash function h is weak collision resistant if, given h and a bitstring x, it is impossible to find some other x' such that h(x) = h(x'). Note that x is specified.
A hash function h is strong collision resistant if it is infeasible to compute any collision (x, x') of h.
So, if a collision was found in MD5, it's no longer strong collision resistant (since the person found a pair x, x' such that h(x) = h(x')). Its when MD5 is no longer weak collision resistant that things start to get scary -- meaning, given any arbitrary bit vector, I can find another bit vector that generates the same hash value in a reasonable amount of time. This means that, after you download your favorite Linux ISO, just making sure the MD5 hash checks out does not garuantee the authenticity of the file.
But no worries. There's still SHA-1. And if that isn't good enough, there's its bigger cousins, SHA-256, SHA-384, and SHA-512.
- sm
Or:
Where do you want to go today... while only making three left turns?
- sm
I'm hoping something like the Sims, combined with the BFG.
Having your Sim settle a dispute with his/her ex has never been so exciting.
- sm
Kinda reminds me of THAC0
To Hate to Administrate Cuz-yer-piss-poor-IIS-box-was 0wned!!1
Yeah, I'm really stretching the limits of acronyms there...
- sm
Because the story submitter absent-mindedly forgot, here's the link to Playboy. ... Like you didn't know it already, lonely geek! (I bet all the images on the site are "mysteriously" pre-cached.)
- sm
Python is not the kind of language that lands you a job
Right -- just ask Bram Cohen at Valve...
But anyway, if people can get jobs by having VB on their resume, why not Python?
- sm
Yes.
It's called SplitStream, and you can find it here. Bram Cohen, the creator of BitTorrent, cites it in his BitTorrent economics paper.
Unfortunately, the research on it was sponsored by Microsoft, and so you must swear an oath to Satan every time you use it.
- shadowmatter
Just because MS makes it available doesn't mean they've worked out all the bugs.
You new here?
- sm
Such systems right now have too high a latency and too much overhead (such as a peer sending "noise" into the network when not having the need to send any real data, just to deter packet analysis) that they aren't terribly practical... for now. So you most likely won't see the technology bundled in the next KaZaA, BitTorrent, etc., but we'll see what the future holds.
- sm
... How can I tell?
Sally Struthers is the dean.
- sm