Lightweight Coloring and Desynchronization for Networks

We study the distributed desynchronization problem for graphs with arbitrary topology. Motivated by the severe computational limitations of sensor networks, we present a randomized algorithm for network desynchronization that uses an extremely lightweight model of computation, while being robust to...

Full description

Saved in:
Bibliographic Details
Main Authors: Motskin, A., Roughgarden, T., Skraba, P., Guibas, L.
Format: Conference Proceeding
Language:English
Subjects:
Communications Society
Computational modeling
Computer networks
Convergence
Distributed computing
Greedy algorithms
Network topology
Peer to peer computing
Protocols
State feedback
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites
container_end_page 2391
container_issue
container_start_page 2383
container_title
container_volume
creator Motskin, A.
Roughgarden, T.
Skraba, P.
Guibas, L.
description We study the distributed desynchronization problem for graphs with arbitrary topology. Motivated by the severe computational limitations of sensor networks, we present a randomized algorithm for network desynchronization that uses an extremely lightweight model of computation, while being robust to link volatility and node failure. These techniques also provide novel, ultra-lightweight randomized algorithms for quickly computing distributed vertex colorings using an asymptotically optimal number of colors.
doi_str_mv 10.1109/INFCOM.2009.5062165
format conference_proceeding
fullrecord <record><control><sourceid>ieee_6IE</sourceid><recordid>TN_cdi_ieee_primary_5062165</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><ieee_id>5062165</ieee_id><sourcerecordid>5062165</sourcerecordid><originalsourceid>FETCH-LOGICAL-i220t-bc74a13a6aaaa79a8ea2e9dc4972b6082a1d0acc32d750e26c8eac1a7d9531493</originalsourceid><addsrcrecordid>eNo1kMtOwzAURM1LopR8QTf5gYR7r1_xEgUKlUK7AYld5TpuaygJciJV7dcTRDmLmcWMZjGMTRByRDB3s_m0XLzkBGByCYpQyTOWGF2gICG4RC7P2YiUwMwUWlywm_-AzCUbgRY8Q6Xer1nSdR8wIEEDwojpKmy2_d7_alq2uzaGZpPapk4ffHdo3Da2TTjaPrRNum5jOvf9vo2f3S27Wttd55OTj9nb9PG1fM6qxdOsvK-yQAR9tnJaWORW2QFtbOEteVM7YTStFBRksQbrHKdaS_Ck3NBwaHVtJEdh-JhN_naD9375HcOXjYfl6QP-AxfBTH8</addsrcrecordid><sourcetype>Publisher</sourcetype><iscdi>true</iscdi><recordtype>conference_proceeding</recordtype></control><display><type>conference_proceeding</type><title>Lightweight Coloring and Desynchronization for Networks</title><source>IEEE Electronic Library (IEL) Conference Proceedings</source><creator>Motskin, A. ; Roughgarden, T. ; Skraba, P. ; Guibas, L.</creator><creatorcontrib>Motskin, A. ; Roughgarden, T. ; Skraba, P. ; Guibas, L.</creatorcontrib><description>We study the distributed desynchronization problem for graphs with arbitrary topology. Motivated by the severe computational limitations of sensor networks, we present a randomized algorithm for network desynchronization that uses an extremely lightweight model of computation, while being robust to link volatility and node failure. These techniques also provide novel, ultra-lightweight randomized algorithms for quickly computing distributed vertex colorings using an asymptotically optimal number of colors.</description><identifier>ISSN: 0743-166X</identifier><identifier>ISBN: 1424435129</identifier><identifier>ISBN: 9781424435128</identifier><identifier>EISSN: 2641-9874</identifier><identifier>EISBN: 9781424435135</identifier><identifier>EISBN: 1424435137</identifier><identifier>DOI: 10.1109/INFCOM.2009.5062165</identifier><language>eng</language><publisher>IEEE</publisher><subject>Communications Society ; Computational modeling ; Computer networks ; Convergence ; Distributed computing ; Greedy algorithms ; Network topology ; Peer to peer computing ; Protocols ; State feedback</subject><ispartof>IEEE INFOCOM 2009, 2009, p.2383-2391</ispartof><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://ieeexplore.ieee.org/document/5062165$$EHTML$$P50$$Gieee$$H</linktohtml><link.rule.ids>309,310,780,784,789,790,2058,27925,54555,54920,54932</link.rule.ids><linktorsrc>$$Uhttps://ieeexplore.ieee.org/document/5062165$$EView_record_in_IEEE$$FView_record_in_$$GIEEE</linktorsrc></links><search><creatorcontrib>Motskin, A.</creatorcontrib><creatorcontrib>Roughgarden, T.</creatorcontrib><creatorcontrib>Skraba, P.</creatorcontrib><creatorcontrib>Guibas, L.</creatorcontrib><title>Lightweight Coloring and Desynchronization for Networks</title><title>IEEE INFOCOM 2009</title><addtitle>INFCOM</addtitle><description>We study the distributed desynchronization problem for graphs with arbitrary topology. Motivated by the severe computational limitations of sensor networks, we present a randomized algorithm for network desynchronization that uses an extremely lightweight model of computation, while being robust to link volatility and node failure. These techniques also provide novel, ultra-lightweight randomized algorithms for quickly computing distributed vertex colorings using an asymptotically optimal number of colors.</description><subject>Communications Society</subject><subject>Computational modeling</subject><subject>Computer networks</subject><subject>Convergence</subject><subject>Distributed computing</subject><subject>Greedy algorithms</subject><subject>Network topology</subject><subject>Peer to peer computing</subject><subject>Protocols</subject><subject>State feedback</subject><issn>0743-166X</issn><issn>2641-9874</issn><isbn>1424435129</isbn><isbn>9781424435128</isbn><isbn>9781424435135</isbn><isbn>1424435137</isbn><fulltext>true</fulltext><rsrctype>conference_proceeding</rsrctype><creationdate>2009</creationdate><recordtype>conference_proceeding</recordtype><sourceid>6IE</sourceid><recordid>eNo1kMtOwzAURM1LopR8QTf5gYR7r1_xEgUKlUK7AYld5TpuaygJciJV7dcTRDmLmcWMZjGMTRByRDB3s_m0XLzkBGByCYpQyTOWGF2gICG4RC7P2YiUwMwUWlywm_-AzCUbgRY8Q6Xer1nSdR8wIEEDwojpKmy2_d7_alq2uzaGZpPapk4ffHdo3Da2TTjaPrRNum5jOvf9vo2f3S27Wttd55OTj9nb9PG1fM6qxdOsvK-yQAR9tnJaWORW2QFtbOEteVM7YTStFBRksQbrHKdaS_Ck3NBwaHVtJEdh-JhN_naD9375HcOXjYfl6QP-AxfBTH8</recordid><startdate>200904</startdate><enddate>200904</enddate><creator>Motskin, A.</creator><creator>Roughgarden, T.</creator><creator>Skraba, P.</creator><creator>Guibas, L.</creator><general>IEEE</general><scope>6IE</scope><scope>6IH</scope><scope>CBEJK</scope><scope>RIE</scope><scope>RIO</scope></search><sort><creationdate>200904</creationdate><title>Lightweight Coloring and Desynchronization for Networks</title><author>Motskin, A. ; Roughgarden, T. ; Skraba, P. ; Guibas, L.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-i220t-bc74a13a6aaaa79a8ea2e9dc4972b6082a1d0acc32d750e26c8eac1a7d9531493</frbrgroupid><rsrctype>conference_proceedings</rsrctype><prefilter>conference_proceedings</prefilter><language>eng</language><creationdate>2009</creationdate><topic>Communications Society</topic><topic>Computational modeling</topic><topic>Computer networks</topic><topic>Convergence</topic><topic>Distributed computing</topic><topic>Greedy algorithms</topic><topic>Network topology</topic><topic>Peer to peer computing</topic><topic>Protocols</topic><topic>State feedback</topic><toplevel>online_resources</toplevel><creatorcontrib>Motskin, A.</creatorcontrib><creatorcontrib>Roughgarden, T.</creatorcontrib><creatorcontrib>Skraba, P.</creatorcontrib><creatorcontrib>Guibas, L.</creatorcontrib><collection>IEEE Electronic Library (IEL) Conference Proceedings</collection><collection>IEEE Proceedings Order Plan (POP) 1998-present by volume</collection><collection>IEEE Xplore All Conference Proceedings</collection><collection>IEEE/IET Electronic Library</collection><collection>IEEE Proceedings Order Plans (POP) 1998-present</collection></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext_linktorsrc</fulltext></delivery><addata><au>Motskin, A.</au><au>Roughgarden, T.</au><au>Skraba, P.</au><au>Guibas, L.</au><format>book</format><genre>proceeding</genre><ristype>CONF</ristype><atitle>Lightweight Coloring and Desynchronization for Networks</atitle><btitle>IEEE INFOCOM 2009</btitle><stitle>INFCOM</stitle><date>2009-04</date><risdate>2009</risdate><spage>2383</spage><epage>2391</epage><pages>2383-2391</pages><issn>0743-166X</issn><eissn>2641-9874</eissn><isbn>1424435129</isbn><isbn>9781424435128</isbn><eisbn>9781424435135</eisbn><eisbn>1424435137</eisbn><abstract>We study the distributed desynchronization problem for graphs with arbitrary topology. Motivated by the severe computational limitations of sensor networks, we present a randomized algorithm for network desynchronization that uses an extremely lightweight model of computation, while being robust to link volatility and node failure. These techniques also provide novel, ultra-lightweight randomized algorithms for quickly computing distributed vertex colorings using an asymptotically optimal number of colors.</abstract><pub>IEEE</pub><doi>10.1109/INFCOM.2009.5062165</doi><tpages>9</tpages><oa>free_for_read</oa></addata></record>
fulltext fulltext_linktorsrc
identifier ISSN: 0743-166X
ispartof IEEE INFOCOM 2009, 2009, p.2383-2391
issn 0743-166X
2641-9874
language eng
recordid cdi_ieee_primary_5062165
source IEEE Electronic Library (IEL) Conference Proceedings
subjects Communications Society
Computational modeling
Computer networks
Convergence
Distributed computing
Greedy algorithms
Network topology
Peer to peer computing
Protocols
State feedback
title Lightweight Coloring and Desynchronization for Networks
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2024-12-27T19%3A17%3A24IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-ieee_6IE&rft_val_fmt=info:ofi/fmt:kev:mtx:book&rft.genre=proceeding&rft.atitle=Lightweight%20Coloring%20and%20Desynchronization%20for%20Networks&rft.btitle=IEEE%20INFOCOM%202009&rft.au=Motskin,%20A.&rft.date=2009-04&rft.spage=2383&rft.epage=2391&rft.pages=2383-2391&rft.issn=0743-166X&rft.eissn=2641-9874&rft.isbn=1424435129&rft.isbn_list=9781424435128&rft_id=info:doi/10.1109/INFCOM.2009.5062165&rft.eisbn=9781424435135&rft.eisbn_list=1424435137&rft_dat=%3Cieee_6IE%3E5062165%3C/ieee_6IE%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-i220t-bc74a13a6aaaa79a8ea2e9dc4972b6082a1d0acc32d750e26c8eac1a7d9531493%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rft_ieee_id=5062165&rfr_iscdi=true