| Popis: |
Though it is common practice to treat synchronization primitives for multiprocessors as abstract data types, they are in reality machine instructions on registers. A crucial theoretical question with practical implications is the relationship between the size of the register and its computational power. We wish to study this question and choose as a first target the popularcompares?logn/loglognvalues andnread/write registers of size 2lognbits. That is,n=(k?1)! wherekis the number of values in thecompare&swapregister, so thecompare&swapregister has onlyO(loglogn) bits.2.We prove a tight tradeoff between the space and time necessary to solve leader election with acompare&swapregister. Specifically, we show that any algorithm for leader election amongnprocesses with akvalue compare&swap register, wherek?logn/loglogn, must have a run that accesses thecompare&swapregister ?(logkn) times. We conjecture that fork |
Full Text from ScienceDirect