{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,11]],"date-time":"2023-01-11T18:29:27Z","timestamp":1673461767007},"reference-count":7,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Parallel Process. Lett."],"published-print":{"date-parts":[[2016,3]]},"abstract":"<jats:p> We consider a message passing model with n nodes, each connected to all other nodes by a link that can deliver a message of B bits in a time unit (typically, B = O(log n)). We assume that each node has an input of size L bits (typically, L = O(n log n)) and the nodes cooperate in order to compute some function (i.e., perform a distributed task). We are interested in the number of rounds required to compute the function. <\/jats:p><jats:p> We give two results regarding this model. First, we show that most boolean functions require \u2038 L\/B \u2039 \u2212 1 rounds to compute deterministically, and that even if we consider randomized protocols that are allowed to err, the expected running time remains [Formula: see text] for most boolean function. Second, trying to find explicit functions that require superconstant time, we consider the pointer chasing problem. In this problem, each node i is given an array A<jats:sub>i<\/jats:sub> of length n whose entries are in [n], and the task is to find, for any [Formula: see text], the value of [Formula: see text]. We give a deterministic O(log n\/ log log n) round protocol for this function using message size B = O(log n), a slight but non-trivial improvement over the O(log n) bound provided by standard \u201cpointer doubling.\u201d The question of an explicit function (or functionality) that requires super constant number of rounds in this setting remains, however, open. <\/jats:p>","DOI":"10.1142\/s0129626416500043","type":"journal-article","created":{"date-parts":[[2016,3,28]],"date-time":"2016-03-28T02:05:18Z","timestamp":1459130718000},"page":"1650004","source":"Crossref","is-referenced-by-count":1,"title":["Clique Here: On the Distributed Complexity in Fully-Connected Networks"],"prefix":"10.1142","volume":"26","author":[{"given":"Benny","family":"Applebaum","sequence":"first","affiliation":[{"name":"School of Electrical Engineering, Tel Aviv University, Israel"}]},{"given":"Dariusz R.","family":"Kowalski","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Liverpool, UK"}]},{"given":"Boaz","family":"Patt-Shamir","sequence":"additional","affiliation":[{"name":"School of Electrical Engineering, Tel Aviv University, Israel"}]},{"given":"Adi","family":"Ros\u00e9n","sequence":"additional","affiliation":[{"name":"CNRS and Universit\u00e9 Paris Diderot, France"}]}],"member":"219","published-online":{"date-parts":[[2016,3,27]]},"reference":[{"key":"p_2","doi-asserted-by":"publisher","DOI":"10.1145\/4221.4227"},{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1007\/PL00001595"},{"key":"p_11","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704441848"},{"key":"p_12","doi-asserted-by":"publisher","DOI":"10.1137\/0222016"},{"key":"p_15","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1731"},{"key":"p_16","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(82)90008-6"},{"key":"p_17","doi-asserted-by":"publisher","DOI":"10.1145\/79173.79181"}],"container-title":["Parallel Processing Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129626416500043","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T08:29:59Z","timestamp":1565080199000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129626416500043"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,3]]},"references-count":7,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2016,3,27]]},"published-print":{"date-parts":[[2016,3]]}},"alternative-id":["10.1142\/S0129626416500043"],"URL":"https:\/\/doi.org\/10.1142\/s0129626416500043","relation":{},"ISSN":["0129-6264","1793-642X"],"issn-type":[{"value":"0129-6264","type":"print"},{"value":"1793-642X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,3]]}}}