Open AccessMartingales and Locality in Distributed Computing
Author(s) -
Devdatt Dubhashi
Publication year - 1998
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v5i23.19429
Subject(s) - locality , computer science , simple (philosophy) , martingale (probability theory) , mathematics , distributed algorithm , theoretical computer science , discrete mathematics , distributed computing , philosophy , linguistics , epistemology
We use Martingale inequalities to give a simple and uniform analysis of two families of distributed randomised algorithms for edge colouring graphs.