(Press-News.org) CAMBRIDGE, Mass-- Now that the Internet's basic protocols are more than 30 years old, network scientists are increasingly turning their attention to ad hoc networks — communications networks set up, on the fly, by wireless devices — where unsolved problems still abound.
Most theoretical analyses of ad hoc networks have assumed that the communications links within the network are stable. But that often isn't the case with real-world wireless devices — as anyone who's used a cellphone knows.
At the Association for Computing Machinery's Symposium on Principles of Distributed Computing in July, past and present researchers from the Theory of Distributed Systems Group at MIT's Computer Science and Artificial Intelligence Laboratory presented a new framework for analyzing ad hoc networks in which the quality of the communications links fluctuates. Within that framework, they provide mathematical bounds on the efficiency with which messages can propagate through the network, and they describe new algorithms that can achieve maximal efficiency.
"There's been a discrepancy between the theory, with its idealized models, and the reality of wireless networks," says Nancy Lynch, the NEC Professor of Software Science and Engineering at MIT and head of the Theory of Distributed Systems Group. "When people start designing theoretical algorithms, they tend to rely too heavily on the specific assumptions of the models. So the algorithms tend to be unrealistic and fragile."
In the past, some researchers have tried to model the unreliability of network links as random fluctuations. "But if you assume real randomness, then you can count on the randomness," Lynch says. "Somehow you can use that in your algorithm. Maybe randomness itself is giving you an assumption that's too strong."
Adversarial relationships
So Lynch and her coauthors on the new paper — Mohsen Ghaffari, a graduate student in electrical engineering and computer science, and Cal Newport, a former graduate student in Lynch's group who's now an assistant professor of computer science at Georgetown University — instead modeled the fluctuations in the links' quality as the willful manipulations of an "adversary." The adversary can't control all the links in the network: Some will remain up throughout the execution of the communication algorithm. But he can change the bandwidth of the others at will. And the network designer doesn't know in advance which links are reliable and which aren't.
"Your algorithm needs to work for all possible adversaries, some of which are benign and some of which might be doing the worst possible thing for your algorithm," Newport says. "In other words, it needs to work for all possible strategies for controlling the network."
In a paper that appeared two years ago, Newport, Lynch and colleagues assumed a very powerful adversary indeed — one that knew in advance every decision that every node in the network would make while trying to disseminate a message. In that context, they proved, efficient communication is impossible.
In the new paper, they weakened the adversary significantly. He may know exactly how the communications algorithm works, and he may intentionally try to thwart it, but he has to determine his pattern of link manipulation in advance, before the algorithm begins to run. Even this weakened adversary, however, has the potential to be much more disruptive than the types of interference that real-world wireless networks are likely to encounter — such as doors opening and closing, people turning on microwaves, or rain falling.
Lynch, Newport and Ghaffari examined two types of message dissemination. In the first, a single node of the network is trying to broadcast a message to all other nodes. In that case, they found, efficient communication is possible, even in the adversary's presence.
Geometrical supposition
The second case is that in which a number of nodes are each transmitting messages, and every one of their immediate neighbors has to receive a message from at least one transmitter. As it turns out, many common problems in the analysis of ad hoc networks boil down to this one.
Here, the researchers found that the adversary's presence can thwart efficient communication — but only if the network has an odd shape, in which a central node is connected to many nearby nodes that aren't connected to each other. That type of network layout is improbable in the real world: If two wireless devices are close enough to a third to communicate with it, they're likely to be able to communicate with each other, too.
Once the researchers added another assumption — that two devices connected to a third will at least sometimes be able to establish links with each other, too — efficient communication again becomes possible.
In both cases, the researchers' communication algorithms were able to thwart the adversary by using randomness. One of the problems with designing communications protocols for ad hoc wireless networks is that if two nearby nodes begin transmitting at the same time at the same frequency, they can interfere with each other, preventing either transmission from being received. The best-performing protocols thus assign each node a probability of transmitting during any one round of communication (where a round is defined by the time it takes for a node to send a message to its immediate neighbors).
The MIT researchers' algorithms adhere to this basic scheme — but rather than cycling through a prescribed sequence of steadily shrinking probabilities, they scramble the sequence up. In the case of the local broadcast, each separate message has to have its own unique sequence of probabilities. So clusters of nodes also temporarily elect local leaders that coordinate the probabilities for different transmitters. The researchers were able to show, however, that this extra computation didn't slow communication egregiously.
###
Written by Larry Hardesty, MIT News Office
Reliable communication, unreliable networks
A new model of wireless networks that better represents the real world could lead to more robust communications protocols
2013-08-05
ELSE PRESS RELEASES FROM THIS DATE:
Making a mini Mona Lisa
2013-08-05
The world's most famous painting has now been created on the world's smallest canvas. Researchers at the Georgia Institute of Technology have "painted" the Mona Lisa on a substrate surface approximately 30 microns in width – or one-third the width of a human hair. The team's creation, the "Mini Lisa," demonstrates a technique that could potentially be used to achieve nanomanufacturing of devices because the team was able to vary the surface concentration of molecules on such short-length scales.
The image was created with an atomic force microscope and a process called ...
Do antioxidants improve a woman's chances of conceiving?
2013-08-05
There is no high quality evidence that antioxidant supplements help to increase a woman's chances of having a baby, according to the results of a new systematic review. The review, published in The Cochrane Library, found women were no more likely to conceive when taking oral antioxidants and that there was limited information about potential harms.
Around a quarter of couples planning a baby are thought to have difficulty conceiving. Women undergoing fertility treatment often take dietary supplements, including antioxidants, to try to increase their chances of becoming ...
The brain's GPS: Researchers discover human neurons linked to navigation in open environments
2013-08-05
Using direct human brain recordings, a research team from Drexel University, the University of Pennsylvania, UCLA and Thomas Jefferson University has identified a new type of cell in the brain that helps people to keep track of their relative location while navigating an unfamiliar environment.
The "grid cell," which derives its name from the triangular grid pattern in which the cell activates during navigation, is distinct among brain cells because its activation represents multiple spatial locations. This behavior is how grid cells allow the brain to keep track of navigational ...
Researchers dismantle bacteria's war machinery
2013-08-05
This is a veritable mechanics of aggression on the nanoscale. Certain bacteria, including Staphylococcus aureus, have the ability to deploy tiny darts. This biological weapon kills the host cell by piercing the membrane. Researchers at EPFL have dismantled, piece by piece, this intriguing little machine and found an assembly of proteins that, in unfolding at the right time, takes the form of a spur. Published in Nature Chemical Biology, this discovery offers new insight into the fight against pathogens that are increasingly resistant to antibiotics.
To attack the host ...
Disorder can improve the performance of plastic solar cells, Stanford scientists say
2013-08-05
Scientists have spent decades trying to build flexible plastic solar cells efficient enough to compete with conventional cells made of silicon. To boost performance, research groups have tried creating new plastic materials that enhance the flow of electricity through the solar cell. Several groups expected to achieve good results by redesigning pliant polymers of plastic into orderly, silicon-like crystals, but the flow of electricity did not improve.
Recently, scientists discovered that disorder at the molecular level actually improves the polymers' performance. Now ...
Materials break, then remake, bonds to build strength
2013-08-05
DURHAM, N.C. -- Microscopic tears in a new kind of man-made material may actually help the substance bulk up like a bodybuilder at the gym.
"We've shown how normally destructive mechanical forces can be channeled to bring about stronger materials," said Duke chemist Steve Craig, who led the research. "The material responses are like Silly Putty transforming into a solid as stiff as the cap of a pen or a runny liquid transforming into soft Jell-O."
Scientists could one day use the stress-induced strength from these new materials to make better fluids such as engine ...
Global investigation reveals true scale of ocean warming
2013-08-05
Warming oceans are causing marine species to change breeding times and shift homes with expected substantial consequences for the broader marine landscape, according to a new global study.
The three-year research project, funded by the National Centre for Ecological Analysis and Synthesis in California, has shown widespread systemic shifts in measures such as distribution of species and phenology – the timing of nature's calendar – on a scale comparable to or greater than those observed on land.
The report, Global imprint of climate change on marine life, will form ...
Distinct brain disorders biologically linked
2013-08-05
A team of researchers have shown that schizophrenia and a disorder associated with autism and learning difficulties share a common biological pathway. This is one of the first times that researchers have uncovered genetic evidence for the underlying causes of schizophrenia.
The team found that a disruption of the gene TOP3B, an exceedingly rare occurrence in most parts of the world, is fairly common in a uniquely genetically distinct founder population from North-eastern Finland. In this population, which has grown in relative isolation for several centuries, the disruption ...
Mechanism offers promising new approach for harnessing the immune system to fight cancer
2013-08-05
St. Jude Children's Research Hospital scientists have discovered a way to target the immune system to shrink or eliminate tumors in mice without causing autoimmune problems. Researchers also found evidence that the same mechanism may operate in humans. The study was published today in the advance online edition of Nature.
The findings provide a new target for ongoing efforts to develop immunotherapies to harness the immune system to fight cancer and other diseases.
The work focused on white blood cells called regulatory T cells. These specialized cells serve as the ...
Practice makes the brain's motor cortex more efficient, Pitt researchers say
2013-08-05
PITTSBURGH, Aug. 4, 2013 – Not only does practice make perfect, it also makes for more efficient generation of neuronal activity in the primary motor cortex, the area of the brain that plans and executes movement, according to researchers from the University of Pittsburgh School of Medicine. Their findings, published online today in Nature Neuroscience, showed that practice leads to decreased metabolic activity for internally generated movements, but not for visually guided motor tasks, and suggest the motor cortex is "plastic" and a potential site for the storage of motor ...
LAST 30 PRESS RELEASES:
CMD-OPT model enables the discovery of a potent and selective RIPK2 inhibitor as preclinical candidate for the treatment of acute liver injury
Melatonin receptor 1a alleviates sleep fragmentation-aggravated testicular injury in T2DM by suppression of TAB1/TAK1 complex through FGFR1
Single-cell RNA sequencing reveals Shen-Bai-Jie-Du decoction retards colorectal tumorigenesis by regulating the TMEM131–TNF signaling pathway-mediated differentiation of immunosuppressive dendritic ce
Acta Pharmaceutica Sinica B Volume 15, Issue 7 Publishes
New research expands laser technology
Targeted radiation offers promise in patients with metastasized small cell lung cancer to the brain
A high clinically translatable strategy to anti-aging using hyaluronic acid and silk fibroin co-crosslinked hydrogels as dermal regenerative fillers
Mount Sinai researchers uncover differences in how males and females change their mind when reflecting on past mistakes
CTE and normal aging are difficult to distinguish, new study finds
Molecular arms race: How the genome defends itself against internal enemies
Tiny chip speeds up antibody mapping for faster vaccine design
KTU experts reveal why cultural heritage is important for community unity
More misfolded proteins than previously known may contribute to Alzheimer’s and dementia
“Too much going on”: Autistic adults overwhelmed by non-verbal social cues
What’s driving America’s deep freezes in a warming world?
A key role of brain protein in learning and memory is deciphered by scientists
Heart attacks don’t follow a Hollywood script
Erin M. Schuman wins 2026 Nakasone Award for discovery on neural synapse function and change during formation of memories
Global ocean analysis could replace costly in-situ sound speed profiles in seafloor positioning, study finds
Power in numbers: Small group professional coaching reduces rates of physician burnout by nearly 30%
Carbon capture, utilization, and storage: A comprehensive review of CCUS-EOR
New high-temperature stable dispersed particle gel for enhanced profile control in CCUS applications
State gun laws and firearm-related homicides and suicides
Use of tobacco and cannabis following state-level cannabis legalization
Long-term obesity and biological aging in young adults
Eindhoven University of Technology and JMIR Publications announce unlimited open access publishing agreement
Orphan nuclear receptors in metabolic dysfunction-associated steatotic liver disease development
A technological breakthrough for ultra-fast and greener AI
Pusan National University researchers identify key barriers hindering data-driven smart manufacturing adoption
Inking heterometallic nanosheets: A scalable breakthrough for coating, electronics, and electrocatalyst applications
[Press-News.org] Reliable communication, unreliable networksA new model of wireless networks that better represents the real world could lead to more robust communications protocols