How is it that the nodes are dynamically resizable? Once a node is created, it has a fixed size. If you use sentinals for head and tail they may need to change size, but not very often. Saying that the nodes are changing size during runtime is flat out wrong.
And as for locking, a skiplist is fast enough that locking the whole thing isn't much of a penalty. Besides, if you're clever enough about it you can lock just a portion of the list and not the whole thing (lock top-down, and pre-decide how high the new node will be). True, that makes the code somewhat more complex, but that's nothing compared to any of the tree structures.
Ah, the skiplist. Every time algorithms come up, the skiplist is not paid nearly enough attention.
I know that I've posted this URL once to this article aready, but skiplists are practically ignored, compared to how nifty they are. No balanced tree has a right to exist (except perhaps B-trees because the mesh nice with hardware) with skiplists around:
And I'd like to add 2 more nifty and somewhat ignored algorithms: the Burrows-Wheeler Transform and the Discreet Cosine Transform. Burrows-Wheeler is what gives us bzip, and Discreet Cosine is what gives us JPEG and MPEG. Heck, while I'm on a compression kick, lets add MTF (move-to-front) and Huffman Codes.
Re:Basic of algorithms
on
Deep Algorithms?
·
· Score: 5, Informative
An algorithm is simply a series of steps one can take that, once you have finished them, will have solved your problem. A deep algorithm is one that is especially useful, applicable in many circumstances, and has some inate cleverness that makes it non-trivial to come up with.
So, for example, an algorithm for searching could be:
1. For i first item to last item
2. If item i is what you are looking for, return it
3. otherwise, go onto the next i.
This isn't a very fancy algorithm, but it works, and it is useful in many many circumstances. Of course, it is also trivial to come up with (look at every item one at a time untill you find your goal), and therefore isn't deep.
It is interesting to compare an algorithm to a heuristic. Heuristics would make great algorithms, if not for the bugs. That is, a heuristic is a set of steps you can follow that are likely to solve your problem, but aren't guarunteed. In that sense, they're just buggy algorithms.
There are also approximation algorithms. Suppose your problem is to find the shortest route that will visit a set of cities, and return you to your starting point. This, btw, is a classic problem called the Traveling Salesman Problem, and is provably rather nasty to solve (it belongs to a class of problems called "NP-Complete"). That is, if you want the SHORTEST route, the best know method is to try all possible routes (and for even a relatively few cities, that's a lot). However, there are algorithms, that if you follow them, are guarunteed to give you an answer no worse than twice as long as the best possible. That is, we can approximate the answer, within some provable bound of optimal, with a set deterministic steps. (For the nitpickers, the approximation only works with Euclidian TSP, not general TSP, and.: doesn't give a solution to the Hamiltonian Cycle problem).
Any other questions?
Well, technically a data structure
on
Deep Algorithms?
·
· Score: 5, Interesting
My personal favorite is the skiplist. O(ln n) insert, search, and delete in the average case. Simple to understand, has good constant factors, doesn't require maintence (unlike trees). Really, what more could you want?
I've seen copies of LoTR, in true DVD quality. Copied from a DVD. The guy who did the rip didn't even bother to remove the notice that this disc is for viewing only by members of the Actor's Guild, only in preperation for the Oscars...
How about voluntary (and strictly volutary, not fake volutary like not required to give your SSN, yeah right) for citizens, and mandatory for foriegners.
Right now the US has one of the most open and insecure immigration policies in the world. Canada's is worse (claiming asylum is an automatic in), but the minor barriers to entry the US puts up is hardly better than nothing at all.
Yes, there is the threat of domestic terrorism. However, that is currently very low. The militia movement is nearly dead, and the few remainding threats are under close surviellence already. The threat of random law-abiding citizens conducting an act of terrorism without displaying very prominent warning signs (ie joining one of said militias) ahead of time is nearly zero. Especially now, the threat that is real is from outside.
Now, you might wonder how this will help. Well, if you put checks in place to ensure that people acquiring other forms of ID (drivers licences) are run through to make sure they aren't in the foriegn system, one can prevent them from getting other authentic ID's with fake information. Mark those other ID's to indicate the national ID must also be offered. Yes, it doesn't solve the problem of counterfeit ID's, but it's better the other proposals. Well, I think so. What to all 'yall think?
Mem subsystem is what I've heard.
on
Itanium Update
·
· Score: 1
From what I've heard from a friend who's gone from DEC to Compaq to Intel, they're mostly interested in the memory subsystem and the bus. The moveover from "Alpha" to "Intel" is supposed to take a while though. He says that one more release of the Alpha is going to be made, a few minor revisions, and then no more. The whole Alpha team will be engulfed by 2007 (I think?), but gradually.
One can hope that one the first subteams to move over is whoever designed the Alpha bus. It might be a bit more expensive, but it's better than that POS that Intel is currently using.
I'm finding it a little scary that all of the people I know who really disliked Intel are now working for them. Alpha just plain got bought, and everyone I know at HP is helping with McKinley. Freaky.
I don't know about that particular story, but a good one along the same lines was written by Robert Heinlein: "Let There Be Light", published along with others in "The Man Who Sold the Moon".
In "Let There Be Light", a scientist discovers a method for building nearly 100% efficient solar panels. At first keeps it secret, and manufactures them himself. However, the oil companies file frivolous lawsuits against him, hire thugs to burn down his factory, torch his demonstration solar car, and threaten violence against his person. So finally he patents it, goes to the big papers, and gives them a big juicy story, on the condition that they also publish all of the technical details. Oh, and openly licenses it for pennies a square yard.
It is a shame that we may have to take the same route, but getting technical details published in a big publication like the New York Times, the Washingon Post, or the Chicago Tribune would be a good way to go. Especially the New York Times. What judge would censor the "Grey Lady"? She's nearly as sacrosant as the Statue of Liberty. Joe Sixpack might not care if some IEEE or ACM publication is censored, but the New York Times is one of the most respected papers in the nation, if not worldwide.
There's no need to hide your publication, but just make it painfully obvious that censoring the publication of these ideas is a direct affront to First Amendment rights.
Find out where they live, and get a gift certificate to some place in the area. Any pizza place should be happy to mail a gift certificate to you over the phone, payment through credit card. Or a national chain, like Hooters, is also good. And a lot cheaper to ship than a keg...
The reason CSS is fundementally flaws is not that they didn't test it, but that the concept itself is flawed. You cannot give someone a hunk of data, and a way to decode that data, and think they will be unable to come up with another way of decoding the data then the way you made.
Yes, the concept behind CSS is flawed. Given that I have physical access to the hardware, and total control over the runtime environment of any software implementations, it is impossible for a perfect lockdown. Hardware is much harder to figure out, but there are no foolproof ways of making reverse engineering impossible (although some methods are damn good).
However, the CSS algorithm itself was flawed, as well as the design of the system itself. Even if Xing's key was kept secret, flaws in the algorithm itself meant that it was only a matter of time before CSS was cracked wide open. I believe that the effective key length of CSS is only about 20 bits (or was it 40?), even though the actual key length is much longer. That's a fairly flawed algorithm, and makes a brute force attack childs play. With a system that bad, you are basing your security on having a secret algorithm. But one of the key principles of crypto is that you should assume that your enemy has access to everything except your key. They know your algorithms, they have large quantities of choosen plaintext, and they have lots and lots of resources at their disposal. CSS's security was based on having a secret key, but design flaws made that ineffective, leaving only the secret nature of the algorithm.
But yes, the attack that was first done on CSS was made much easier by very poor security in Xing. Regardless, even without an easily reverse engineered software imp of CSS, it would have fallen eventually. The Japanese cipher PURPLE was broken during WWII. The people who broke it never recieved even a vague description of the official PURPLE cipher machine. To this day nobody really knows how PURPLE worked (all of the machines were destroyed before being captured). But dispite having a hidden algorithm, it was cracked.
So, yes, handing people a software player is a surefire way to get cracked. But CSS's flaws run much deeper than that.
They didn't want software DES available because it is much harder to regulate. If DES is available hardware only, then they can make sure that the hardware is only exported to trustworthy companies. Software is more ethereal, and therefore much harder to control.
Just look at PGP. Easily available anywhere, and totally beyond any government's ability to control. DES hardware, on the other hand, is something physical that you can stop at the boarder, confiscate, track, etc. Copying DES hardware is something that no terrorist organization has the resources to do. Copying PGP, however, is mindnumbingly easy. Simply by being in hardware makes it much easier control DES than PGP. Of course, now that there are software implementations of DES, DES is out of the bag too. But this is about crypto control in the early 80's.
Lucifer was being developed for a product, which eventually became DES. IBM didn't set out to create DES, they set out to take this Lucifer thing that they had and turn it into something they could sell. When they realized what they had would blow any other DES submission out of the water, they submitted it. DES is a cipher that sprang from the development of Lucifer.
I didn't mention it, but one of the conditions (among many) that the NSA gave in exchange for their help was that IBM make it hardware only. I've heard someone say that DES sucks performancewise today because it was meant to be easy to do in 1970's hardware, but difficult to impossible by design to do in the software of the day. The 56-bit key was not a hardware issue, however, and even after much slimming, the pre-NSA view of DES/Lucifer was 128 bit (slimmed down from 256?), with much more elegent S-Boxes and simpler rounds, to be done in hardware for speed reasons. Even just before 56-bit was announced, IBM had done signifigent hardware design work on a 64-bit version. The small keysize was entirely the NSA's doing. The simplification of the algorithm was a combination of making it doable in HW (for commercial reasons), and better design (security reasons).
56 bit may have been "strong", but IBM knew at the time that in a few years it wouldn't be good enough. I believe that much of the public commentatry submitted to NIST about DES was that the keysize was strangely small. 56 bit was hard to break, but IBM estimated that dedicated hardware could bring the cost of decrypts down to about 10K each, amortized over 1 year. NIST gave ridiculously large estimates on the strength of 56-bit, saying it would take on the order of 200 million to build a machine to crack a handful a week. Only the gullible believed those numbers. The IBM numbers were done without even the benefit of Moore's law, and were therefore also pretty high. 56 bit was sufficient, but not strong.
But yes, DES isn't strictly Lucifer. Lucifer was the precursor to DES, and DES is the result of highly refining Lucifer. And yes, the NSA had no intention of allowing software DES out if they could help it.
The NSA didn't explain anything unnecessary to IBM. They also forbid IBM from discussing the reasoning behind IBM's own design changes, or even the design itself. The world has the algorithm, and any idea of why it works is up to ppl to figure out themselves.
The general feeling is that the NSA did not do anything to purposely weaken DES's basic algorithm. First off, nobody has found any truly effective attacks against DES. Bruteforce, of course, but that isn't basic to the algorithm, and besides, 3DES provides more than adequate protection. DES is also slightly vulnerable to differential (know plaintext) attacks. Differential attacks were (re)discovered by IBM, and they changed DES to prevent against it. The NSA knew about such attacks (and kept the knowledge to itself) for some unknown long time, probably before Lucifer was even somebody's dream. While the NSA did change the S-Boxes, the changes strengthened DES against some differential attacks, rather than weakening it.
Besides a lack of evidence, it was/is probably beyond the ability of even the NSA to weaken DES and get away with it. Such a weakening would have to masquarade as a strengthening, or else IBM wouldn't accept it, would have to be so subtle that it wouldn't be caught, and still leave DES strong against any other concievable attack. Making a strong code is hard enough. Making a code that seems strong, that you do not have 100% control over, and leaving one but only one subtle hole in it is probably impossible even today.
Overall, the NSA probably honestly tried to make the basic algorithm strong. The changes they made to the S-Boxes were probably geared towards differntial attacks, which the IBM'ers had only just discovered, and probably didn't understand some subtle point of. They did, however, weaken the key. 56 bits was probably low enough that they could brute force an intercept if they really really needed it, but high enough to lock out everybody else, with the possible exception of the KGB. But of course anything that the KGB would want badly enough to brute force in such a manner probably wouldn't be encrypted with DES, but with a stronger secret cipher. If the S-Boxes were weak, however, and an enemy discovered the NSA's trap door, then the enemy could decrypt everything, and sift through for tidbits later.
Some PDF encryption is strong, some is weak. What was attacked by Dmitry was the plugin protocol, which is weak. Adobe itself isn't really in the market of encryption, but in a protocol that allows restricion of usage in certain ways. Many vendors provide plugins that use the protocol, and many of their plugins have cryptographic weaknesses. The plugins themselves are moot, however, as the protocol blows.
First, lets go over why 3DES and RSA haven't been cracked. DES was developed by IBM, for use as a commercial product. The original design was developed by a pretty bright guy, who, among other things, had attended a few NSA sponsered talks, and knew about some nifty new things (like S-Boxes). When IBM decided to turn his cipher (Lucifer) into a product, they got worried that if it was broken, they'd be mega-liable. Therefore they busted their asses trying to break it. In the process they (re)discovered many types of attacks, include differential attacks (a type of chosen plaintext attack). Somebody noticed that NIST had asked for ciphers and nobody had a good submission, so IBM submitted Lucifer. BUT they were still worried about it, and spent more time refining it. The NSA didn't want free crypto going loose, and offered to give it their seal of approval if IBM would cooperate fully. IBM didn't want to be liable if Lucifer had a small flaw, so they agreed. The NSA then also joined the groups of people attacking Lucifer, and helped the IBM team avoid differential attacks (which they had already done, but NSA offered refinements). The only bad thing the NSA did was cut the key length. Lucifer was submitted, and became DES.
Now, the whole point of this is that it took a long time and many many manhours of very bright people attacking the cipher, and coming up with design principles to help avoid the attacks, because IBM DID NOT want to release a cipher without doing it's damndest to guaruntee it was secure. They invited outsiders from all over (including the NSA) to attack and comment on it. A lot of work was put into it initially.
If DES had an easy attack against it, it would have been found, the design principles would have been revised, and hopefully the entire class of attacks would be taken care of.
RSA was similar. R and S came up with ciphers, and tried to break them. When they thought they had something good, they'd hand it over to A, who would then break it (supposedly he broke the first 31 attempts without any trouble). This is the same cycle IBM did: a team designs it, submits to others who will attack it, they get feedback and refine it. After the original RSA was OK'ed by R S and A, they gave it to colleages to try and break. Who failed.
My point is that all successful ciphers have gone through extensive work. Many many ciphers developed in the course of coming up with good ones are scraped. Only a few are secure. The best ciphers have been analysed by many people for a long time before they even see the light of day.
CSS was not put through such a process. They developed it, and never submitted it to the glare of public scrutiny. It contains glaring design flaws, that even a small amount of competitive attacking would have found. But it was never submitted to such, and therefore deployed before it was proved secure. The PDF security model (which Dmitry broke) was also not given a public vetting before release. (BTW, Dmitry didn't break crypto, he broke the protocol. However, many of the encryption schemes used in eBooks are proprietary designs that haven't been put to public scrutiny, and are therefore likely weak) I haven't chewed through the details of the 802.11 break, but 802.11, while it has been submitted to public scrutiny, hasn't been there very long.
It isn't that the codes are bad, but that most codes developed are crap. If you want a good code, take a code, and try as hard as you can to break it. Ask your friends/hire independant consultants to break it. Then, release it to the public to break it. Only then can you have any confidence that it is secure. And at that, if a new code hasn't been around for a while, it's probably crap. Most codes are easily broken. Scrutiny breaks the easily broken ones, leaving the strong ones for wider use.
Well, the particular book in question (And Then There Were None) appears to have a copy published by Mass Market Paperback, so this particular copyright has expired.
Some of her other works, I expect, as she lived until the '80's. The death of the author doesn't terminate all of the copyrights, but (under current law at least) 70 years later. If it was published before Jan 1 1923 it is in the public domain no matter what. So if she published it after '23 it is still copyrighted.
By contrast, the telecom network is the opposite: a smart network with dumb terminals. The intelligence and thus control of the network is contained in the switching technology, allowing the operator to ensure and contract a given quality of service. This allowed the pre-breakup AT&T to promote their famous "Five 9s" performance, 99.999% reliability. The ability to control access and routing also allowed higher margins, and thus profitability, despite the high startup costs.
Umm, wasn't the entire idea behind a packet network is that it was more robust than a traditional centralized network? If you loose a node in a centralized network, everybody that goes through that node is screwed, as your topology closely resembles a minimum spanning tree. Anybody looking for an example of an unreliable minimum spanning tree should take a look at EFNet.
Even today, if there is a natural disaster somewhere, and everybody wants to call their family in $PLACE to see if they are alright, the phone service in $PLACE goes to pot.
A packet network (like the internet) however, will just start dumping packets. Everybody's comminications will EVENTUALLY (for TCP/IP at least) get through, although the throughput will suck rocks through a swizzle stick. The entire point of a packet network is building a reliable network out of unreliable parts. A centralized network is no more reliable than the parts that it is made of, though. Saying that ATT achieved 5 9's is a bunch of crap.
Specifically, a company has to use due dilligence in preventing it from becoming public knowledge. So, if Coca-Cola leaves copies of it's secret formula lying around, they can loose their trade secret protection.
In fact, if you look in the Nolo definition, they say:
Sensible precautions include, for example, marking documents containing trade secrets "Confidential," locking trade secret materials away after business hours, maintaining computer security and limiting access to secrets to people with a reasonable need to know.
Which indicates to me that by allowing its computers to become infected with SirCam a company has not taken the necessary sensible precautions, and is fair game.
Now, you could say that some of these employees are disclosing things that they have no right to disclose, and trade secret protection still exists. However, it is the company's duty to prevent the SirCam infection, not necessarily the individual employees. It is an interesting thing to consider: does the carelessness of the company in becoming infected count as failing to properly keep their secret? I'm sure if SirCam was used as a tool to dupe a specific company into releasing specific information it would count as industrial espionage. However, at this point SirCam is something that is just out there as a general threat, and it means that if you do not take adequate precautions against it your (possible secret) information will be made available to other people.
Now, if you accidently recieve something that is clearly marked as cinfidential, it probably is still protected. But if there is no such clear marking, or if the "confidential" file is spewed all over the place, regardless of marking, I'd think that the former owner of the trade secret is SOL.
VeriSign is claiming that their competitors are blatantly defrauding them, and that the evidence provided to VeriSign of the customers wanting to switch is falsified. Looks to me as if VeriSign is the one whose lying. Their analysis of the evidence (as presented in the letter) is bogus.
one provided copies of several e-mails described as having come from more than 20 different customers-all using exactly the same wording and type font; and another provided identical e-mails, all dated after the VeriSign Registrar's request, and claimed that they showed prior customer intent to transfer
Now, must ask VeriSign, how many ways are there to word a registrar switch? "Dear Verisign - we are dumping your ass for a better registrar?". No, they're all probably a standard business letter layout, with a body of:
Dear $ACCOUNTMANAGER
We are switching to using $REGSTRAR as our domain name registrar.
Thank you
$CUSTOMERNAME
There aren't that many ways to do it. In fact, if a large ISP was switching a lot of customers (read the main article), the wording should be the same. And as for same font, umm, wouldn't that be more dependant on the person printing them out? Last time I checked, email didn't embed the font (unless you use html, and not even always then), and that the font would be the same if they were printed by the same person. Nothing unusual at all in that. Hey, here's an open offer to VeriSign: 5 bucks if the font isn't Courier. My $5 is perfectly safe...
Now, the second set of emails being exactly identical is a bit erie, but as I said above, there are two good explinations: there are very few ways to politely word "go f*ck off verisign", and if a big ISP were switching customers they should be identical. As for the dates, well, if someone forwarded them, the email header would have the date of forwarding. And if they were printed, then they would all have the print date. Either way, it would be weird if the dates were before (not after, as stated) VeriSign's request, since that would mean the competing registrar anticipated VeriSign's request.
I doubt that Mr. Lynn (the President of ICANN) won't catch on to VeriSign's obvious attempt at fooling him. And I doubt that VeriSign will like the consequences.
The stuff they say about certain HP printers is true too. We have a HP LaserJet 4000N, and it's been going down all day. The secretary (who's since gone home) has been confused as all else as to why the printer keeps giving some strange error. I'd guess that all HP's that use the same internal network spooler will have the same problem.
The FSF registers most of their copyrights. That means that they can get punative damages if it is violated. While I'm sure the FSF would be happy to ignore past violations if you open up the code, simply stopping may not always be enough.
If you really really stretch things, you can file a patent and wait an eternity before it becomse public domain. The USPTO has no trouble collecting that late fee over and over and over again. I don't remember the details, but there is a patent involving machine vision that was filed in the 50's, but only was granted in the last 10-20 years. The original inventor is dead, but the foundation he created to handle his patents is trying to claim that his patents can cover bar-code scanners.
If somebody remembers the guy's name, it would be nice to put it up. The guy has a huge collection of patents, and has taken huge advantage of that particular hole in the patent system. That and that they allow unlimited modification of the wording of your patent so long as it is true to the original spirit of the filing (read: remotely close).
First, they aren't mucking with the TOC, but putting delibrate errors in the data, and mucking with the ECC
However, they are still selling CDs which aren't standards compliant. This leads to a rather interesting question: If you sell a "CD" that purposely doesn't conform to the standard, is it fraudulent to sell it as a CD? It could be possible to claim that as their CDs don't have the proper ECC, they are lacking a standard feature present in all other functional and non-damaged CD's, and the manufacturers are knowingly selling a defective product.
I doubt that they could be hit under fair-use laws, but if the packaging of the CDs claim that they are normal CDs, without mentioning the copy protection, they might be liable under consumer protection laws.
Apparently you're fairly new here. If you weren't, you'd know that it is next to impossible to get a refund for Windows. MS says it's the vendor's problem, but the vendors are prohibited from releasing what they were charged for Windows, and they therefore can't give a refund either.
What MS did wrong was imposing such rules on the hardware vendors. If they wanted to sell machines with Windows on them at all, they could only sell machines with Windows on them. Well, yes, they could get retail copies, but the price difference is so unreasonable that nobody could make a profit selling that way. MS effectively prohibited anybody from selling PC's without including a MS OS.
Price discrimination, which is what MS was practicing with their agreements, is illegal in many countries, and in the US, if you are a monopoly, it is very suspicious and indicative of possible monopolistic abuse (aka, also illegal).
As for buying parts and assembling them, that is not always a valid option. What percentage of the general population is hardware savvy enough to do that? Hell, what percentage of slashdot readers are using a wholly custom box? Hmmm? I doubt that even here on/. it is over 40%.
Why don't you grow an opinion of your own. Astroturf is pretty damn ugly.
7 Experts Write Off After a Journalism Test By Joe Sixpack
Wurshington Past Staff Writer
To test loosy summarization techniques, we recruited a diverse panel of readers: two linux advocates, a gamer, a cheerleader, a MBA, and two MS windows users.
We had them read summarized versions of two articles: "MS beats Linux in Mindcraft Test" and "New Detonater 17 Drivers Released by nVidia".
The tests were conducted in a home environment with an ordinary browser. We focused most of our attention on JohnKatz and ZDNet, the two most fanatical formats, with Tom's Hardware and MSNBC, the unbiased and more journalistically responsible formats, given more limited tests.
Of the seven readers, two couldn't differentiate between JohnKatz and ZDNet. The other 5 agreed that JohnKatz was the least realistic, with Tom's Hardware better and MSNBC reading best of all.
"JohnKatz just started blathering in the Mindcraft story. There was a lot of cruft about freedom and how OSS rules, but the real content was cut out completely" said Duke Fraggem, a hard-core gamer. "Tom's Hardware, on the other hand, man, you could even read the friggin' frame rate in the benchmark's section"
Betty Bouncealot, a professional cheerleader, said "I thought it was funny that the MSNBC article cut that Demonitator thingy out completely, not even a headline. But at least it was the least confusing of the articles."
Both of our linux advocates felt that the ZDNet article totally destroyed the readability of the "Mindcruft" article. "It seemed made-up and artificial, like they didn't even review the facts at all," said Colonel Kernel Sanders, a RedHat staffer. "I couldn't even finish reading it, it was to painful" was all Joe "OSS" Bloggs had to say about it.
One thing that all of the readers agreed upon was that JohnKatz was the worst of the summerizing formats. Sanders said the nVidia article lost a lot of "sense." Bob and Clippy, the Windows users, blamed this on the way JohnKatz shaves off the sanity and content from articles. John Doe, who holds an MBA from Harvard, noted that the sanity of a JohnKatz article abruptly terminated, compared to ZDNet's gradual fadeout.
On a tiny PDA screen -- the kinds of environments where many articles are read -- the loss of information would probably go unnoticed.
But Bloggs worried about how the loss of subtle information meant less journalistic integrity overall. "Those little details give you a lot of information about what really happened."
Slashdot Mirror
How is it that the nodes are dynamically resizable? Once a node is created, it has a fixed size. If you use sentinals for head and tail they may need to change size, but not very often. Saying that the nodes are changing size during runtime is flat out wrong.
And as for locking, a skiplist is fast enough that locking the whole thing isn't much of a penalty. Besides, if you're clever enough about it you can lock just a portion of the list and not the whole thing (lock top-down, and pre-decide how high the new node will be). True, that makes the code somewhat more complex, but that's nothing compared to any of the tree structures.
Ah, the skiplist. Every time algorithms come up, the skiplist is not paid nearly enough attention.
I know that I've posted this URL once to this article aready, but skiplists are practically ignored, compared to how nifty they are. No balanced tree has a right to exist (except perhaps B-trees because the mesh nice with hardware) with skiplists around:
ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdfAnd I'd like to add 2 more nifty and somewhat ignored algorithms: the Burrows-Wheeler Transform and the Discreet Cosine Transform. Burrows-Wheeler is what gives us bzip, and Discreet Cosine is what gives us JPEG and MPEG. Heck, while I'm on a compression kick, lets add MTF (move-to-front) and Huffman Codes.
An algorithm is simply a series of steps one can take that, once you have finished them, will have solved your problem. A deep algorithm is one that is especially useful, applicable in many circumstances, and has some inate cleverness that makes it non-trivial to come up with.
So, for example, an algorithm for searching could be:
1. For i first item to last item2. If item i is what you are looking for, return it
3. otherwise, go onto the next i.
This isn't a very fancy algorithm, but it works, and it is useful in many many circumstances. Of course, it is also trivial to come up with (look at every item one at a time untill you find your goal), and therefore isn't deep.
It is interesting to compare an algorithm to a heuristic. Heuristics would make great algorithms, if not for the bugs. That is, a heuristic is a set of steps you can follow that are likely to solve your problem, but aren't guarunteed. In that sense, they're just buggy algorithms.
There are also approximation algorithms. Suppose your problem is to find the shortest route that will visit a set of cities, and return you to your starting point. This, btw, is a classic problem called the Traveling Salesman Problem, and is provably rather nasty to solve (it belongs to a class of problems called "NP-Complete"). That is, if you want the SHORTEST route, the best know method is to try all possible routes (and for even a relatively few cities, that's a lot). However, there are algorithms, that if you follow them, are guarunteed to give you an answer no worse than twice as long as the best possible. That is, we can approximate the answer, within some provable bound of optimal, with a set deterministic steps. (For the nitpickers, the approximation only works with Euclidian TSP, not general TSP, and .: doesn't give a solution to the Hamiltonian Cycle problem).
Any other questions?
My personal favorite is the skiplist. O(ln n) insert, search, and delete in the average case. Simple to understand, has good constant factors, doesn't require maintence (unlike trees). Really, what more could you want?
Here's the paper:
ftp://ftp.cs.umd.edu/pub/skipLists (many formats)PDF
Umm, not always.
I've seen copies of LoTR, in true DVD quality. Copied from a DVD. The guy who did the rip didn't even bother to remove the notice that this disc is for viewing only by members of the Actor's Guild, only in preperation for the Oscars...
How about voluntary (and strictly volutary, not fake volutary like not required to give your SSN, yeah right) for citizens, and mandatory for foriegners.
Right now the US has one of the most open and insecure immigration policies in the world. Canada's is worse (claiming asylum is an automatic in), but the minor barriers to entry the US puts up is hardly better than nothing at all.
Yes, there is the threat of domestic terrorism. However, that is currently very low. The militia movement is nearly dead, and the few remainding threats are under close surviellence already. The threat of random law-abiding citizens conducting an act of terrorism without displaying very prominent warning signs (ie joining one of said militias) ahead of time is nearly zero. Especially now, the threat that is real is from outside.
Now, you might wonder how this will help. Well, if you put checks in place to ensure that people acquiring other forms of ID (drivers licences) are run through to make sure they aren't in the foriegn system, one can prevent them from getting other authentic ID's with fake information. Mark those other ID's to indicate the national ID must also be offered. Yes, it doesn't solve the problem of counterfeit ID's, but it's better the other proposals. Well, I think so. What to all 'yall think?
From what I've heard from a friend who's gone from DEC to Compaq to Intel, they're mostly interested in the memory subsystem and the bus. The moveover from "Alpha" to "Intel" is supposed to take a while though. He says that one more release of the Alpha is going to be made, a few minor revisions, and then no more. The whole Alpha team will be engulfed by 2007 (I think?), but gradually.
One can hope that one the first subteams to move over is whoever designed the Alpha bus. It might be a bit more expensive, but it's better than that POS that Intel is currently using.
I'm finding it a little scary that all of the people I know who really disliked Intel are now working for them. Alpha just plain got bought, and everyone I know at HP is helping with McKinley. Freaky.
I don't know about that particular story, but a good one along the same lines was written by Robert Heinlein: "Let There Be Light", published along with others in "The Man Who Sold the Moon".
In "Let There Be Light", a scientist discovers a method for building nearly 100% efficient solar panels. At first keeps it secret, and manufactures them himself. However, the oil companies file frivolous lawsuits against him, hire thugs to burn down his factory, torch his demonstration solar car, and threaten violence against his person. So finally he patents it, goes to the big papers, and gives them a big juicy story, on the condition that they also publish all of the technical details. Oh, and openly licenses it for pennies a square yard.
It is a shame that we may have to take the same route, but getting technical details published in a big publication like the New York Times, the Washingon Post, or the Chicago Tribune would be a good way to go. Especially the New York Times. What judge would censor the "Grey Lady"? She's nearly as sacrosant as the Statue of Liberty. Joe Sixpack might not care if some IEEE or ACM publication is censored, but the New York Times is one of the most respected papers in the nation, if not worldwide.
There's no need to hide your publication, but just make it painfully obvious that censoring the publication of these ideas is a direct affront to First Amendment rights.
Find out where they live, and get a gift certificate to some place in the area. Any pizza place should be happy to mail a gift certificate to you over the phone, payment through credit card. Or a national chain, like Hooters, is also good. And a lot cheaper to ship than a keg...
The reason CSS is fundementally flaws is not that they didn't test it, but that the concept itself is flawed. You cannot give someone a hunk of data, and a way to decode that data, and think they will be unable to come up with another way of decoding the data then the way you made.
Yes, the concept behind CSS is flawed. Given that I have physical access to the hardware, and total control over the runtime environment of any software implementations, it is impossible for a perfect lockdown. Hardware is much harder to figure out, but there are no foolproof ways of making reverse engineering impossible (although some methods are damn good).
However, the CSS algorithm itself was flawed, as well as the design of the system itself. Even if Xing's key was kept secret, flaws in the algorithm itself meant that it was only a matter of time before CSS was cracked wide open. I believe that the effective key length of CSS is only about 20 bits (or was it 40?), even though the actual key length is much longer. That's a fairly flawed algorithm, and makes a brute force attack childs play. With a system that bad, you are basing your security on having a secret algorithm. But one of the key principles of crypto is that you should assume that your enemy has access to everything except your key. They know your algorithms, they have large quantities of choosen plaintext, and they have lots and lots of resources at their disposal. CSS's security was based on having a secret key, but design flaws made that ineffective, leaving only the secret nature of the algorithm.
But yes, the attack that was first done on CSS was made much easier by very poor security in Xing. Regardless, even without an easily reverse engineered software imp of CSS, it would have fallen eventually. The Japanese cipher PURPLE was broken during WWII. The people who broke it never recieved even a vague description of the official PURPLE cipher machine. To this day nobody really knows how PURPLE worked (all of the machines were destroyed before being captured). But dispite having a hidden algorithm, it was cracked.
So, yes, handing people a software player is a surefire way to get cracked. But CSS's flaws run much deeper than that.
They didn't want software DES available because it is much harder to regulate. If DES is available hardware only, then they can make sure that the hardware is only exported to trustworthy companies. Software is more ethereal, and therefore much harder to control.
Just look at PGP. Easily available anywhere, and totally beyond any government's ability to control. DES hardware, on the other hand, is something physical that you can stop at the boarder, confiscate, track, etc. Copying DES hardware is something that no terrorist organization has the resources to do. Copying PGP, however, is mindnumbingly easy. Simply by being in hardware makes it much easier control DES than PGP. Of course, now that there are software implementations of DES, DES is out of the bag too. But this is about crypto control in the early 80's.
Lucifer was being developed for a product, which eventually became DES. IBM didn't set out to create DES, they set out to take this Lucifer thing that they had and turn it into something they could sell. When they realized what they had would blow any other DES submission out of the water, they submitted it. DES is a cipher that sprang from the development of Lucifer.
I didn't mention it, but one of the conditions (among many) that the NSA gave in exchange for their help was that IBM make it hardware only. I've heard someone say that DES sucks performancewise today because it was meant to be easy to do in 1970's hardware, but difficult to impossible by design to do in the software of the day. The 56-bit key was not a hardware issue, however, and even after much slimming, the pre-NSA view of DES/Lucifer was 128 bit (slimmed down from 256?), with much more elegent S-Boxes and simpler rounds, to be done in hardware for speed reasons. Even just before 56-bit was announced, IBM had done signifigent hardware design work on a 64-bit version. The small keysize was entirely the NSA's doing. The simplification of the algorithm was a combination of making it doable in HW (for commercial reasons), and better design (security reasons).
56 bit may have been "strong", but IBM knew at the time that in a few years it wouldn't be good enough. I believe that much of the public commentatry submitted to NIST about DES was that the keysize was strangely small. 56 bit was hard to break, but IBM estimated that dedicated hardware could bring the cost of decrypts down to about 10K each, amortized over 1 year. NIST gave ridiculously large estimates on the strength of 56-bit, saying it would take on the order of 200 million to build a machine to crack a handful a week. Only the gullible believed those numbers. The IBM numbers were done without even the benefit of Moore's law, and were therefore also pretty high. 56 bit was sufficient, but not strong.
But yes, DES isn't strictly Lucifer. Lucifer was the precursor to DES, and DES is the result of highly refining Lucifer. And yes, the NSA had no intention of allowing software DES out if they could help it.
The NSA didn't explain anything unnecessary to IBM. They also forbid IBM from discussing the reasoning behind IBM's own design changes, or even the design itself. The world has the algorithm, and any idea of why it works is up to ppl to figure out themselves.
The general feeling is that the NSA did not do anything to purposely weaken DES's basic algorithm. First off, nobody has found any truly effective attacks against DES. Bruteforce, of course, but that isn't basic to the algorithm, and besides, 3DES provides more than adequate protection. DES is also slightly vulnerable to differential (know plaintext) attacks. Differential attacks were (re)discovered by IBM, and they changed DES to prevent against it. The NSA knew about such attacks (and kept the knowledge to itself) for some unknown long time, probably before Lucifer was even somebody's dream. While the NSA did change the S-Boxes, the changes strengthened DES against some differential attacks, rather than weakening it.
Besides a lack of evidence, it was/is probably beyond the ability of even the NSA to weaken DES and get away with it. Such a weakening would have to masquarade as a strengthening, or else IBM wouldn't accept it, would have to be so subtle that it wouldn't be caught, and still leave DES strong against any other concievable attack. Making a strong code is hard enough. Making a code that seems strong, that you do not have 100% control over, and leaving one but only one subtle hole in it is probably impossible even today.
Overall, the NSA probably honestly tried to make the basic algorithm strong. The changes they made to the S-Boxes were probably geared towards differntial attacks, which the IBM'ers had only just discovered, and probably didn't understand some subtle point of. They did, however, weaken the key. 56 bits was probably low enough that they could brute force an intercept if they really really needed it, but high enough to lock out everybody else, with the possible exception of the KGB. But of course anything that the KGB would want badly enough to brute force in such a manner probably wouldn't be encrypted with DES, but with a stronger secret cipher. If the S-Boxes were weak, however, and an enemy discovered the NSA's trap door, then the enemy could decrypt everything, and sift through for tidbits later.
Some PDF encryption is strong, some is weak. What was attacked by Dmitry was the plugin protocol, which is weak. Adobe itself isn't really in the market of encryption, but in a protocol that allows restricion of usage in certain ways. Many vendors provide plugins that use the protocol, and many of their plugins have cryptographic weaknesses. The plugins themselves are moot, however, as the protocol blows.
First, lets go over why 3DES and RSA haven't been cracked. DES was developed by IBM, for use as a commercial product. The original design was developed by a pretty bright guy, who, among other things, had attended a few NSA sponsered talks, and knew about some nifty new things (like S-Boxes). When IBM decided to turn his cipher (Lucifer) into a product, they got worried that if it was broken, they'd be mega-liable. Therefore they busted their asses trying to break it. In the process they (re)discovered many types of attacks, include differential attacks (a type of chosen plaintext attack). Somebody noticed that NIST had asked for ciphers and nobody had a good submission, so IBM submitted Lucifer. BUT they were still worried about it, and spent more time refining it. The NSA didn't want free crypto going loose, and offered to give it their seal of approval if IBM would cooperate fully. IBM didn't want to be liable if Lucifer had a small flaw, so they agreed. The NSA then also joined the groups of people attacking Lucifer, and helped the IBM team avoid differential attacks (which they had already done, but NSA offered refinements). The only bad thing the NSA did was cut the key length. Lucifer was submitted, and became DES.
Now, the whole point of this is that it took a long time and many many manhours of very bright people attacking the cipher, and coming up with design principles to help avoid the attacks, because IBM DID NOT want to release a cipher without doing it's damndest to guaruntee it was secure. They invited outsiders from all over (including the NSA) to attack and comment on it. A lot of work was put into it initially.
If DES had an easy attack against it, it would have been found, the design principles would have been revised, and hopefully the entire class of attacks would be taken care of.
RSA was similar. R and S came up with ciphers, and tried to break them. When they thought they had something good, they'd hand it over to A, who would then break it (supposedly he broke the first 31 attempts without any trouble). This is the same cycle IBM did: a team designs it, submits to others who will attack it, they get feedback and refine it. After the original RSA was OK'ed by R S and A, they gave it to colleages to try and break. Who failed.
My point is that all successful ciphers have gone through extensive work. Many many ciphers developed in the course of coming up with good ones are scraped. Only a few are secure. The best ciphers have been analysed by many people for a long time before they even see the light of day.
CSS was not put through such a process. They developed it, and never submitted it to the glare of public scrutiny. It contains glaring design flaws, that even a small amount of competitive attacking would have found. But it was never submitted to such, and therefore deployed before it was proved secure. The PDF security model (which Dmitry broke) was also not given a public vetting before release. (BTW, Dmitry didn't break crypto, he broke the protocol. However, many of the encryption schemes used in eBooks are proprietary designs that haven't been put to public scrutiny, and are therefore likely weak) I haven't chewed through the details of the 802.11 break, but 802.11, while it has been submitted to public scrutiny, hasn't been there very long.
It isn't that the codes are bad, but that most codes developed are crap. If you want a good code, take a code, and try as hard as you can to break it. Ask your friends/hire independant consultants to break it. Then, release it to the public to break it. Only then can you have any confidence that it is secure. And at that, if a new code hasn't been around for a while, it's probably crap. Most codes are easily broken. Scrutiny breaks the easily broken ones, leaving the strong ones for wider use.
Well, the particular book in question (And Then There Were None) appears to have a copy published by Mass Market Paperback, so this particular copyright has expired.
Some of her other works, I expect, as she lived until the '80's. The death of the author doesn't terminate all of the copyrights, but (under current law at least) 70 years later. If it was published before Jan 1 1923 it is in the public domain no matter what. So if she published it after '23 it is still copyrighted.
By contrast, the telecom network is the opposite: a smart network with dumb terminals. The intelligence and thus control of the network is contained in the switching technology, allowing the operator to ensure and contract a given quality of service. This allowed the pre-breakup AT&T to promote their famous "Five 9s" performance, 99.999% reliability. The ability to control access and routing also allowed higher margins, and thus profitability, despite the high startup costs.
Umm, wasn't the entire idea behind a packet network is that it was more robust than a traditional centralized network? If you loose a node in a centralized network, everybody that goes through that node is screwed, as your topology closely resembles a minimum spanning tree. Anybody looking for an example of an unreliable minimum spanning tree should take a look at EFNet.
Even today, if there is a natural disaster somewhere, and everybody wants to call their family in $PLACE to see if they are alright, the phone service in $PLACE goes to pot.
A packet network (like the internet) however, will just start dumping packets. Everybody's comminications will EVENTUALLY (for TCP/IP at least) get through, although the throughput will suck rocks through a swizzle stick. The entire point of a packet network is building a reliable network out of unreliable parts. A centralized network is no more reliable than the parts that it is made of, though. Saying that ATT achieved 5 9's is a bunch of crap.
Specifically, a company has to use due dilligence in preventing it from becoming public knowledge. So, if Coca-Cola leaves copies of it's secret formula lying around, they can loose their trade secret protection.
In fact, if you look in the Nolo definition, they say:
Sensible precautions include, for example, marking documents containing trade secrets "Confidential," locking trade secret materials away after business hours, maintaining computer security and limiting access to secrets to people with a reasonable need to know.
Which indicates to me that by allowing its computers to become infected with SirCam a company has not taken the necessary sensible precautions, and is fair game.
Now, you could say that some of these employees are disclosing things that they have no right to disclose, and trade secret protection still exists. However, it is the company's duty to prevent the SirCam infection, not necessarily the individual employees. It is an interesting thing to consider: does the carelessness of the company in becoming infected count as failing to properly keep their secret? I'm sure if SirCam was used as a tool to dupe a specific company into releasing specific information it would count as industrial espionage. However, at this point SirCam is something that is just out there as a general threat, and it means that if you do not take adequate precautions against it your (possible secret) information will be made available to other people.
Now, if you accidently recieve something that is clearly marked as cinfidential, it probably is still protected. But if there is no such clear marking, or if the "confidential" file is spewed all over the place, regardless of marking, I'd think that the former owner of the trade secret is SOL.
VeriSign is claiming that their competitors are blatantly defrauding them, and that the evidence provided to VeriSign of the customers wanting to switch is falsified. Looks to me as if VeriSign is the one whose lying. Their analysis of the evidence (as presented in the letter) is bogus.
one provided copies of several e-mails described as having come from more than 20 different customers-all using exactly the same wording and type font; and another provided identical e-mails, all dated after the VeriSign Registrar's request, and claimed that they showed prior customer intent to transfer
Now, must ask VeriSign, how many ways are there to word a registrar switch? "Dear Verisign - we are dumping your ass for a better registrar?". No, they're all probably a standard business letter layout, with a body of:
Dear $ACCOUNTMANAGER
We are switching to using $REGSTRAR as our domain name registrar.
Thank you
$CUSTOMERNAME
There aren't that many ways to do it. In fact, if a large ISP was switching a lot of customers (read the main article), the wording should be the same. And as for same font, umm, wouldn't that be more dependant on the person printing them out? Last time I checked, email didn't embed the font (unless you use html, and not even always then), and that the font would be the same if they were printed by the same person. Nothing unusual at all in that. Hey, here's an open offer to VeriSign: 5 bucks if the font isn't Courier. My $5 is perfectly safe...
Now, the second set of emails being exactly identical is a bit erie, but as I said above, there are two good explinations: there are very few ways to politely word "go f*ck off verisign", and if a big ISP were switching customers they should be identical. As for the dates, well, if someone forwarded them, the email header would have the date of forwarding. And if they were printed, then they would all have the print date. Either way, it would be weird if the dates were before (not after, as stated) VeriSign's request, since that would mean the competing registrar anticipated VeriSign's request.
I doubt that Mr. Lynn (the President of ICANN) won't catch on to VeriSign's obvious attempt at fooling him. And I doubt that VeriSign will like the consequences.
The stuff they say about certain HP printers is true too. We have a HP LaserJet 4000N, and it's been going down all day. The secretary (who's since gone home) has been confused as all else as to why the printer keeps giving some strange error. I'd guess that all HP's that use the same internal network spooler will have the same problem.
The FSF registers most of their copyrights. That means that they can get punative damages if it is violated. While I'm sure the FSF would be happy to ignore past violations if you open up the code, simply stopping may not always be enough.
If you really really stretch things, you can file a patent and wait an eternity before it becomse public domain. The USPTO has no trouble collecting that late fee over and over and over again. I don't remember the details, but there is a patent involving machine vision that was filed in the 50's, but only was granted in the last 10-20 years. The original inventor is dead, but the foundation he created to handle his patents is trying to claim that his patents can cover bar-code scanners.
If somebody remembers the guy's name, it would be nice to put it up. The guy has a huge collection of patents, and has taken huge advantage of that particular hole in the patent system. That and that they allow unlimited modification of the wording of your patent so long as it is true to the original spirit of the filing (read: remotely close).
First, they aren't mucking with the TOC, but putting delibrate errors in the data, and mucking with the ECC
However, they are still selling CDs which aren't standards compliant. This leads to a rather interesting question: If you sell a "CD" that purposely doesn't conform to the standard, is it fraudulent to sell it as a CD? It could be possible to claim that as their CDs don't have the proper ECC, they are lacking a standard feature present in all other functional and non-damaged CD's, and the manufacturers are knowingly selling a defective product.
I doubt that they could be hit under fair-use laws, but if the packaging of the CDs claim that they are normal CDs, without mentioning the copy protection, they might be liable under consumer protection laws.
Apparently you're fairly new here. If you weren't, you'd know that it is next to impossible to get a refund for Windows. MS says it's the vendor's problem, but the vendors are prohibited from releasing what they were charged for Windows, and they therefore can't give a refund either.
What MS did wrong was imposing such rules on the hardware vendors. If they wanted to sell machines with Windows on them at all, they could only sell machines with Windows on them. Well, yes, they could get retail copies, but the price difference is so unreasonable that nobody could make a profit selling that way. MS effectively prohibited anybody from selling PC's without including a MS OS.
Price discrimination, which is what MS was practicing with their agreements, is illegal in many countries, and in the US, if you are a monopoly, it is very suspicious and indicative of possible monopolistic abuse (aka, also illegal).
As for buying parts and assembling them, that is not always a valid option. What percentage of the general population is hardware savvy enough to do that? Hell, what percentage of slashdot readers are using a wholly custom box? Hmmm? I doubt that even here on /. it is over 40%.
Why don't you grow an opinion of your own. Astroturf is pretty damn ugly.
By Joe Sixpack
Wurshington Past Staff Writer
To test loosy summarization techniques, we recruited a diverse panel of readers: two linux advocates, a gamer, a cheerleader, a MBA, and two MS windows users.
We had them read summarized versions of two articles: "MS beats Linux in Mindcraft Test" and "New Detonater 17 Drivers Released by nVidia".
The tests were conducted in a home environment with an ordinary browser. We focused most of our attention on JohnKatz and ZDNet, the two most fanatical formats, with Tom's Hardware and MSNBC, the unbiased and more journalistically responsible formats, given more limited tests.
Of the seven readers, two couldn't differentiate between JohnKatz and ZDNet. The other 5 agreed that JohnKatz was the least realistic, with Tom's Hardware better and MSNBC reading best of all.
"JohnKatz just started blathering in the Mindcraft story. There was a lot of cruft about freedom and how OSS rules, but the real content was cut out completely" said Duke Fraggem, a hard-core gamer. "Tom's Hardware, on the other hand, man, you could even read the friggin' frame rate in the benchmark's section"
Betty Bouncealot, a professional cheerleader, said "I thought it was funny that the MSNBC article cut that Demonitator thingy out completely, not even a headline. But at least it was the least confusing of the articles."
Both of our linux advocates felt that the ZDNet article totally destroyed the readability of the "Mindcruft" article. "It seemed made-up and artificial, like they didn't even review the facts at all," said Colonel Kernel Sanders, a RedHat staffer. "I couldn't even finish reading it, it was to painful" was all Joe "OSS" Bloggs had to say about it.
One thing that all of the readers agreed upon was that JohnKatz was the worst of the summerizing formats. Sanders said the nVidia article lost a lot of "sense." Bob and Clippy, the Windows users, blamed this on the way JohnKatz shaves off the sanity and content from articles. John Doe, who holds an MBA from Harvard, noted that the sanity of a JohnKatz article abruptly terminated, compared to ZDNet's gradual fadeout.
On a tiny PDA screen -- the kinds of environments where many articles are read -- the loss of information would probably go unnoticed.
But Bloggs worried about how the loss of subtle information meant less journalistic integrity overall. "Those little details give you a lot of information about what really happened."
(C) 31337 The Wurshinton Past Company