Slashdot Mirror
A Simple Grid Computing Synchronization Solution
atari_kid writes "NewScientist.com is running a article about a simple solution to the synchronization problems involved in distributed computing. Gyorgy Korniss and his colleagues at the Rensselaer Polytechnic Institute proposed that each computer in a grid synchronize by occasionally checking with a randomly chosen computer in the network instead of centralizing the grid by having a global supervisor."
NewScientist also carried an article how randomly moving search agents can speed up P2P technologies, the current idea of : "Each individual computer makes occasional checks with randomly-chosen others, to ensure it is properly synchronised." is again very similar
The gist is, use a mathematical ploy to ensure that the ammount by which the system can degrade over time is compoensated by the simplest system possible.
This idea could perhaps be taken further...
If I understand this correctly, wouldn't it contain the potential for the computers to become very desynchronized. What I mean is that, since each computer may become slightly off from all the others on its own, if each computer synchronizes to another random computer in the group, couldn't some of the computers become massively off?
how is that modded up, yet a previous post identifying that this research of randomising and disassociating nodes of a P2P system is still a 0 modded post? /. who do you want to mod today?
1: You dont understand it correctly
/.
2: 'massively off' ?
3: Oh you know everything don't you
Every random synch would be a degree of hops from the master node, THE KEY WORD is SIMPLE, it isn't bloody rocket science, and you don't even get it.
By randomly updating, the net effect is a smooth, disassociated update which uses a temporal variable to maintain a degree of acceptable degredation within the system to ensure that all nodes have enough updates.
TADA BLUDDY DA.
Fuck
Hey buddy, you got any change?
I bet you can slice time really thin with the ammount you procrastinate.
Or I bet your l33t 'knowledge' of noded based systems and dist. computing stems from your l33t pr0n finding abilities on K4z4a
Who knows if the other computer is correct?
The real answer is a smaller scale super computer controllig the distributed computing.
From the original New Scientist article...
Each individual computer makes occasional checks with randomly-chosen others, to ensure it is properly synchronised.
"This means each individual processor only has to communicate with a finite number of others," says Korniss.
To me this would imply processors being 'grouped' with different groups checking with one another randomly. e.g. if you have 2 groups of 2 processors (to keep the example simple) group A gets it's timings by checking with a random processor in group B and vice versa. This way a whole group cannot go out of sync because it's timings are determined by a different group.
Of course if I'm talking crap I'm absolutely certain someone will tell me.
Who knows if the 'small scale super computer' is correct?
/. today
Hmmm? hmmmm? And what would it do actually? hmm?
Oh perhaps the guys who modded you up understodd it, adn could tell me, since they thought it was an honourable mention.
Procrastination, and modification, who do you want to
The whole fucking point of the article is how a simple fucking system statistically floats every node about a degradation factor, thus giving the system enough stability.
But if your system is so good, please post a fucking URL to it bitch.
As I read it, we cannot reply on such system that may break down under a DDoS attack. For global itterative distributed systems, the key fundemantal chaining laws indicate that unless the synchronisation is secure, then the whole system state is unreadable.
Read Thomas Methodsons paper on distributed backends he developed similar to SETI systems, which run transient security functions on all nodes. These systems require extremely high system stability to function, and such systems would not cater for them convincingly.
Definately a centralised super computer setup, which could predictively monitor the system remotely. I have seen such solutions in papers, nothing you can look into however.
I suppose on difference between random-gridding and P2P is that all machines in the grid would know about all others - they just select random peers to sync with. In P2P a major problem is simply *finding* the other hosts.
:-)
Also in a grid the machines are presumably more reliable - they'll stay up for a much longer time than typical P2P hosts.
So I think this is a pretty cool - and novel - idea.
Since it might help grids scale better and many grids are Linux is another step in the world domination campaign
a greedy algorithm. at every iteration, do the best that you can and hope for the best. even if the solution/end-state is suboptimal, the huge resources needed for central coordination aren't needed.
g reedy/
"Greedy algorithms work in phases. In each phase, a decision is made that appears to be good, without regard for future consequences. Generally, this means that some local optimum is chosen. This 'take what you can get now' strategy is the source of the name for this class of algorithms. When the algorithm terminates, we hope that the local optimum is equal to the global optimum. If this is the case, then the algorithm is correct; otherwise, the algorithm has produced a suboptimal solution. If the best answer is not required, then simple greedy algorithms are sometimes used to generate approximate answers, rather than using the more complicated algorithms generally required to generate an exact answer."
http://www.cs.man.ac.uk/~graham/cs2022/
smd4985
Gridster, Gridtella and Gridzaa...
Starcraft RPG? only at
Online Starcraft RPG? At
Dietary fiber is like asynchronous IO-- Non-blocking!
And it all comes down to, the great idea of the international mesh of networked computers. The same philosophy that says tree stractures are a bottleneck to a stable network. And indeed are. A network that feeds from its members, not from the "great master-servers" can serve well on stability and performance. In fact, its stability is guaranteed in a way that is impossible to cut off the net unless the whole neibhorhood gets cut off.
Lets keep this ideas since they give something new not only to technology but the whole pfilosophy the western civilization is based on.
We are used to masters and slaves, what about all equal?
All responsible.
All powerfull.
I really hope not, because I live in Troy, and my dad works at RPI.
I'd actually heard they were going to be attending Rocehster Institute of Technology, anyway, which is where my boyfriend will most likely be going next year.
But hey, this is the internet, and random rumours abound. They could be not going at all, or going somewhere entirely different, and chances are, there'd be some rumour that they were going to just about any large university you care to think of.
Why is this news?
Distributed systems that do not rely on a centralised authority, be it for synchronising or resource distribution, are by far not a new thing. To name a random example (and you can find a dozen others with five minutes of Googling), the Prospero Resource Manager was a USC project started in the early 90s that relied on distributed authorities with no centralised command centre.
Furthermore, if the computers are self-controlling and not guarded by anything besides their internal mechanisms that rely on the checks on other computers, the potential danger lies in a computer in the grid having a seriously fscked-up internal state. In other words, can a malfunctioning computer be trusted to monitor itself correctly? I think not.
ok, look at your sources next time...
the article to which you refer "Olsen twins to attend Rensselaer" was a fake CNN site created by a script.
this script was hosted by spo0fed.com
it is now down (due to legal reasons) so i cannot show you, but it had a page to inptu all of your fake details and it would slap it into a copy of the CNN.com news page.
among other things, it said that they got 1600s on SATs and were interested in nanotech
if you actually looked at teh URL of the post it wasnt from CNN.com, but from someone's personal server...
See that reference at the bottom of the New Scientist article: "Journal reference: Science (vol 299, p 677)"?
Science Magazine is where to go for the actual results as explained by the people who did the research (as opposed to results as filtered through the mind of a journalist on a deadline, without the time to really understand the research, and with a desire to make the research more "interesting" and more "accessible" to his readers, regardless of the impact that may have on accuracy).
For those who have access to Science (your school may have a site subscription?) go here. For everyone else, the abstract is here courtesy of the National Institutes of Health.
I'll come back and post the full text of the article later.
-A.C.
Wouldn't this mean that all computers would have to be connected to the internet at all times to be part of the group? This might not be a problem for those with broad-band, but what about those that still use dial-up?
The extent to which communication is a bottleneck in parallel processing depends strongly on the problem at hand and the algorithm used to tackle it. Some problems are amenable to batch processing (e.g. Seti@home), others require some level of boundary-synchonisation (simple fluid codes), others require synchronisation across all nodes (e.g. more complex plasma simulations)
For batch processing tasks, there isn't an issue. For the other's the loose synchronisation may be acceptable depending on the knock-on effect. Loosening the synchronisation obviously decreases the network and infrastructural burden on the job allowing the algorithm to scale better, but the effect of this has to be carefully studied.
This is important to the application developer, but is not particularly relevent to grids per-say. Grid activity, at the moment, is mainly towards developing code at a slightly lower level than application-dependant communication. It is already building up an infrastructure in which jobs can run which tries to remove any dependancy on a central machine. This is because having a central server is a design that doesn't scale well (and also introduces a single point-of-failure). The Globus toolkit provides a basic distributed environment for batch parallel processing, including a PKI-based Grid security system: GSI.
On top of this, several projects are developing extra functionality. For example, the DataGrid project is adding may component, such as automatic target selection, fabrication management (site management, fault tolerance, ...), data management (replica selection, management and optimisation, grid-based RDBMS), network monitoring infrastructure and so on.
The basic model is currently batch-processing, but this will be extended soon to include sub-jobs (both in parallel and with a dependency tree) and an abstract information communication system which could be used for intra-job communication (R-GMA).
The applications will need to be coded carefully to fully exploit the grid, and reducing network overhead is an important part of this, but The Grid isn't quite at that stage, yet. But we're close to having the software needed for people to just submit jobs to the grid, without caring who provides the computing resource, or the geographical location they'll run.
| What, you were expecting
-O_O- +---- something witty?
Based on the (limited) details available, I'd say it sounds like they've just reinvented NTP -- except they've done it poorly, and without any security.
Tarsnap: Online backups for the truly paranoid
In the early 80's I heard a talk at IBM's Almaden
Research facility by a couple of the people involved in the ethernet development. They we synchronizing Xerox's phone/address list throughout the world by random contact and update. While they are certainly people with a hammer (random control) hitting anything looking vaugely like a nail, the experiment was a great success. They had a strong mathematical analysis developed in the medical community: communicable disease propogation. The system was far more reliable and lower cost (in communications) than any attempt to track the connections and run data propogation that "knows" an even slightly out-of-date view of available network connections.
If you think random cannot work in practice, don't use ethernet. For that matter, don't use semiconductor technology at all.
It is the same general idea, using decentralized decision making to improve efficiency in a distributed system.
Google highlightedhttp://openmosix.sourceforge.net
Of course, the idea is implemented quite differently in the two systems.
-Dave
...there is a leader. People clapping in unison only do so in the presence of a rythmic audio source, namely music.
This is the equivalent of a central timing server. When people start to go by their neighbours (ie people looking around with excited looks on their faces ["aren't we cool, clapping to this music!"]) and stop listening to the source of music, one half of the auditorium gets waaay off beat.
My apologies if you were referring to people beginning to clap after a performance, because you have a point there.
My $0.02 CDNThis is similar to the classic example used in physics classes of fireflys. Each makes a small movement to synchronise with some that are close. (in terms of flashing rythm). The result is a swarm that flashes in synchrony. It is normally used to illustrate concepts around forced oscillators - the key is to give the proper weighting to the change made to bring each unit into time with the local area.
The New Scientist summary is lame. Pick up a copy of Science and read the actual article if you can. It says, "Here, we show a way to construct fully scalable parallel simulations for systems with asynchronous dynamics and short-range interactions." This method, while interesting, does not generalize to a wide range of applications. For example, you could not apply this approach to molecular dynamics simulations, which involve primarily long-range interactions between atoms. Still, the authors of this article are clearly pretty clever.
I remember reading an article in DDJ about this, back in 1990 or so.
They called it "flooding protocol" and it's old technology. Call your neighbors and simply issue
IHAVE and IWANT commands back & forth.
They were doing stuff like that back in BBS days over modem when long distance calls were expensive.
It is good to see technology come full circle.
``Suppressing Roughness of Virtual Times in Parallel Discrete-Event Simulations'' G. Korniss, M.A. Novotny, H. Guclu, Z. Toroczkai, and P.A. Rikvold, Science 299, 677 (2003).
Now, let's ask why that is such a good contribution. In discrete event simulation, the system consists of a set of entities, each entity has a discrete state, but can undergo state changes at an arbitrary time (so states update asynchronously, unlike in time step driven models). In PDES, the entities are mapped to logical processors (LPs), and communicate via message passing using time stamped messages. It can be shown that the fidelity of the simulation is preserved if each LP processes its messages in ascending time stamp order, this is called the local causality constraint. There are two primary kinds of protocols:
Dear Emily:
I saw a long article that I wish to rebut carefully, what should
I do?
-- Angry
Dear Angry:
Include the entire text with your article, and include your comments
between the lines. Be sure to post, and not mail, even though your article
looks like a reply to the original. Everybody *loves* to read those long
point-by-point debates, especially when they evolve into name-calling and
lots of "Is too!" -- "Is not!" -- "Is too, twizot!" exchanges.
-- Emily Postnews Answers Your Questions on Netiquette
- this post brought to you by the Automated Last Post Generator...