Slashdot Mirror

Not as detailed or comprehensive?
have you seen CiteSeer?

This seems like a fine time to mention Slow Sort, which makes bubble sort look downright efficient and clever. From this paper (PDF).

(The paper is fun if you know computer science, the c2.com link is in "normal English". Try the paper if you think you'd enjoy it; it has a dry wit and pursues its task of sorting as slowly as possible with great gusto.)

This seems like a fine time to mention Slow Sort, which makes bubble sort look downright efficient and clever. From this paper (PDF).

(The paper is fun if you know computer science, the c2.com link is in "normal English". Try the paper if you think you'd enjoy it; it has a dry wit and pursues its task of sorting as slowly as possible with great gusto.)

I'm sorry I can't address your question for good remote filesystems in the face of an unreliable network. My network has been relatively reliable and that's been a decreasing concern. Perhaps network reliability will be less of a concern for you, too, in future.

Lately, what I've been looking for is a remote filesystem that provides performance, security, flexibility, the latter in reference to being able to log into someone else's desktop machine and easily get my home directory mounted, whether from a big server up 24x7, or from my desktop.

Some have dabbled with DCE/DFS, but I've heard that's slowly dieing, ponderous to set up, performance suffers.

SFS looks intriguing, but I haven't heard pro or con about its performance. It appears to be secure and flexible.

NFS is an old friend and, yes, if the network or the server dies, a lot of local sessions will hang interminably 'NFS server not responding'. But, this doesn't happen as much as it did 5 years ago.

Right now we're running NFS v3, but the new NFSv4 looks like it has a better security model.

Finally (and you shouldn't even think about this if network reliability is an issue), simple block service like iSCSI looks promising as a way of interchangeably moving around from desktop to desktop and getting your same home directory no matter where you are. More, you could conceivably even get your own flavor of OS booting, be it Red Hat 9, Win2K, XP, Gentoo, etc. Don't know about its security; it's heavily dependent on a reliable, high-performance network, but looks like a good way to get the most storage for your dollar (NAS instead of SAN).

Sure: WORM (write-once-read-many) file systems have been around much longer. See here for a paper from 1991. And write-once optical drives were available commercially already at least in the late 1980's.

Well about 10 years ago, just down the hall from Jim Gettys' office, they were working on this. It was called audiofile, and basically did for audio what X did for graphics.

I had a "DECaudio" box on my DECstation-5000.. and had audiofile running. It was pretty cool.

Official Site

Short Blurb from Time Magazine


Descriptive Article (with pictures)

Details Regarding its Supercomputer Status

but computer-type algorithms choke on this stuff.

Note also however that this is one of the areas in NLP that is recieved a huge amounts of attention over the past two decades - people were producing papers on the recognition of indirect speech acts back in the 80's...

Explanation-Based Learning of Indirect Speech Act Interpretation Rules

Now, Speech act theory and its applications is not directly my field of expertese, so maybe someone who does research in that area could let us know what the state of that art achieves these days...

~D

MS Press released this format multiple times, notably in this book, Advanced MS DOS. Another volume is the tome referenced here, The MSDOS Encyclopedia. These volumes detail the internal file structures and layout of FAT (without releasing the implementation.) Publishing the specification allows others to use the same data layout when creating an implementation for other operating systems or platforms. There is a violation only if the Microsoft implementation (closed source code) is used directly.

The book NT File System Internals was a lot thinner and perhaps why the clean room implementation of NTFS has proved more difficult (and NTFS is a moving target.)

This actually was reported yesterday in Japan (here), but I could not find any article in English until now.

Courtesy of the Rejected Post Machine:

NTT DoCoMo: Linux-based 3G Mobile Phones in 2004

* 2003-12-02 11:59:33 NTT DoCoMo: Linux-based 3G Mobile Phones in 2004 (articles,pilot)(rejected)

Reuters cites a confidential source as saying that NTT DoCoMo will offer its customers Linux-based 3G mobile phones in 2004. DoCoMo has apparently sent specifications to handset manufacturers and DoCoMo supplier NEC has said that it will offer Linux-based phones by 2004. If true, the report would indicate a shift from the dominant TRON and Symbian-based handsets.

This was also submitted yesterday morning, but I guess Reuters wasn't considered authoritative enough until the English version of the Japanese story. =)

The original source for the "three-click rule" is Catledge and Pitkow's 1995 paper, Characterizing Browsing Strategies in the World Wide Web.; see an online copy.

To quote: Directions for Design Since users accessed on average 10 pages per server, this would indicate that "must see" information must be accessible within two to three jumps of the initial home page (two/three navigations in, two/three out, performed three/two times). However, [...]

This paper is one of the first, if not the very first, actual user survey studies on the Web. It is very limited in scope, of course, and there may be good arguments to question its validity, but if you're going to do that, at least quote the rule correctly, mention its origins, and mention the fact that it was co-written by James Pitkow, who has continuing this line of research until the present day.

Better check webster.com - first, it's free, second it's a pretty reliable source. and it says:

The plural criteria has been used as a singular for nearly half a century

You may want to looak at google how many pretty "oficial" documents use a single criteria.

Finally, check "CiteSeer" (very "academic" computer-science article repository) for a single criteria.

I understand you attempt to keep English clean, but there is not such thing as a standard English. It's a very alive social phenomenon, varying over the time and across social groups.

And your attempt is especially loughable at /. :)

I'm not sure we know what they do today, but the original PageRank was published some time ago, and there's been lots of follow-on work. Go to citeseer when it comes back up, and query pagerank.

My opinion? Formal proofs are a holy grail, unreachable, and the reality of software is that small, testable, interworking pieces is the only way to assure "correctness". That, and code generation, the wizard's wand of software.

For an alternative view, I recommend this this article.

You can get info about Page Rank in this paper.

As others pointed out, this article referers to citations made in research papers to online sources which become obsolete over time. Unless your 4 year old is regularly publishing work referenced in academic journals, this probably isn't an issue.

Incidentally, try Citeseer for an example of a stable online repository of research papers.

Actually I know that Clint Whaley is still working on ATLAS and related topics, since he shares the same advisor as me at Florida State University.

Perhaps more interesting (and relevant to the topic at hand) is some other research involving compiler optimization and genetic algorithms. (Please note that I am part of a group currently working in this area.) There have been several papers on the topic already from Rice University as well as from our group at FSU. These results have more to do with tuning the order of optimization phases in a compiler using a genetic algorithm, since certain phases may enable or inhibit other phases. Thus the big difference between these studies and the gcc study is the lack of a fixed optimization phase sequence, so certain phases may be skipped, repeated or just rearranged to provide greater benefit.

The "folks" you refer to is Professor Adrian Thompson of the University of Sussex. A paper describing his interesting experiment can be found here. It was actually a flawed FPGA chip he was programming.

Another example of this tendency of Genetic Algorithms to make use of helpful "flaws" in their environments can be found in the works of Karl Sims. A round-off error in his physics model resulted in some weird locomotion by a branch of virtual creatures.

You will find details of both examples in this entry on my Wetware blog.

see this and related documents from here.

see this and related documents from here.

I have a paper for your list. The paper topic is fault tolerant computer systems and is referenced heavily in Aerospace/NASA/Military reseach...

The Byzantine Generals Problem (1982) Leslie Lamport, Robert Shostak, Marshall Pease Advances in Ultra-Dependable Distributed Systems, N. Suri, C. J. Walter, and M. M. Hugue (Eds.), IEEE Computer Society Press

It basically points out that in fault tolerant systems, you need a minimum of 3 sources to determine if one source is bad.

I have a paper for your list. The paper topic is fault tolerant computer systems and is referenced heavily in Aerospace/NASA/Military reseach...

The Byzantine Generals Problem (1982) Leslie Lamport, Robert Shostak, Marshall Pease Advances in Ultra-Dependable Distributed Systems, N. Suri, C. J. Walter, and M. M. Hugue (Eds.), IEEE Computer Society Press

It basically points out that in fault tolerant systems, you need a minimum of 3 sources to determine if one source is bad.

Nine Men's Morris has been solved by Ralph Gasser in 1996 (Draw).

So has Qubic (4x4x4 Tic-Tac-Toe) by Patashnik O in 1980. (First Player Win)

Connect Four by James Allen in September 1998. (First Player Win)

Let's see John W. Romein and Henri E. Bal from that wonderful games research group in U of Alberta solved Awari in 2002. (Draw)

Read Victor Allis' PhD thesis for a good overview on finding game theoretic results of games. He invented the proof-number search technique that he used to (re)solve Qubic and Connect-Four. http://www.cs.vu.nl/~victor/thesis.html


Nine Men's Morris is not researched actively anymore, but Ralph Gasser's paper is often cited in any paper that deals with artificial intelligence in games.

Of course, even though the game might already be solved, that does not mean that it is not fun to play...

This is the paper by Diffie and Hellman that originated public-key cryptography. This paper explained for the first time (in an unclassified place) how two parties could communicate privately over an open channel without previously agreeing on a secret key. Every time your browser says, "Setting up a secure connection..." when you order from Amazon or check your bank account, you're witnessing the impact of this work.

Since nobody who seems to have actually read any computer science papers has posted, here are two that immediately come to my mind.

Vannevar Bush. As We May Think. Atlantic Monthly, July, 1945.

This paper put forth the very first ideas about how people can mechanically search for information. While we don't have desks with levers on them, we do have Google. :)

Tim Berners Lee. Information Management: A Proposal. 1989.

This paper is where Tim Berners Lee proposes what we now know as the world wide web. It's an interesting read if you'd like to see what the original intent of the web was so that you can compare it to what we have today.

A place to look for good old computer science papers is in older issues of Communications of the ACM. There are lots of articles in plain English that you may find of interest. If you are a university student, your school may have a subscription to the ACM Digital Library. If they do, you can read all the issues back to 1958.

Also, you can find a lot of interesting CS publications at Citeseer. They have a page with the top 200 most accessed papers of all times. When I skimmed through it, I saw quite a few titles that may be of interest.

Since nobody who seems to have actually read any computer science papers has posted, here are two that immediately come to my mind.

Vannevar Bush. As We May Think. Atlantic Monthly, July, 1945.

This paper put forth the very first ideas about how people can mechanically search for information. While we don't have desks with levers on them, we do have Google. :)

Tim Berners Lee. Information Management: A Proposal. 1989.

This paper is where Tim Berners Lee proposes what we now know as the world wide web. It's an interesting read if you'd like to see what the original intent of the web was so that you can compare it to what we have today.

A place to look for good old computer science papers is in older issues of Communications of the ACM. There are lots of articles in plain English that you may find of interest. If you are a university student, your school may have a subscription to the ACM Digital Library. If they do, you can read all the issues back to 1958.

Also, you can find a lot of interesting CS publications at Citeseer. They have a page with the top 200 most accessed papers of all times. When I skimmed through it, I saw quite a few titles that may be of interest.

As a PhD student, I often have to look for papers in the computer science field ; and very often, CiteSeer yields better results - or, rather, different results, but with a very good cross-referencing system. You can directly jump to the other papers cited by the paper you're reading, and you can see which papers did cite it, too.

The URL :
http://citeseer.nj.nec.com/cs

That said, I often find very interesting ideas in scientific papers, but sometimes things can't be implemented with current technology (I'm still talking about computer science domain, since that's what I know), or sometimes, the good idea in the paper is obsoleted a few years later.

For instance, I remember a scheduling algorithm to read disk blocks in a Video-On-Demand server : it was maybe very clever when it was written, when they had to feed 155 Mbps with a computer having 16 MB of RAM, but today, you have maybe 10 times more throughput, but 100 times more RAM - so you can use simpler, memory-hungry, buffering methods.

The problem is, that it's difficult (IMHO) to say "OK, this paper is theoretically interesting, but we can't implement this today, BUT we will probably be able to do it in a few (dozen) years", because you don't know what will and won't evolve (in my previous example, it was easy to predict that network bandwidth and memory size would increase, but it was maybe harder to guess that MPEG4 and DivX would allow the bitrate of a video stream to stay low...)

• Van Jacobson and Michael J. Karels Congestion Avoidance and Control. SIGCOMM, 1988
• J.H. Saltzer, D.P. Reed and D.D. Clark, End-to-end Arguments in System Design, ACM Transactions on Computer Systems, Nov 1984, p. 277-288
• Jeffrey C. Mogul The Case for Persistent-Connection HTTP. In Proceedings of ACM Sigcomm '95, pp. 299-313, Cambridge, MA, August 1995

• Van Jacobson and Michael J. Karels Congestion Avoidance and Control. SIGCOMM, 1988
• J.H. Saltzer, D.P. Reed and D.D. Clark, End-to-end Arguments in System Design, ACM Transactions on Computer Systems, Nov 1984, p. 277-288
• Jeffrey C. Mogul The Case for Persistent-Connection HTTP. In Proceedings of ACM Sigcomm '95, pp. 299-313, Cambridge, MA, August 1995

Does anyone know of a website where you can get access to comp sci and comp eng papers and stuff?

Try looking at arxiv.org and CiteSeer.

Citeseer was cited in the blurb, but a really nice service that they provide is the Computer Science Directory. There you can look for papers sorted by domain, and ranked by several criteria like "authority". The top papers are usually a good read if you are interested in a particular domain.

Actually, this whole thing is probably blown out of proportion. The patent summary looks a lot like a paper by Robert J. Hall. I expect that ATT has a policy of patenting everything any of their researchers works on, regardless of what it is. The paper itself is mainly mathematics with the spam theme thrown in to make it interesting.

Ssh may be a better idea than netcat.

I suggest you go read this paper about the economic viability of a Matian Colony. It was writtent by Robert Zubrin, of Lockheed Martin Astronautics.

Many people thought that there wasn't a buck to be made from the "worthless wilderness" in newly-discovered America or Australia back then.

By the way, I've found a link to the paper I mention above. It's the paper by Charles Bennett, Francois Bessette, Gilles Brassard, Louis Salvail, and John Smolin, "Experimental Quantum Cryptography" (Citeseer link).

I imagine they're using the protocol, or a close variation thereof, of the one described by Charles H. Bennett, Gilles Brassard, Louis Salvail, and John Smolin in their paper "Experimental Quantum Cryptography" (Citeseer link). They use the quantum channel to allow Alice and Bob to negotiate a random key known only to them, which cannot be eavesdropped upon, and also allows them to discover any eavesdropper attempting to obtain their key. You can't use a quantum channel to transmit real information, but you can use it to negotiate a perfectly random key between two communicants without anyone but the two parties knowing it. In other words, the quantum cryptographic protocols are just like Diffie-Hellman and other key exchange protocols we all know well, only they provide a physical proof that according to the laws of physics as we understand it today, eavesdropping is impossible.

but I am not aware of any such solution.

xmove

The relocatability of X11 applications has been academically studied for a long time, and implementations like xmove are easy to download. But their shortcomings are numerous, as you'll quickly notice by giving it a try. The existence of the pseudo-server is the most obvious shortcoming, as it means there will be a performance hit for the entire life of the application, even though you'll only rarely want to move an X11 app from one display to another.

If X11 supported re-heading deeper in the protocol, then not only would transferring operation be cheaper, but we also might be able to restart XFree86 on a Linux system without killing all the applications connected to it.

You'll be happy to know that the MIT media lab is hard at work on your idea. Here are some related technologies: an emotional communication device and a a medium for intimate conversation.

I actually remember a talk at CHI about a vibrating vest or something like that for sending and receiving hugs. I also remember discussing with someone how they must have been discretely funded by the pr0n industry.

Try
"Lotka Distribution" (38 occurrences)
"Lotka's Law" (440 occurrences)
"Zipf Distribution" (2320 occurrences)
"Power Law" (282,000 occurences)

The Zipf name is probably more familiar than Lotka but the last term is most commonly used (well, doh). Quoting from a citation of Lotka's paper...

"...Zipf is often credited with noting that city sizes appear to match a power law, although this idea can be traced back further to 1913 and Auerbach Lotka (circa 1926) found in examining the number of articles produced by chemists that the distribution followed a power law."

A non-disclosure is not a non-compete. A non-disclosure can only prohibit disclosure of confidential information. A non-disclosure should clearly define information that is confidential and actions that make it disclosable. Notably, if you learn the same information through a public channel (one not covered by NDA) you are allowed disclose it.

I have a spooky 10-year NDA with IBM regarding PowerPC features and test methods that doesn't expire until early next year. I'd estimate 99+% of what I learned on the project is now public information so I no longer fear talking to people about the instruction set (parts of which were under NDA at the time I did the project) and most of the then-bleeding-edge test methods have been presented at numerous contracts. For a few years, I actually ran occasional searches to let me know when IBM disclosed things so I knew I could talk about them. Now I can pretty freely talk about random test vector generation.

My very favorite part of the IBM thing was they had lawyers review and blackout every document that hit my desk; apparently they thought my NDA wasn't strong enough. I received a manual on the test generation program that had all of the numerical constants in the examples blacked out. As an exercise, I reverse engineered them all from the descriptions.

I have only had a few NDAs that actually prohibited mentioning the clients name. I charge a lot for that privilege.

The PLoS is really important. More important than "open source", and it should be on the front page of slashdot.

Listen: Right now, basically everything published in a journal in the last 50 years is *owned* not by scientists but by publishers. You might not realize this if you never published, but journals and conferences make you *assign the copyright* for your paper to the publishing company. Not license it to them for publication (this would be reasonable), but *give* them the copyright and lose your own rights to publish and distribute the work. Here's a sample agreement from the IEEE .

This is seriously fucked up. It means that, if the publishers wanted, they could close up shop and never let anybody see the archive of scientific papers again. It means they can sue you if you publish your own paper on your web page, or make copies of it for a class you teach!

Computer scientists, being handy with the web, typically publish their papers and then put them up on their websites, playing "civil disobedience." (Some journals have even caved to this, and part of the copyright assignment you actually get licensed to put the paper on your web page.) That means there's already a sort of PLOS for computer science: an index of Computer Scientists' web pages and publications at citeseer .

The culture in other sciences, like biology, is really different. These guys write, sign the form, and then pay for a few paper copies of the article that they can give out if requested.

The way it's happening in CS is one way to free science. It seems to be working. But for those who don't actively maintain web pages and don't have a culture where the web is the place to go to look for papers, the PLoS seems like a good way to make this happen. I really, really hope it succeeds.

Well, it doesn't seem people are really searching for a solution, or they'd be working to implement Capability Systems to replace the crappy ACL systems we have today, that provably and significantly reduce many of today's security problems.

I'll also say that the first difficulty in your analysis comes in by stating how much energy it takes to flip a bit.

It's called the Landauer Bound. It's the thermodynamic minimum required to erase one bit of information (or, for any von Neumann computer, the energy required to flip, set or erase a bit). If you can go below this level, then you've just broken the Second Law of Thermodynamics. You suspect that my energy estimate will go down over time? I suspect the Second Law will prevail.

All right, so you have a huge amount of numbers storable on a relatively small amount of space, from what I'm gathering. You know, as a layman. And it goes on to say that operations can be perfomed simultaneously on all these states.

Yes. Now sit down and do the math. Figure out how many qubits you need to solve a problem of that magnitude. Figure out the minimum energy required for those qubits. Figure out whether or not the decoherence problem can be resolved for that many qubits (this one is completely unknown). And don't forget to prove that the chess space lends itself to a quantum solution; one of the things we've formally proven about quantum computing is that there are many, many problems which cannot be efficiently solved on quantum hardware.

All of these are mathematical and/or physical limitations, not technological or engineering limitations.

You say that, no matter what, there can be no possible situation where we could work out the entire tree.

Not until computers are made of something other than matter and occupy something other than space and run on something other than energy. Every model we currently have says it's not going to happen. If you want to say "well, it will happen!", then you need to first present a different model.

It's like saying that I'm "anti-scientific-revolutions" because I believe in the Second Law of Thermodynamics. I'm not anti-revolution. I'm anti-idiocy. Ignoring the Second Law just because "well, someday we'll figure out how to get around it" is a fool's errand.

For now, for the forseeable future, and very possibly for all time, the entire chess space will be an intractable problem. This is not anti-science. This is not prejudice. This is postjudice; taking a look at the corpus of knowledge and making decisions about what avenues of research are likely to bear fruit and which are likely to be barren.

If you want to sit there and say "hey, you're a stick-in-the-mud who doesn't believe in scientific progress," go right ahead. As for me, I'm going to take a look down one road and say "as near as I can tell, that's a dead end" and look down another road and say "hey, I don't know what's at the end there, but it looks pretty cool."

Carl Sagan, himself a great advocate of both skepticism and open-mindedness, once came up with a remark for people like you. "They laughed at Fulton. They laughed at the Wright brothers. They laughed at Einstein. But they also laughed at Bozo the Clown."

In particular, the failure of the x86 architecture to implement the Popek-Goldberg requirements. VMWare and Plex86 have to do a lot of work to paper over the cracks. Xen uses a modified guest operating system to get around this.

Popek and Goldberg worked this out in 1974. It's taken Intel a little while to notice.

Would anyone in the audience be willing to start a GNU version of a virtual machine monitor (VMM)? Writing a VMM only takes tens of thousands of lines of code as opposed to tens of millions of lines for an operating system. The project could be done within a year. Take a cue from the work done on Disco, the VMM developed at Stanford University.

Then, we in the open-source community could feedback to Intel what we want in terms of support for VMM. We could even get help from our uncle, IBM. IBM invented VMs and VMMs back in the 1960s. Unlike Sun Microsystems, IBM has been a strong supporter of the open-source movement and Linux and would surely be willing to help in building a GNU version of VMM.

This is a golden opportunity for the open-source community to impact the future direction of processor development. Is anyone up to the challenge? Would anyone like to accrue the same fame that Linus Torvalds has?

... from the desk of the reporter

Freenet is just a research project

It has quite a few citations. I doubt Freenet has just a pure "for research" motivation, but other computer scientists believe it has technical merit.

Sun's mistakes are well documented, but the biggest one is believing that what made them successful in the past would make them successful in the future."

If that is the biggest mistake, then the second biggest mistake is the processor-design team. According to "Sun's processor plans slip a notch", the schedule of the UltraSPARC processors has slipped again. The processor-design team has 2 characteristics: chronically behind schedule and chronically behind the performance curve. Right now, the UltraSPARC III is being crushed, performance-wise, by the Power4+ and the SPARC64-V, according to SPEC".

Yet, McNealy stubbornly clings to the UltraSPARC III. If he knew how to run Sun, he would immediately scrap the UltraSPARC III and successors and tell his server team to use the SPARC64-V. He could come out with an E15K that just barely competes against the p690 in about 2 months. The SPARC64-V is instruction-set compatiable with the UltraSPARC III and vastly outperforms it, and modifying the E15K and other Sun servers to use the SPARC64-V is a simple matter.

Time is extremely critical. Sun itself claims that it will lose about 10 cents per share for the first quarter. 10 cents per share means a loss of about $300 million. Extrapolating to the full fiscal year means a loss of about $1.2 billion. In order to compensate for that loss, Sun will need to fire about 6000 employees.

The only conceivable reason that McNealy refuses to abandon the UltraSPARC III is that he fervently supports a workforce weighted in favor of H-1B workers. Sun has many H-1B employees, and they built the UltraSPARC III. By contrast, Fujitsu uses native workers (i.e. Japanese citizens), and they built the SPARC64-V. (IBM also prefers American citizens or permanent residents, and they built the Power4).

McNealy better put aside his ego and go with the SPARC64-V. It is the fastest, safest route to boosting Sun's fortunes. In the future, he should consider giving preference to American workers, not H-1B workers. There is no evidence to suggest that H-1B workers are better than American ones; indeed, H-1B workers might actually be destroying Sun as evidenced by the horribly designed UltraSPARC III.

Most importantly, the SPARC64-V will buy time for McNealy. Maybe 1 year or 2 years of breathing room. Then, he can make the hard decision of spinning off the processor-development group and transforming Sun into a niche player that focuses on two areas: software applications and highend-servers that use Fujitsu processors (or, gasp, IBM processors) designed by native talent. Other possibilities have been thoughtfully outlined by Merrill Lynch, the premier American investment company.

... from the desk of the reporter

Look at the publication histogram at the bottom of this ResearchIndex citation query for 'chaos'

Kinda like Tripwire , Symantec Anti-Virus, RedHat Enterprise Linux's dymanic relocatable address to fight worms, OpenBSD StackGhost and ZoneAlarm Firewall all rolled in one.

Once implemented, we should see a dramatic change in the network security world; less IDS/IPS/IDPS business model.

The last frontier would then be the social hacking engineering prevention.

Mark Mah Words

These guys need to read the LRVM paper - a poor attempt by the OS community: PDF (by Satya and Co. at CMU). Of course, as a database researcher I don't think much of Prevlayer .. mainly because the database community went through this in 1990. Great paper to read is Carey and Dewitt's Of Objects and Databases: A decade of turmoil - it won the "Test of Time" award in VLDB 1996.