NDLI: Local MST computation with short advice

Please wait, while we are loading the content...

Universal augmentation schemes for network navigability: overcoming the √n-barrier

Approximation algorithms for multiprocessor scheduling under uncertainty

Feasibility study of MPI implementation on the heterogeneous multi-core cell BE™ architecture

Optimal sparse matrix dense vector multiplication in the I/O-model

Scheduling threads for constructive cache sharing on CMPs

Tight bounds for distributed selection

Packing to angles and sectors

Weakening the online adversary just enough to get optimal conflict-free colorings for intervals

The notion of a timed register and its application to indulgent synchronization

Online frequency allocation in cellular networks

Maximizing total upload in latency-sensitive P2P applications

Cilk provides the "best overall productivity" for high performance computing: (and won the HPC challenge award to prove it)

Rate vs. buffer size: greedy information gathering on the line

Sparse parallel Delaunay mesh refinement

On triangulation of simple networks

Scheduling DAGs on asynchronous processors

Evaluating synchronization techniques for light-weight multithreaded/multicore architectures

The cache-oblivious gaussian elimination paradigm: theoretical framework, parallelization and experimental evaluation

Supermatrix out-of-order scheduling of matrix operations for SMP and multi-core architectures

Local MST computation with short advice

Conflict-free coloring for rectangle ranges using $O(n^{.382})$ colors

On the truthfulness and the approximation for scheduling selfish tasks

Nonblocking transactions without indirection using alert-on-update

Energy efficient randomised communication in unknown AdHoc networks

Bi-objective scheduling algorithms for optimizing makespan and reliability on heterogeneous systems

PRAM-on-chip: first commitment to silicon

Online collaborative filtering with nearly optimal dynamic regret

Using SIMD registers and instructions to enable instruction-level parallelism in sorting algorithms

Strong-diameter decompositions of minor free graphs

Scheduling to minimize gaps and power consumption

Towards soft optimization techniques for parallel cognitive applications

Cache-oblivious streaming B-trees

Proximity-aware directory-based coherence for multi-core processor architectures

Distributed approximation of capacitated dominating sets

Balanced allocations with heterogenous bins

Optimal bit-reversal using vector permutations

Time-based transactional memory with scalable time bases

Local strategies for maintaining a chain of relay stations between an explorer and a base station

Speed scaling on parallel processors

Transactional memory and the birthday paradox

Truthful unsplittable flow for large capacity networks

A tight bound on online buffer management for two-port shared-memory switches

An experimental comparison of cache-oblivious and cache-conscious programs

A parallel dynamic programming algorithm on a multi-core architecture

Deadlock-free scheduling of X10 computations with bounded resources

On the convergence of multicast games in directed networks

Local MST computation with short advice

Content Provider	ACM Digital Library
Author	Korman, Amos Fraigniaud, Pierre Lebhar, Emmanuelle
Abstract	We use the recently introduced advising scheme framework for measuring the difficulty of locally distributively computing a Minimum Spanning Tree (MST). An (m,t)-advising scheme for a distributed problem P is a way, for every possible input I of P, to provide an "advice" (i.e., a bit string) about I to each node so that: (1) the maximum size of the advices is at most m bits, and (2) the problem P can be solved distributively in at most t rounds using the advices as inputs. In case of MST, the output returned by each node of a weighted graph G is the edge leading to its parent in some rooted MST T of G. Clearly, there is a trivial (log n,0)-advising scheme for MST (each node is given the local port number of the edge leading to the root of some MST T), and it is known that any (0,t)-advising scheme satisfies t ≥ Ω (√n). Our main result is the construction of an (O(1),O(log n))-advising scheme for MST. That is, by only giving a constant number of bits of advice to each node, one can decrease exponentially the distributed computation time of MST in arbitrary graph, compared to algorithms dealing with the problem in absence of any a priori information. We also consider the average size of the advices. On the one hand, we show that any (m,0)-advising scheme for MST gives advices of average size Ω(log n). On the other hand we design an (m,1)-advising scheme for MST with advices of constant average size, that is one round is enough to decrease the average size of the advices from log(n) to constant.
Starting Page	154
Ending Page	160
Page Count	7
File Format	PDF
ISBN	9781595936677
DOI	10.1145/1248377.1248402
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2007-06-09
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Local computation Distributed algorithm Minimum spanning tree
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in