Single-Bit Distributed Equality-Constraint Optimal Scheduling and Allocation

Single-Bit Distributed Equality-Constraint Optimal Scheduling and Allocation | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article Single-Bit Distributed Equality-Constraint Optimal Scheduling and Allocation mohammadreza Doostmohammadian, Hamid R. Rabiee This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-6189692/v1 This work is licensed under a CC BY 4.0 License Status: Posted Version 1 posted You are reading this latest preprint version Abstract Distributed resource allocation finds applications in multi-agent-based networked scheduling scenarios. In this work, a single-bit solution is proposed for distributed resource allocation to optimize strictly convex cost functions. The main contribution is that the proposed solution only requires the exchange of single-bit of (local) gradient information. This significantly reduces the computational complexity and communication load on agents. The solution further preserves anytime feasibility over weight-balanced directed graphs, which ensures that the equality-constraint (between resource and demand) is always met. This implies that at any termination time the allocated resources are equal to the demand and there is no service disruption. Due to the reduced order of information exchange and complexity, the proposed single-bit algorithm converges to the neighborhood of the optimal solution. The general Lyapunov-based proof technique (i) is regardless of this particular sign-based nonlinearity and (ii) holds under weak network connectivity (uniform-connectivity, i.e., connectivity of the union network over time). Further, the solution solves general (possibly) non-quadratic objectives including additive penalty terms (and barrier functions) to address the local box constraints approximations. The algorithm works over weight-balanced networks, relaxing the need for iterative stochastic weight design, e.g., in case of link failure or packet drops. Applications in power resource allocation and CPU scheduling are simulated to verify the theoretical results. Optimal resource allocation parallel data processing distributed learning constrained convex scheduling multi-agent networks Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Posted Version 1 posted You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-6189692","acceptedTermsAndConditions":true,"allowDirectSubmit":true,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":427112732,"identity":"8bc35f03-3c85-4728-9e1a-0c08e859a467","order_by":0,"name":"mohammadreza Doostmohammadian","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAAxElEQVRIiWNgGAWjYDCCAyCiAkmAjSgtB86QrOVgGwnOYuA73nz488d5dXK6s5ufPWCosWPgkz6AX4vkmWNpEge3HTY2u3PM3IDhWDIDG18Cfi0GN3LMGA5uO5C47UaCmQQD2wEGNh4CDgNqMf5wcE5d/bYb6d8kGP4Rp8VA4mADc4IZ0DoJxjYitID9cubYYcNtN3LKJBL7knkIagGF2IeKmjp5sxvp2yQ+fLOTk+8hoAUVJDAwELJjFIyCUTAKRgExAAAZAEJxTbU8bQAAAABJRU5ErkJggg==","orcid":"","institution":"Semnan University","correspondingAuthor":true,"prefix":"","firstName":"mohammadreza","middleName":"","lastName":"Doostmohammadian","suffix":""},{"id":427112733,"identity":"fc8f2c5f-9959-4007-88d4-a53148c22d7a","order_by":1,"name":"Hamid R. Rabiee","email":"","orcid":"","institution":"Sharif University of Technology","correspondingAuthor":false,"prefix":"","firstName":"Hamid","middleName":"R.","lastName":"Rabiee","suffix":""}],"badges":[],"createdAt":"2025-03-09 16:38:13","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-6189692/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-6189692/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":96085544,"identity":"0b2666d5-a80b-481a-bba6-545aa4d390c5","added_by":"auto","created_at":"2025-11-17 12:23:42","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":652154,"visible":true,"origin":"","legend":"","description":"","filename":"11MCSS.pdf","url":"https://assets-eu.researchsquare.com/files/rs-6189692/v1_covered_32bbc14c-a985-4d6f-82ce-0e5876891313.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Single-Bit Distributed Equality-Constraint Optimal Scheduling and Allocation","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":true,"highlight":"","institution":"","isAcceptedByJournal":false,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true},"keywords":"Optimal resource allocation, parallel data processing, distributed learning, constrained convex scheduling, multi-agent networks","lastPublishedDoi":"10.21203/rs.3.rs-6189692/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-6189692/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"Distributed resource allocation finds applications in multi-agent-based networked scheduling scenarios. In this work, a single-bit solution is proposed for distributed resource allocation to optimize strictly convex cost functions. The main contribution is that the proposed solution only requires the exchange of single-bit of (local) gradient information. This significantly reduces the computational complexity and communication load on agents. The solution further preserves anytime feasibility over weight-balanced directed graphs, which ensures that the equality-constraint (between resource and demand) is always met. This implies that at any termination time the allocated resources are equal to the demand and there is no service disruption. Due to the reduced order of information exchange and complexity, the proposed single-bit algorithm converges to the neighborhood of the optimal solution. The general Lyapunov-based proof technique (i) is regardless of this particular sign-based nonlinearity and (ii) holds under weak network connectivity (uniform-connectivity, i.e., connectivity of the union network over time). Further, the solution solves general (possibly) non-quadratic objectives including additive penalty terms (and barrier functions) to address the local box constraints approximations. The algorithm works over weight-balanced networks, relaxing the need for iterative stochastic weight design, e.g., in case of link failure or packet drops. Applications in power resource allocation and CPU scheduling are simulated to verify the theoretical results.","manuscriptTitle":"Single-Bit Distributed Equality-Constraint Optimal Scheduling and Allocation","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2025-03-13 09:04:05","doi":"10.21203/rs.3.rs-6189692/v1","editorialEvents":[{"type":"communityComments","content":0}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true}}],"origin":"","ownerIdentity":"73239206-d7a1-4fcd-b3e8-f61ea946fa91","owner":[],"postedDate":"March 13th, 2025","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"posted","subjectAreas":[],"tags":[],"updatedAt":"2025-11-17T12:23:10+00:00","versionOfRecord":[],"versionCreatedAt":"2025-03-13 09:04:05","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-6189692","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-6189692","identity":"rs-6189692","version":["v1"]},"buildId":"8U1c8b4HqxoKbykW_rLl7","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}